Комбинаторика
Комбинаторика располагает столь многообразными методами, решает столь разнообразные задачи, что трудно чётко обозначить её границы. Условно в комбинаторной теории можно выделить следующие три большие части (см. схему):
- Теорию конфигураций, включающую блок - схемы, группы подстановок, теорию кодирования.
- Теорию перечисления, содержащую производящие функции, теоремы обращения и исчисление конечных разностей.
- Теорию порядка, включающую конечные упорядоченные множества и решётки, матрицы и теоремы существования, подобные теоремам Холла и Рамсея.
Следует ещё раз подчеркнуть в высшей степени условный характер представленной схемы. Повсеместно можно наблюдать взаимную связь перечисленных разделов комбинаторики. Например, перечислительная комбинаторика рассматривает задачи, относящиеся и к конфигурациям, и к упорядоченным множествам.
Теория конфигураций и теория перечисления
Теория конфигураций является традиционным и наиболее разработанным разделом комбинаторики. Теория конфигураций рассматривает задачи выбора и расположения элементов некоторого, обычно конечного, множества, в соответствии с заданными правилами. Перечислительная комбинаторика основным методом исследования провозгласила метод производящих функций, используя который было доказано громадное число комбинаторных тождеств.
Элементарными комбинаторными конфигурациями являются сочетания, размещения, перестановки. Для подсчёта числа этих конфигураций используются правила суммы и произведения.
Правило суммы:
Если элемент A можно выбрать m способами, а элемент B можно выбрать k способами, то выбор элемента A или B можно осуществить m + k способами.
Правило суммы можно перефразировать на теоретико-множественном языке. Обозначим через | A | число элементов множества A, через A 
B - объединение множеств A и B, через A x B - декартово произведение множеств A и B. Тогда для непересекающихся множеств A и B выполняется равенство:
| A 
B | = | A | + | B |.
Обобщением правила суммы является правило произведения.
Правило произведения:
Если элемент A можно выбрать m способами, а после каждого выбора элемента A элемент B можно выбрать k способами, тогда, упорядоченную пару элементов (A, B) можно выбрать m*k способами.
Правило произведения можно распространить на выбор последовательности (x1, x2, …, xn) произвольной конечной длины n.
На теоретико-множественном языке правило произведения формулируется так: | A х B | = | A | 
| B |.
Размещения.
Назовём множество, содержащее n элементов, n -множеством.
Последовательность (x1, x2, …, xk) длины k без повторяющихся элементов из элементов данного n -множества назовём k -размещением.
Обозначим символом 
число размещений из n по k элементов (от фран. "arrangement" - размещение). Используя правило произведения, вычислим число .
Пусть произвольное размещение длины k имеет вид:
(x1, x2, …, xk).
Элемент x1 можно выбрать n способами. После каждого выбора x1 элемент x2 можно выбрать
(n - 1) способами. После каждого выбора элементов x1 и x2 элемент x3 можно выбрать (n - 2) способами, и т.д. После каждого выбора элементов x1, x2, …, xk-1 элемент xk можно выбрать
(n - (k - 1)) = (n - k + 1) способами. Тогда, по правилу произведения, последовательность
(x1; x2;, …, xk) можно выбрать числом способов, равным
n (n - 1)(n - 2) … (n - k + 1) = 
Произведение в левой части равенства умножим и разделим на (n - k)!, получим:
.
Если k = n, то 
есть число Pn перестановок из n элементов
Pn = n! (от "permutation"- перестановка).
Сочетания.
k -подмножество данного n -множества называется k -сочетанием.
Обозначим через 
число k -сочетаний из данных n элементов. Формулу для числа 
получим, рассуждая следующим образом. Если каждое сочетание упорядочить всеми возможными способами, то получим все k -последовательностей из n элементов, без повторений, то есть все k -размещения.
Иными словами, 
Откуда: 
или 
Предполагая, что n и k - целые положительные числа и 0!=1, сформулируем основные свойства сочетаний.
Основные свойства сочетаний.
1. Условились, что 
2. 
3. 
4. 
5. 
Сочетания и размещения широко используются при вычислении классической вероятности случайных событий.
Таблица 1.Треугольник Паскаля
| n | 
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
|
Заметим, что Блез Паскаль называл числовой треугольник, начало которого содержится в таблице1, арифметическим. Паскаль посвятил свойствам арифметического треугольника основополагающий "Трактат об арифметическом треугольнике" (1654). Справедливости ради, стоит упомянуть, что биномиальные коэффициенты были хорошо известны в Азии за много веков до рождения Паскаля. В Италии треугольник Паскаля называют треугольником Тартальи.
Сочетания имеют многочисленные интерпретации и приложения. Сочетания 
являются биномиальными коэффициентами в разложении бинома
В этой интерпретации индексы могут принимать вещественные значения. Используя свойства биномиальных коэффициентов (при разных ограничениях на выбор верхних и нижних индексов), доказано громадное число комбинаторных тождеств, составивших самостоятельный раздел комбинаторной математики. В частности, из формулы выше при x = 1, получим 
, при
x = -1, n > 0, получим 
, продифференцировав равенство, получим при x = 1, 
и т.д.
Существует тесная связь между подмножествами множества и разложениями целого (положительного) числа. Разложение n есть представление числа n в виде упорядоченной суммы положительных целых чисел. Например, существует восемь разложений числа 4, именно:
1+1+1+1 3+1
2+1+1 1+3
1+2+1 2+2
1+1+2 4
Если разложение 
содержит в точности k слагаемых, то говорят, что 
имеет k частей и называется k -разложением. Для k -разложения числа n: a1 + a2 + … + an - определим
(k - 1)-подмножество 
(
), (n - 1)-множества {1, 2, …, n-1}, формулой.
() ={ a1, a1 + a2,…, a1 + a2 +…+ ak-1 }
Эта формула устанавливает биекцию между всеми k -разложениями числа n и (k - 1)-подмножествами (n - 1)-множества.
Следовательно, существует 
k -разложений числа n и 2n-1 разложений числа n. Биекцию 
часто схематично изображают строкой, состоящей из n точек и k - 1 разделяющей вертикальной черты. Точки разделились по k линейно упорядоченным "купе"; числа точек в "купе" соответствуют слагаемым в k -разложении числа n. Например, строка | 
| | | | соответствует разложению 1+2+1+1+3+2. Другая проблема, тесно связанная с разложениями, есть задача подсчёта числа N (n, k) решений уравнения
x1 + x2 + …+ xk = n
Неотрицательные целые решения уравнения называются слабыми k -разложениями числа n. Число неотрицательных целых решений уравнения равно числу положительных решений уравнения
y1 + y2 + … + yk = n + k,
то есть числу k -разложений числа n + k. Таким образом, N (n, k) = 
.
Если k -сочетание содержит повторяющиеся элементы, то такое k -сочетание называют
k -мультимножеством. Число всех k -сочетаний с повторениями из данного n -элементного множества обозначим через 
, где
Сочетание 
можно интерпретировать, как распределение элементов n -множества S между двумя категориями, первая из которых содержит k элементов, вторая содержит n - k элементов. Обобщим это представление. Пусть (a1, a2, …, am)- последовательность неотрицательных целых чисел, сумма которых равна n. Рассмотрим m категорий C1, C2, … Cm.
Обозначим символом 
число способов распределения n элементов среди категорий C1, C2, … Cm так, чтобы категории Ci принадлежало точно ai элементов. Тогда 
Блок-схемы
Комбинаторные конфигурации наиболее общего вида были исследованы в 30-е годы XX столетия и были названы блок-схемами (block design). Блок-схемы состоят из наборов элементов, называемых блоками. Выбор элементов и пар элементов в блоки подчиняются определённым правилам.
Уравновешенной неполной блок-схемой называется такое размещение v различных элементов по b блокам, что каждый блок содержит точно k различных элементов, каждый элемент появляется точно в k различных блоках и каждая пара различных элементов ai, aj появляется точно в 
блоках.
Множество всех 
сочетаний из v элементов по k, взятых в качестве блоков, образует полную блок-схему. Часть этих сочетаний, в которых каждая пара ai, aj появляется одно и то же число раз, является неполной, но уравновешенной блок-схемой. Между пятью параметрами блок-схемы выполняются следующие два соотношения:
bk = vr
r (k - 1) = (v - 1)
Частным случаем блок-схем являются так называемые конечные плоскости. Выберем конечное множество P. Элементы из P назовём точками. Некоторые подмножества из P назовём прямыми. Пусть отношение инцидентности между точками и прямыми удовлетворяет следующим геометрическим аксиомам.
1. На каждой прямой лежит n точек B.
2. Через каждую точку проходят n прямых.
3. Любые две прямые пересекаются в одной точке.
4. Через любые две точки проходит единственная прямая.
5. Существуют 4 точки неколлинеарные по три.
Тогда конечное множество P точек и множество L прямых образует конечную проективную плоскость.
Пример:
P = { 1, 2, 3, 4, 5, 6, 7 }.
L = { l1, l2, l3, l4, l5, l6, l7 }
l1 = {1, 2, 3}, l2 = {3, 4, 5}, l3 = {1, 5, 6}, l4 = {1, 4, 7}, l5 = {2, 5, 7},
l6 = {3, 6, 7}, l7 = {2, 4, 6}.
Пример 1.
Александр, Питре, Дэйв, Роза, Люси часто ходят в столовую. Каждый раз, обедая там, они рассаживаются по-разному. Сколько дней сотрудники отдела смогут это сделать без повторения?
1)Пронумеруем стулья, на которых должен сесть каждый, и будем считать, что они рассаживаются поочередно:
№1 - Александр - есть возможность выбрать из 5 вариантов (стульев)
№2 - Питре - 4 варианта
№3- Дэйв - 3 варианта
№4- Роза - 2 варианта
№5 - Люси - 1 вариант
Используя правило умножения, получаем: 5х4х3х2х1=120
2)Используя понятие факториала: 5!=120
Пример 2.
В программном отделе лучше всех программирование на Java знают 5 кодеров: Вильям, Дак, Олов, Кэйт и Эприл. На конференцию по новым средствам программирования нужно отправить пару, состоящую из 1 юноши и 1 девушки. Сколькими способами директор может эту пару выбрать?
1) Обозначим имена кандидатов первыми заглавными буквами.
Получаем следующие пары:
В-К, В-Э, Д-К, Д-Э, О-К, О-А.
Ответ: 6 пар.
2) Юношей 3, из них 1 можно выбрать 
, девушек 2, из них можно 1 выбрать 
, используя правило умножения, получаем:
х = 6
Пример 3.
Лари на работе имеет 7 флеш-накопителей, а Роберт - 9. Сколькими способами они могут обменять 4 любых накопителя одного на 4 другого?
Вычислим, сколько четверок из 7 накопителей можно составить у Лари:
=35, число четверок у Роберта из 9 накопителей - 
= 126
По правилу умножения находим число обменов 35х126=4410
Пример 4.
Доступ к компьютеру системного администратора защищен паролем, состоящим из двух различных гласных букв русского алфавита, за которой следуют 3 различные цифры. Сколько вариантов придется перебрать хакеру получить доступ к его компьютеру?
В русском языке 9 гласных букв - а, е, е, и, о, у, э, ю, я. Выбрать из них 2 можно 
=36 способами. Из 10 цифр выбрать 3 можно 
=120 способами. Применяя правило умножения, получаем:
36х120=4320