Перестановки (permutations) были первым классическим объектом комбинаторики. Сейчас мы рассмотрим два остальных — размещения (allocations) и сочетания (combinations).

Важность этих двух определений различна. Сочетания используются повсеместно. Размещения же нужны почти исключительно для того, чтобы сочетания было удобно определять, они служат удобным переходом от перестановок к сочетаниям.

Пусть задано множество из  n  элементов. Упорядоченный набор, содержащий  m  из этих элементов называется размещением из  n  элементов по  m.

Обозначим множество размещений из  n  элементов по  m  через  A_n^m,  а его мощность через  A_n^m.

И опять те же три вопроса: чему равно  A_n^m,  как перебрать элементы  A_n^m , как их перенумеровать.

Легко видеть, что

     A_n^m = n(n−1). . .(n−m+1) = n! / (n−m)!

имеем  n  возможностей выбора первого элемента,  n−1  возможностей выбора второго и т.д. Получаем m сомножителей, начинающихся с n и уменьшающихся каждый раз на 1. Такой неполный факториал, который обычно делают полным, дописывая необходимые множители в числителе и знаменателе.

Перечислим размещения из 5 элементов по 3. Их число должно быть равно 5·4·3 = 60. Имеем
     abc bac cab dab eab
     abd bad cad dac eac
     abe bae cae dae ead
     acb bca cba dba eba
     acd bcd cbd dbc ebc
     ace bce cbe dbe ebd
     adb bda cda dca eca
     adc bdc cdb dcb ecb
     ade bde cde dce ecd
     aeb bea cea dea eda
     aec bec ceb deb edb
     aed bed ced dec edc

Перечисляемые тройки выписаны по столбцам. Как и раньше, мы стараемся менять прежде всего последний элемент, если это невозможно то меняем предыдущмй и снова перебираем все возможности последнего, и т. д.

Если сгруппировать эти размещения в группы с одинаковым составом, мы получим 10 строк по 6 элементов (это скоро понадобится)

     abc acb bac bca cab cba
     abd adb bad bda dab dba
     abe aeb bae bea eab eba
     acd adc cad cda dac dca
     ace aec cae cea eac eca
     ade aed dae dea ead eda
     bcd bdc cbd cdb dbc dcb
     bce bec cbe ceb ebc ecb
     bde bed dbe deb ebd edb
     cde ced dce dec ecd edc

Для нумерования размещений, подобно случаю перестановок, мы отобразим множество  A_n^m  взаимнооднозначно (построим биекцию) в другое множество  T_n^m,  на котором ввести нумерацию будет гораздо проще, а затем для любого элемента α О  A_n^m  в качестве его номера возьмем номер его образа в  T_n^m.

Множество  T_n^m  — это прямое произведение нескольких числовых отрезков

   T_n^m = 0:(n−1) ´ 0:(n−2) ´ … ´ 0:(n−m+1).

Таким образом, каждый элемент  T_n^m — это набор неотрицательных чисел i₁, i₂, …, i_m−1, i_m,  причем  i_k £ n−k.

Обратите внимание, насколько малы отклонения этого текста от текста для перестановок.

Пусть задано множество из  n  элементов. Неупорядоченный набор, состоящий из  m  этих элементов называется сочетанием из  n  элементов по  m.

Определение отличается от определения для размещений всего одним словом: неупорядоченный.

Обозначим множество сочетаний из  n  элементов по  m  через  C_n^m , а его мощность через  C_n^m.

И еще раз три вопроса: чему равно  C_n^m,  как перебрать элементы  C_n^m,  как их перенумеровать.

Легко видеть связь между  C_n^m  и  A_n^m:

C_n^m = A_n^m / m! = n! / (m!(n−m)!)

Вспомним вторую таблицу в примере: в каждой строке  m!  элементов-размещений, и каждая строка представляет одно сочетание, записанное во всех возможных упорядочениях.

Лексикографический перебор сочетаний можно выполнять по-разному.

Один путь — устроить что-то вроде переборов 0-1-наборов или преребора перестановок в лексикографическом порядке: взять начальный набор индексов от  0  до  m−1  и на каждом шаге стремиться увеличивать самый правый из последних индексов. Оставим разработку деталей такого подхода слушателям.

А подробнее рассмотрим другой способ, с другой формой представления сочетаний.

Каждое сочетание — это подмножество мощности  m  в множестве
из  n  элементов. Если вспомнить о представлении подмножества характеристическим вектором, мы придем к тому, что сочетание задается набором, в котором ровно  m  единиц и  n−m  нулей. Значит нужно научиться перебирать такие наборы.
В лексикографическом порядке!

