1.9 Комбинаторика
Число (n, k)-размещений без повторений Akn может быть определено с помощью правила произведения.
Первый из k элементов размещения может быть выбран n способами, второй - (n-1) способами, поскольку элемент, выбранный
первым, не должен быть повторен; аналогично, для третьего (если k > 2) элемента остается (n-2) способов и тд. Всего k
элементов могут быть выбраны
Akn = n∙(n-1)∙ ... ∙(n-k+1) способами: произведение k убывающих
на 1 сомножителей, начиная с n. По-другому, используя обозначение n!=1∙2∙ ... ∙n, можно записать:
Akn = n!/(n-k)!
Примеры
А37=7!/4! = 7·6·5 = 210; А47 = 7!/3! = 7·6·5·4 = 840; А57 =7!/2! = 7·6·5·4·3 = 2520.
Если k = 1, то А1n = n!/(n - 1)! = n; если k = n - 1, то Аn-1n = n! / 1! = n!;
Если k = n, то Аnn = n! / 0! = [для единообразия формул удобно считать, что 0! = 1!] = n!.
Равенство чисел Аn-1n и Аnn естественно: если выбраны (n - 1) элементов из n, то единственный оставшийся элемент может быть выбран одним способом, и это не изменяет числа Аn-1n по сравнению с Аnn
Таким образом, число n-перестановок Рn равно n!. (n, k)-размещения с повторениями - это кортежи (по-другому, слова) длины k в n-элементном алфавите. Используя правило произведения, нетрудно показать, что число различных (n, k)-размещений с повторениями Akn = nk . Действительно, каждый из n членов упорядоченной последовательности может быть выбран n способами, независимо от других, а число их равно k.
Примеры
- Число слов длины k в алфавите {0, 1 } равно 2k; таково же число всех подмножеств k-элементного множества, поскольку множество однозначно задается своей характеристической функцией. Число k - значных двоичных чисел равно 2k-1 т.к. первая цифра должна равняться 1.
- Число k - значных десятичных чисел (т.е. имеющих ровно k знаков) равно 9 ∙ 10k-1: 1. их можно рассматривать как слова в алфавите {0, 1, 2,..., 9}, причем первая цифра должна быть отлична от 0.
2. Числа (n, k)-сочетаний без повторений обозначаются символами Ckn или (n, k) и называются также биномиальными коэффициентами, поскольку совпадают с коэффициентами формулы бинома Ньютона для n-й степени двучлена
 | (7)
|
Действительно, коэффициент при члене xk ∙ yn-k равен числу способов, которыми из n одинаковых сомножителей (х + у) ∙ (х + у) ∙ ... ∙ (х + у) можно выбрать k (в них выбирается х, а в остальных у -произведение выбранных так множителей равно как раз xk ∙ yn-k).
Для пересчета (n, k)-сочетаний без повторений удобно рассмотреть разбиение множества всех (n,k)-размещений без повторений на классы эквивалентности по отношению "иметь одинаковый состав элементов"; сочетания, отличающиеся составом элементов, попадают в различные классы. В каждом из классов содержатся упорядоченные конфигурации из одних и тех же k различных элементов, т.е. они представляют k-перестановки, и в каждом классе их число равно k!. Отсюда число Ckn (n, k)-сочетаний без повторений равно Akn /k!, т.е.
 | (8)
|
Для небольших значений k удобнее последнее выражение для Ckn, поскольку в нем и в числителе, и в знаменателе - по k сомножителей: в числителе - отрезок натурального ряда, начиная с n, по убыванию; в знаменателе - отрезок натурального ряда [1, k], начиная с 1, по возрастанию.
В частности, C0n = 1, С1n= n, C2n = n∙(n-l)/2. Удобно также считать, что Ckn =0, если k > n.
Примеры

Приведем некоторые свойства биномиальных коэффициентов.
- Ckn = Cn-kn.Это следует как из формулы (8), так и из того, что выборка k элементов из n однозначно определяет дополнение: выборку (n - k) оставшихся элементов из n. Отсюда и из предыдущих равенств следуют
Cnn= Cn0=1, Cnn-1= Cn1=n.
Например,

В последнем равенстве в числителе и в знаменателе выделены скобками одинаковые сомножители.
- следует из подстановки х = у = 1 в формулу (7).
1 + 5 + 10 + 10 + 5 + 1 = 32 = 25.
1 + 6 + 15 + 20 + 15 + 6 + 1 = 64 = 26.
- следует из подстановки х = 1, у = -1 в формулу (7).
Например, для n = 6 : 1 - 6 + 15 - 20 + 15 - 6 + 1 = 0.
Используя свойство 3, покажем справедливость формулы (6) -принципа включения и исключения. Действительно, объект считается один раз в N, если не обладает никаким свойством, и совсем не учитывается во всех остальных слагаемых. Объект, имеющий t > О свойств, принимается за 1 в общем числе N, за (-t) в -
Ni, за С2t в
и вообще за (-1)s- Сst в сумме (-1)s

