1.9 Комбинаторика

1.9.1 Основные комбинаторные конфигурации

1.9.2 Формулы пересчёта числа комбинаторных конфигураций

1.9.3 Перечисление перестановок

1.9.4 Приложения к теории вероятностей

 

Формулы пересчета числа комбинаторных конфигураций

Число (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.

Примеры

  1. Число слов длины k в алфавите {0, 1 } равно 2k; таково же число всех подмножеств k-элементного множества, поскольку множество однозначно задается своей характеристической функцией. Число k - значных двоичных чисел равно 2k-1 т.к. первая цифра должна равняться 1.
  2. Число 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.

Примеры


    Приведем некоторые свойства биномиальных коэффициентов.
  1. Ckn = Cn-kn.Это следует как из формулы (8), так и из того, что выборка k элементов из n однозначно определяет дополнение: выборку (n - k) оставшихся элементов из n. Отсюда и из предыдущих равенств следуют
    Cnn= Cn0=1, Cnn-1= Cn1=n.
    Например,
    В последнем равенстве в числителе и в знаменателе выделены скобками одинаковые сомножители.
  2. - следует из подстановки х = у = 1 в формулу (7).
1 + 5 + 10 + 10 + 5 + 1 = 32 = 25.
1 + 6 + 15 + 20 + 15 + 6 + 1 = 64 = 26.
  1. - следует из подстановки х = 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).
  2. ∙ k = n ∙ 2n-1 . Чтобы убедиться в справедливости равенства, представим, что для каждого сочетания из n элементов {а1, а2,..., аn} выписаны на отдельную карточку символы аi1,ai2,...,аik, соответствующие элементам этого (k-элементного) сочетания: всего карточек - 2n (по свойству 2). Тогда суммарное число символов на всех карточках можно подсчитать двояко:
    1. Суммарное число символов на Сkn карточках, содержащих ровно k символов, равно k ∙ Сkn ; в левой части рассматриваемого равенства -общее число символов на всех карточках для k = 0, 1,..., n.
    2. Если зачеркнуть некоторый символ а, на всех карточках, на которых он написан, то на них останутся всевозможные сочетания из остальных (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.
  3. С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, выражается через значения этой же функций при других (здесь - меньших) значениях переменных.
    01
    11 1
    21 2 1
    31 3 3 1
    41 4 6 4 1
    51 5 10 10 5 1
    61 5 15 20 15 5 1
    71 7 21 35 35 21 7 1
    81 8 28 56 70 56 28 8 1
    91 9 36 84 126 126 84 36 9 1
    101 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-элементных делегаций такое, как в правой части равенства.
    Пример. С41047+3=-С07+ С4317+ С3327+ С23+ С37∙С1347∙С03 = [учитывая, что С34 = 0] = 7∙1 + 21 ∙ 3 + 35 ∙ 3 + 35 ∙ 1 = 210.
  1. Чтобы получить число (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. Рассмотрим всевозможные размещения с повторениями а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.
  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, НИ один из т адресатов не получит предназначенного ему письма. Может показаться парадоксальным,
  3. Одна из классических задач комбинаторики - определить число способов разместить некоторое множество объектов в каком-то количестве "ящиков" так, чтобы были выполнены заданные ограничения.
    Если даны два множества X, Y, причем X=n, Y=n, то всякая функция f: XY задает такое размещение, если считать 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