Самый младший набор — тот, в котором идут сначала все нули, а потом все единицы. Самое выгодное увеличение набора — это сдвиг на одну позицию вправо самого правого из нулей, которые еще можно сдвигать, и «подтаскивание» к нему всех находящихся справа нулей. Полезен пример.

Пусть  n = 7  и  m = 5.
     0011111 1010111 1101110
     0101111 1011011 1110011
     0110111 1011101 1110101
     0111011 1011110 1110110
     0111101 1100111 1111001
     0111110 1101011 1111010
     1001111 1101101 1111100

Красным выделены нули, сдвигаемые на позицию вправо. Опишите сами этот алгоритм в терминах позиций, занятых единицами, и в терминах позиций, занятых нулями.

Итак, каждое сочетание из  n  по  m  — это набор из  m  единиц и  n−m  нулей. А, как говорилось раньше, каждый такой набор изображается путем на прямоугольной решетки из точки  (0, 0)  в точку  (m, n−m).  Так что число таких путей равно  C_n^m.

Вместе с тем, все пути, приходящие в точку  (m, n−m),  идут через  (m−1, n−m)  или через  (m, n−m−1).  Отсюда следует, что

     C_n^m = C_n−1^m−1 + C_{n −1}^m.

Эту формулу можно получить и непосредственным вычислением. Попробуйте.

Обычно формулу для  C_n^m  доопределяют для отрицательных  m,  полагая  C_n^m = 0.

Перенумеровать сочетания — это значит перенумеровать пути, о которых говорилось только что. Будем нумеровать сначала пути, идущие через точку  (0, 1),  а затем пути, идущие через точку  (1, 0).

Пути из  (0, 1)  в  (m, n−m−1)  нумеруются как пути из  (0, 0)  в  (m, n−m−1).  Пути из  (1, 0)  в  (m, n−m−1)  нумеруются как пути из  (0, 0)  в  (m−1, n−m)  с добавлением смещения нумерации на  C_n−1^m−1  уже использованных номеров.

Пример.

Биномиальные коэффициенты очень красиво располагаются треугольником, в котором каждое число (кроме первого) является суммой двух предшествующих. Этот треугольник называется треугольником Паскаля (Blaise Pascal, 1623-1662).
14 11 33 27 29 41 15 26 32 1
14 11 33 27 29 41 15 26 1 54 1
14 11 33 27 29 41 15 1 32 2 87 1
14 11 33 27 29 41 1 26 3 954 3 83 1
14 11 33 27 29 1 15 4 732 6 987 4 15 1
14 11 33 27 1 41 5 26 10 54 10 983 5 77 1
14 11 33 1 29 6 15 15 32 20 87 15 15 6 91 1
14 11 1 27 7 41 21 26 35 54 35 83 21 77 7 16 1 44 23 35 37 38 12 20 29

Недавно стал, если не известен, то популярен, тот факт, что в треугольнике Паскаля суммы элементов по линиям, проведенным наискось, образуют так называемые числа Фибоначчи (Leonardo Pisano Fibonacci, 1170-1250): 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 и т. д.: каждое следующее равно сумме двух предыдущих.

1. При a = b =1 формула бинома превращается в формулу

     2ⁿ = Σ_{k ∈ 0:n} C_n^k.

Интересна геометрическая трактовка этого факта: при проекции вершин n-мерного куба на его диагональ, все вершины распределяются по группам, и количество вершин в каждой равно некоему биномиальному коэффициенту.

2. При a = 1, b = −1 формула бинома превращается в формулу

     C_n⁰ − C_n¹ + C_n² − . . . = 0.

Некоторые другие замечательные формулы можно получить, используя формулу де Муавра (Abraham De Moivre, 1667-1754), французского ученого, жившего в Лондоне (сбежавшего из Франции из-за религиозных преследований) и близко знавшего Ньютона.

В одной книге я прочел такую историю: в конце жизни Муавр решил, что будет каждый день спать на 10 минут дольше, и так и сделал. Когда он проспал целые сутки подряд, он умер, поступив как настоящий математик.

1. В обычном дверном кодовом замке 10 кнопок, из которых нужно нажать три. Сколько возможно комбинаций кодирования этого замка?
   
   
2. Как должна выглядеть аналог формулы бинома для  (a+b+c)ⁿ  и для  (a+b+c+d)ⁿ ?