Но для t>1 из свойства 3 имеем: 1-t+ Ct2+...+(-1)s Cts+...= 0.
Таким образом, всякий объект, не обладающий никаким из свойств, вносит 1 в правую часть формулы (6), а объект, обладающий t > 1 свойствами, вносит 0. Это доказывает формулу (6).
-
∙ k = n ∙ 2n-1 . Чтобы убедиться в справедливости равенства, представим, что для каждого сочетания из n элементов {а1, а2,..., аn} выписаны на отдельную карточку символы аi1,ai2,...,аik, соответствующие элементам этого (k-элементного) сочетания: всего карточек - 2n (по свойству 2). Тогда суммарное число символов на всех карточках можно подсчитать двояко:
- Суммарное число символов на Сkn карточках, содержащих ровно k символов, равно k ∙ Сkn ; в левой части рассматриваемого равенства -общее число символов на всех карточках для k = 0, 1,..., n.
- Если зачеркнуть некоторый символ а, на всех карточках, на которых он написан, то на них останутся всевозможные сочетания из остальных (n - 1) элементов (их число - 2n-1); значит символ аi, написан ровно на 2n-1 карточках. Общее число символов n ∙ 2n-1 - в правой части равенства.
Например, для n = 5: 0 ∙ 1 + 1 ∙ 5 + 2 ∙ 10 + 3 ∙ 10 + 4 ∙ 5 + 5 ∙ 1 = 80 = 5-24.
Для n = 6: 0 ∙ 1 + 1 -6 + 2- 15 + 3 ∙ 20 + 4- 15 + 5 -6 + 6- 1 = 192= i 6 ∙ 25.
- Сkn = Сk-1n-1 + Сkn-1. Равенство следует из такого рассуждения. Зафиксируем некоторый элемент х n-элементного множества. Совокупность всех k-элементных подмножеств последнего (их число -левая часть равенства) разбивается на два непересекающихся класса:
содержащих и не содержащих элемент х. В первом классе Сk-1n-1 подмножеств: они содержат х и (k - 1) из остальных (n - 1) элементов. Во втором классе, очевидно, Сkn-1 элементов. Последнее тождество связано со схемой, называемой треугольником Паскаля (рисунок 1). Если перенумеровать по порядку строки этого треугольника числами 0,1, 2,..., то i-я строка окажется состоящей из чисел С0i , С1i ,..., Сii .
В силу свойства 5 каждое число строки, кроме крайних, равных единице, можно получить как сумму двух ближайших чисел, находящихся над мим в предыдущем ряду. Это дает простой метод построения треугольника Паскаля и, тем самым, нахождения биномиальных коэффициентов: n-я строка задает коэффициенты бинома (х + у)n. Замечание. Свойство (5) представляет собой пример рекуррентного (возвратного) соотношения: величина Сkn рассматриваемая как функция двух аргументов n, k, выражается через значения этой же функций при других (здесь - меньших) значениях переменных.
0 | | | | | | | | | | | | 1 |
1 | | | | | | | | | | | 1 | | 1 | | | | | |
2 | | | | | | | | | | 1 | | 2 | | 1 |
3 | | | | | | | | | 1 | | 3 | | 3 | | 1 | | | | |
4 | | | | | | | | 1 | | 4 | | 6 | | 4 | | 1 | | | | | | |
5 | | | | | | | 1 | | 5 | | 10 | | 10 | | 5 | | 1 |
6 | | | | | | 1 | | 5 | | 15 | | 20 | | 15 | | 5 | | 1 | | | | | |
7 | | | | | 1 | | 7 | | 21 | | 35 | | 35 | | 21 | | 7 | | 1 | | | | |
8 | | | | 1 | | 8 | | 28 | | 56 | | 70 | | 56 | | 28 | | 8 | | 1 | | | |
9 | | | 1 | | 9 | | 36 | | 84 | | 126 | | 126 | | 84 | | 36 | | 9 | | 1 |
10 | | 1 | | 10 | | 45 | | 120 | | 210 | | 252 | | 210 | | 120 | | 45 | | 10 | | 1 | |
11 | 1 | | 11 | | 55 | | 165 | | 330 | | 462 | | 462 | | 330 | | 165 | | 55 | | 11 | | 1 |
. . . . . . . . . . . . . . . . . . . . . . . . . . . . |
Рисунок 1 - Треугольник Паскаля
|
(тождество Коши). Для доказательства удобно рассмотреть такую интерпретацию. Пусть из группы, состоящей из m мужчин и n женщин, выбирается делегация k человек. Это можно сделать Cm+nk способами. Все k-элементные подмножества нашего (m + n)- J элементного множества можно классифицировать по числу мужчин в делегации, k-элементную делегацию, содержащую s мужчин, можно получить, выбирая сначала s мужчин одним из С5m способов, а затем (k - s) женщин одним из Ck-sn способов. По правилу произведения число таких делегаций равно Csm -Ck-1n, а по правилу суммы общее число k-элементных делегаций такое, как в правой части равенства.
Пример. С410=С47+3=-С07+ С43+С17+ С33+С27+ С23+ С37∙С13+С47∙С03 = [учитывая, что С34 = 0] = 7∙1 + 21 ∙ 3 + 35 ∙ 3 + 35 ∙ 1 = 210.
- Чтобы получить число (n, k)-сочетаний с повторениями Ckn. поставим в соответствие каждому такому сочетанию (т.е. неупорядоченной k-выборке из n-элементного множества) кортеж в двухбуквенном алфавите (0, 1} следующим образом. Составим сначала кортеж из n натуральных чисел {аi}, так что а равно числу i-x элементов n-множества, входящих в данную k-выборку. Некоторые а, могут быть равны 0. Сумма n компонент этого кортежа равна k. Далее составим кортеж из нулей и единиц, заменив каждое число аi на аi единиц, перемежая их нулями: 11..101...10...00...
Если некоторое аi = 0, то между соответствующими нулями не будет ни одной единицы. Говоря по-другому, кортеж из (n - 1) нулей определяет n мест: слева от всего кортежа и справа от каждого из нулей. На место i вставим а, единиц (некоторые аi, как сказано выше, могут равняться 0).
Например, (4, 7)-сочетанию (1,1,3,4,4,4,4) соответствует кортеж (2,0,1,4), а ему, в свою очередь, - кортеж 1100101111; (4, 7)-сочетанию(1, 2, 2, 2, 3, 3, 3) соответствует сначала кортеж (1, 3, 3, 0), а затем кортеж 1011101110.
В результате получаем набор из (n - 1) нулей k единиц, т.е. вектор длины (n - k + 1). Обратно, каждому такому вектору соответствует (n, k) -сочетание: серии идущих подряд единиц определяют числа аi - их сумма равна k. Поэтому: Сkn= Сkn+k-1= Сkn= Сn-1n+k-1
Равенство (9) можно получить и другим способом. Пусть (с1, с2,..., ck) - (n, k)-сочетание с повторениями, причем с1 < с2 <. ... < ck. Сопоставим ему выборку (d1, d2,..., dk), где d1 = с1 + 0, d2 = c2 + 1, d3 = с3 + 2,... dk = ck + k - 1. Все числа d различны - поэтому выборка (d1, d2,..., dk) может рассматриваться как (n+k-1, k)-сочетание без повторений. Обратно, каждому (n+k-1, k)-сочетанию без повторений соответствует (n, k)-сочетание, возможно с повторениями, откуда следует равенство (9).
Пример. С43= С46 = 6∙5/2=15 В таблице 1 перечислены все 15 (3, 4)-сочетаний с повторениями из 3 элементов по 4 вместе с соответствующими им кортежами и соответствующими (6, 4)-сочетаниями без повторений.
Таблица 1
4,0,0 | 111100 | 1234 |
3,1,0 | 111010 | 1235 |
3,0,1 | 111001 | 1236 |
2,2,0 | 110110 | 1245 |
2,1,1 | 110101 | 1246 |
2,0,2 | 110011 | 1256 |
1,3,0 | 101110 | 1345 |
1,2,1 | 101101 | 1346 |
1,1,2 | 101011 | 1356 |
1,0,3 | 100111 | 1456 |
0,4,0 | 011110 | 2345 |
0,3,1 | 011101 | 2346 |
0,2,2 | 011011 | 2356 |
0,1,3 | 010111 | 2456 |
0,0,4 | 001111 | 3456 |
- Рассмотрим всевозможные размещения с повторениями а1а2...аn из n элементов с дополнительным условием: в каждом из них b1, элементов первого рода, b2 элементов второго рода и вообще bi, элементов i-ro рода (1=1, 2,..., r). Естественно, выполнено равенство b1, + b2 +...+ br = n. Заменим bi элементов i-ro рода различающимися элементами bi1, .....,bib так, чтобы все элементы стали различными, и получим n! перестановок. Каждое исходное размещение дает b1! b2!... br! перестановок. Следовательно, число исходных размещений равно
где b1+ b2+... br=n
Это число называется полиномиальным коэффициентом: оно равно коэффициенту при произведении xb11 xb21 xbrr в разложении по степеням переменных полинома (х1, + х2 + ...+ хr)n. Биномиальные коэффициенты представляют частный случай при r = 2.
- Еще один пример применения принципа включения и исключения дает задача о беспорядках (другое название - задача о встречах); сколько существует перестановок а1, а2,..., аn чисел 1, 2 ..... n таких, что аi=i при любом i=1,2 ..... n?
Обозначим это число через Dn и воспользуемся формулой (6). Здесь N элементов - это n! перестановок а1, а2 ..... аn, а свойство P(i) выражается равенством ai = i (i = 1, 2 ..... n). Тогда Ni1,i2...ir = (n - r)! - число перестановок, оставляющих на месте r определенных символов.
Далее, в
Ni1i2...ir имеется Сrn слагаемых - по числу способов N(0) = n! - n ∙ (n-1)! + С2n ∙ (n-2)! -...+ (-1)r ∙ Сrn ∙ (n-r)! +...+(-1)n∙1 = n!-n∙(n-1)! + n∙((n-1)/2)-(n-2)! -...+ (-1)r ∙ (n∙ (n-1)-...- (n-r+1)/ r!) ∙ (n-r)! +..>(-1)n = n! ∙ (1 - 1 + 1/2! - 1/3! +...+ (-1)r/r! +...+ (-1)n/n!).
Сумма 1 - 1 + 1/2! - 1/3! +...+ (-1)r/r! +...+ (-1)n/n!, заключенная в скобки - это частная сумма бесконечного ряда для числа е-1. Поэтому N(0), равное Dn, есть целое число, ближайшее к n!/е, т.е. Dn/N!= e-1
Вот простая интерпретация формулы (10). Если n писем для различных адресатов случайным образом разложены в n конвертах написанными адресами, то с вероятностью, близкой к 1/е = 0.368, НИ один из т адресатов не получит предназначенного ему письма. Может показаться парадоксальным,
- Одна из классических задач комбинаторики - определить число способов разместить некоторое множество объектов в каком-то количестве "ящиков" так, чтобы были выполнены заданные ограничения.
Если даны два множества X, Y, причем X=n, Y=n, то всякая функция f: X
Y задает такое размещение,
если считать X объектами, а Y - ящиками и трактовать f(xi) =уi как помещение объекта х в ящик у.
Другая интерпретация - раскраска: Y - множество "цветов" и f(x) - цвет объекта х. Тогда задачу можно сформулировать как определение количества раскрасок с соблюдением некоторых ограничений.
Заметим, что без потери общности можно всегда считать, что X = {1, 2,...,n}, a Y = {1, 2,..., m}. Если не накладывать никаких ограничений на размещения, то число всех функций f: X
Y равно mn, ибо это просто (m, n)-размещения с повторениями.
Если каждый ящик содержит не более одного объекта, то мы имеем (m, n)-размещения без повторений; при этом m > n. Их число
равно Аnm : из m упорядоченных ящиков мы выбираем n и кладем в них одному объекту. Если же n > m, то такое размещение, очевидно, невозможно. Здесь вступает в силу так называемый принцип Дирихле, или принцип ящиков - если в m ящиках находятся (m + 1) или больше камней, то хотя бы в одном из ящиков больше одного камня.
Если мы размещаем n объектов по m ящикам так, чтобы каждый и ящик содержал упорядоченную последовательность, а не просто неупорядоченное множество помещенных в него объектов, то будем называть такое размещение упорядоченным размещением т объектов по m ящикам. Их число - обозначим его [m]lnl- равно, полагая (для n = 0) [m]0 = 1: [m][n]=m∙(m+1)∙...∙(m+n-1) = Anm+n-1
Доказательство. Будем строить упорядоченные размещения, добавляя по очереди новые объекты. Первый объект можно разместить m способами, помещая его в любой из пока пустых ящиков. Второй (m + 1) способами, ибо его можно разместить в одном из (m - 1) пустых ящиков или в ящике, содержащем первый объект: перед ним или после него. В общем случае, если в ящике находятся s объектов, то очередной объект можно поместить в этот ящик (s + 1) способами. Поэтому, если перед размещением i-ro объекта в k-ом ящике находятся rk (k = 1, 2,..., m;
=i-1 rk = i -1) объектов, то его можно разместить всего k=i (г1 + 1)+...+ (rm+1) = (r1+...+ rm)+ m = (i-1) + m способами. Тем самым проведен индукционный шаг доказательства.
В таблице 2 представлены [З]2 =3·4=12 упорядоченных: размещений двух элементов a,b в трех ящиках.
Таблица 2
A |
B |
|
A |
|
B |
B |
A |
|
B |
|
A |
A B |
|
|
B A |
|
|
|
A |
B |
|
B |
A |
|
A B |
|
|
B A |
|
|
|
A B |
|
|
B A |