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

1. О чём речь

Комбинаторика — это особый раздел математики, занимающийся вопросами подсчёта количества объектов. Объекты, о которых идёт речь, — конечно же, не яблоки, не землекопы и не что-либо в таком духе. С яблоками ведь, как правило, всё просто: есть 10 ящиков по 20 яблок в каждом, сколько всего? Тут и пятиклассник справится. А если я спрошу, сколько есть способов взять из этих ящиков 40 яблок так, чтобы из каждого ящика было взято хотя бы одно яблоко? Расчёт сразу становится не таким уж простым, и тут на помощь и приходит комбинаторика.

Зачем это нужно? Главным образом для расчёта вероятностей. Ну вот пример. Идёт игра в дурака; были сданы карты, и вы, делая первый ход, думаете: есть ли у вашего противника на руке хотя бы одна козырная карта? Если карты мешались как следует, этого, конечно, невозможно узнать наверняка. Однако шанс, или, говоря научным языком, вероятность того, что козырная карта есть, можно оценить!

В самом деле. В вашей колоде 52 карты; одна из них уже выложена как козырь. Осталась 51 карта, из них 12 козырных (не 13, потому что одна козырная уже лежит отдельно). Из этих карт вы раздаёте шесть случайных себе и шесть случайных противнику. Пусть вам досталось два козыря (вместо двух можно взять сколько угодно — рассуждения останутся в силе, только числа немного поменяются); тогда, перед тем, как вы раздадите карты противнику, у вас в колоде остаётся 45 карт, из которых 10 козырных. И вот это уже комбинаторный вопрос совершенно в духе озвученного ранее: сколько существует способов выбрать шесть карт из 10 козырных и 35 обычных так, чтобы хотя бы одна выбранная была козырной, и сколько существует способов выбрать шесть карт из 45 всего?

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

Прежде чем перейти, собственно, к комбинаторике, я скажу ответ. Число способов выбрать шесть карт из 45 равно 8 145 060 (просто перебором вариантов и не сосчитаешь, а?); число способов выбрать шесть карт, чтобы хоть одна была козырной, равно (в нашем случае) 6 521 900. Итого вероятность того, что у противника есть хотя бы одна козырная карта, равна
(6 521 900) ⁄ (8 145 060)=0.800718472301002… .
Соответственно, в привычных журналистам процентах получаем вероятность около 80%. Можно интерпретировать это как «козырная карта у противника есть почти наверняка».

2. Перестановки

Путь к решению задач с картами мы начнём издалека, с самого простого комбинаторного объекта — перестановки. Название тут говорит само за себя. Чтобы получить всевозможные перестановки некой совокупности объектов, нужно просто по очереди выставлять их в ряд в любом возможном порядке. Разные порядки предметов в ряду и будут перестановками.

В качестве примеров мы возьмём шары для бильярда.

Итак, пусть у нас есть n разных шаров. Сколько существует различных способов поставить их в ряд, то есть составить из них упорядоченный набор?

Обозначим это число способов через P_n и начнём думать. Если шаров ноль, то и число способов будем считать нулевым. Если же шар один, то и способ, ясное дело, тоже один. Запишем это математически, используя введённое нами обозначение: P_1=1.

Если шаров два, то несложно проверить, что и возможных перестановок тоже только две (P_2=2). Но дальше всё, конечно, становится чуть веселее. Так, если шаров три, то возможных перестановок становится шесть:

Яркий жёлтый шар на этой картинке подсказывает нам, как получить всевозможные перестановки трёх шаров, зная всевозможные перестановки двух: взять каждую перестановку двух и «впихнуть» третий шар по очереди в каждую доступную позицию: в начало, в середину и в конец. Каждая перестановка из двух шаров таким образом «породит» три перестановки из трёх шаров, и несложно проверить, что получить одну и ту же перестановку несколько раз этим методом не получится. Значит, число перестановок из трёх шаров в три раза больше числа перестановок из двух: P_3=3⋅ P_2.

Однако, теперь, проведя те же рассуждения, мы можем показать, что это свойство выполняется для любого числа шаров! Пусть шаров n, и число перестановок любых (n−1) из них равно P_{n−1}. Возьмём всевозможные перестановки последних (n−1) шаров (то есть всех, кроме первого) и в каждую из них по очереди «впихнём» первый шар во все возможные позиции: в начало, между первым и вторым, между вторым и третьим и так далее. Несложно посчитать, что таких позиций n: одна в начале, (n−2) между разными соседними шарами и одна в конце. Таким образом мы гарантированно получаем все возможные перестановки, включающие последние (n−1) шаров и наш первый шар (подумайте, почему!), то есть все возможные перестановки. Получается, мы пришли к великому открытию: для числа перестановок P_n справедливо равенство
§cale[1.5]{P_n=n⋅ P_{n−1} .}
(2.1)
Оно справедливо для любого числа предметов n, а значит, и для (n−1):
P_{n−1}=(n−1)⋅ P_{n−2} .
Подставляя эту формулу в предыдущую, получаем
P_n=n⋅(n−1)⋅ P_{n−2} .
Теперь раскроем в этой формуле P_{n−2} и так далее, пока не дойдём до P_1. Мы знаем, что P_1=1; значит, тут можно остановиться. По ходу дела мы домножали ответ на все числа в ряду n, n−1, n−2, …; значит, в итоге число всевозможных перестановок из n предметов в точности равно
P_n=n⋅(n−1)⋅…⋅ 2⋅ 1 .
Это число, равное произведению первых n натуральных чисел, называется факториалом n и обозначается n! .

К получению этой формулы для P_n можно зайти и с другой стороны. Предположим, что мы хотим как-то поставить шары, лежащие в урне, в ряд на полку. Изначально полка пуста, а в урне лежит n шаров. Будем по очереди доставать из урны шар и ставить на полку. На первом шаге у нас есть n разных вариантов, какой шар достать и поставить. На втором шаге шаров в урне осталось (n−1), и вариантов выбора шара тоже (n−1). И так далее; на k-м шаге у нас будет ровно (n−k+1) вариантов действий. Мы последовательно, n раз совершаем некий выбор; наше решение каждый раз не зависит от предыдущих решений — от них зависит только количество вариантов. Понятно, что общее число число возможностей при этом равно произведению числа возможностей при каждом из независимых выборов, то есть в точности
n⋅(n−1)⋅(n−2)⋅…⋅ 2⋅ 1 .
(Заметьте, что последний выбор оказывается «выбором» из одного варианта. Ну ничего страшного, голосование с одним кандидатом, как известно всем, пожившим в Советском Союзе, — тоже голосование.)

Этот вариант рассуждения может показаться несколько умозрительнее, но такие умозрительные рассуждения, как водится, следует проводить с двойной осторожностью. (Особенно внимательно стоит следить за независимостью отдельных решений. Счесть зависимые события независимыми — одна из излюбленнейших ошибок при решении задач по теории вероятности.)

Задача
Каждое утро вожатый выстраивает группу из 20 пионеров в шеренгу случайным образом. Каков шанс трёх закадычных друзей, Пети, Васи и Егора, оказаться рядом в шеренге?

Итак, чтобы найти эту вероятность, нам надо на общее количество вариантов расстановки пионеров поделить число «хороших» вариантов, то есть вариантов, в которых Петя, Вася и Егор оказываются рядом. Общее число перестановок 20 пионеров мы уже знаем — оно равно
20! = 2432902008176640000 ≈ 2,5 квинтиллионов.

Теперь давайте подумаем, как посчитать число «хороших» перестановок. В любой «хорошей» перестановке Петя, Вася и Егор стоят рядом — значит, при пересчёте можно считать их одним большим целым («сверхчеловеком», если хотите!). Число перестановок 17 пионеров и одного сверхпионера (итого 18 субъектов) нам тоже известно — оно равно
18! = 6402373705728000 ≈ 6,5 квадриллионов.
Однако, Петя, Вася и Егор могут при этом размещаться произвольным образом относительно друг друга внутри своей «неделимой группы». Таких возможностей ровно 3!=6. Значит, каждая из найденных 6,5 квадриллионов перестановок может существовать в шести вариантах, и всего «хороших» перестановок пионеров 18!⋅ 3!. Что ж, теперь остаётся прикинуть искомую вероятность:
вероятность =(18!⋅ 3!) ⁄ (20!) = (6) ⁄ (19⋅ 20) ≈ 0.015789473684210527 .
Около 1,6%. Крепитесь, пионеры! (Впрочем, вероятность хоть раз оказаться рядом за 14 дней смены уже почти 20%! Но об этом — в статье о вероятностях.)

Для тренировки абстрактного мышления можете проверить, что для k друзей в группе из n пионеров искомая вероятность равна
((n − k + 1)!⋅ k!) ⁄ (n!)

3. Размещения

Пойдём дальше. (По пути усложнения, разумеется!) Пусть у нас по-прежнему есть n шаров, только теперь мы хотим рассмотреть всевозможные перестановки не из всех них, а из какого-то меньшего количества m: m≤ n. Такие всевозможные перестановки называются размещениями из n предметов по m. Попробуем подсчитать, сколько же их.

Всё становится немного сложнее из-за того, что у нас теперь два числа-параметра m и n, а не одно. Обозначим количество размещений из n по m знаком A_n^m. Очевидно, что если m=1, то есть нужно выбрать один шар из n имеющихся, то A_n^1=n: просто можно выбрать любой шар и остановиться на этом. Если два, то A_n^2=n⋅(n−1): выбираем первый шар из n вариантов, а потом второй из оставшихся (n−1) вариантов. Вооружившись опытом предыдущего параграфа, мы можем сообразить, что так будет продолжаться и дальше: число вариантов будет уменьшаться, эти уменьшающиеся числа будут перемножаться… Соотношение, аналогичное (2.1), будет для числа размещений выглядеть так:
§cale[1.5]{A_n^m=n⋅ A_{n−1}^{m−1} .}
Озвучить эту формулу можно так: «если, желая выбрать размещение m предметов из n имеющихся, я достал один (у меня было n разных способов сделать это), то мне остаётся выбрать размещение (m−1) предмета из (n−1) имеющихся».

Повторив с этой рекуррентной (включающей себя же с меньшими значениями параметров) формулой те же логические действия, что и с предыдущей, приходим к итоговому выражению для числа размещений:
A_n^m=n⋅(n−1)⋅…⋅(n−m+1) .
Она отличается от (2.1) потому, что в данном случае нам пришлось остановиться раньше — ведь m не превосходит n! А с факториалами эта формула записывается ещё лаконичнее:
A_n^m=(n!) ⁄ ((n−m)!)=\frac{ 1⋅ 2⋅…⋅(n−m) ⋅(n−m+1)⋅…⋅ n }{ 1⋅ 2⋅…⋅(n−m)\hphantom{ ⋅(n−m+1)⋅…⋅ n} } .
Эта величина называется убывающим факториалом из n по m и обозначается n^{m̲}.

Как и в предыдущем параграфе, тут возможен другой ход рассуждений. Проведём рассуждение, объясняющее это загадочно возникшее деление факториалов друг на друга. Итак, нам нужны все размещения m предметов из n возможных. Сначала возьмём всевозможные перестановки всех предметов; их, как мы уже знаем, n!. Теперь скажем, что первые m предметов каждой перестановки — это и есть интересующие нас размещения. Всё хорошо, все возможные размещения получены, но они повторяются. В самом деле, достаточно посмотреть на картинку с перестановками шаров в начале соответствующего параграфа. Прикройте рукой третьи шары всех строк, и вы сможете найти две одинаковых строчки, то есть два совпадающих размещения.

К счастью, это не беда. Давайте подсчитаем, сколько раз нам встретилось в нашем методе каждое размещение! Возьмём какое-то одно. В нём m предметов. В правой части, которую мы отбросили, было ещё (n−m) предметов. Понятно, каких — тех, что не попали в первые m. Кроме того, поскольку мы брали всевозможные перестановки, то и эти (m−n) аутсайдеров побывают в отброшенной части, будучи переставленными всеми возможными способами! Таких способов ровно P_{m−n}=(m−n)!, потому что это просто перестановки (m−n) предметов. Значит, каждое размещение встретилось нам повторно ровно (m−n)! раз (независимо от попавших в него предметов!).

Итого, у нас есть n! размещений, среди которых по (m−n)! копий каждого. Значит, для получения «чистого» количества размещений нужно получить общее число полученных на число копий:
A_n^m=(n!) ⁄ ((m−n)!) .

Вот мы заодно и увидели, что в комбинаторике можно не только умножать, но и делить. (Но только очень осторожно.)

В завершение давайте испытаем нашу формулу на практике. Попробуем посчитать число размещений двух шаров из четырёх. Теоретически оно должно быть равно
A_4^2=(4!) ⁄ (2!)=(1⋅ 2⋅ 3⋅ 4) ⁄ (1⋅ 2)=12 .
Сколько же их на деле, нам подскажут бильярдные шары.

4. Сочетания

Заключительный номер базовой программы — сочетания. Будем всевозможными способами выбирать m предметов из n имеющихся, но теперь, в отличие от размещений, без учёта порядка. Каждый такой неупорядоченный набор из m элементов и будет сочетанием.

Обозначим число сочетаний знаком C_n^m и попробуем сразу же его вычислить. Возьмём всевозможные размещения m предметов из n имеющихся. Их, как мы уже знаем, A_n^m=n!⁄(n−m)! . Если перестать обращать внимание на порядок (образно выражаясь, сгрести все ряды в отдельные кучки), то мы, конечно же, получим всевозможные сочетания, но опять-таки они будут повторяться. По старой методике проверим число повторений. В каждой кучке из m элементов можно ввести порядок m! способов (потому что каждый порядок — не что иное, как перестановка!). Значит, каждое сочетание повторяется среди всех размещений ровно m! раз! Для получения числа сочетаний остаётся поделить число размещений на этот факториал:
§cale[1.5]{C_n^m=(A_n^m) ⁄ (m!)=(n!) ⁄ ((n−m)! m!) .}
Эта величина называется биномиальным коэффициентом из n по m и обозначается как \binom{n}{m}.

Кстати, внимательно глядя на формулу, можно заметить, что
\binom{n}{m}=\binom{n}{n−m} .
То есть способов выбрать из n шаров немножко столько же, сколько и способов выбрать почти все. Разумно: ведь выбрать немножко — это всё равно, что выбросить почти все.

В связи с этим обстоятельством наша картинка может в этом параграфе быть гораздо красочнее. Вот всевозможные способы выбрать пять шаров из семи. Их ровно двадцать один, как и способов выбрать два из семи.

А вот сочетаний трёх и четырёх из семи уже тридцать пять. И вообще максимальное число сочетаний достигается при попытке выбрать половину всех предметов (ну или почти половину, если предметов нечётное число).

5. Бином Ньютона

Доказательство бинома Ньютона — традиционная задачка в курсе матанализа, дающая начинающим студентам представление о методе математической индукции. Сам бином выглядит так: если даны два вещественных слагаемых a и b и некая натуральная степень n, то
(a+b)^n = ∑_{k=0}^n \binom{n}{k} a^{n−k} b^k .
(БН)
(Отсюда и берут своё название биномиальные коэффициенты.)

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

Во-первых, давайте посмотрим, что будет, если раскрыть скобки «в лоб». Возьмём n=2:
\begin{array}{cl} (a+b)^2 &=(a+b)(a+b)\\[2mm] &=aa+ab+ba+bb=a^2+2ab+b^2 . \end{array}
Получилась всем известная формула квадрата суммы. Становится видна и главная проблема при раскрытии скобок «в лоб»: многие слагаемые одинаковы и их нужно собрать вместе — привести подобные, то есть подсчитать, сколько копий каждого слагаемого есть в итоговой сумме, и выписать в итоге только разные слагаемые с соответствующими множителями.

Для пущей наглядности выпишем ещё вариант с n=3:
\begin{array}{cl} (a+b)^3 &= (a+b)(a+b)^2 \\[2mm] &= (a+b)(aa+ab+ba+bb)\\[2mm] &\hspace{−0.425em}\begin{array}{cccccccc} =&aaa&+&aab&+&aba&+&abb\\ +&baa&+&bab&+&bba&+&bbb \end{array}\\[4mm] &= a^3 + 3a^2b + 3b^2a + b^3 . \end{array}
Видно также, что все слагаемые имеют вид a^pb^q, где p и q — какие-то целые числа.

Давайте для начала подсчитаем итоговое число слагаемых до приведения подобных. Это довольно тривиально, но всё-таки. Распишем бином следующим образом:
\begin{array}{cl} (a+b)^n &=(a+b)(a+b)^{n−1}\\[2mm] &=a(a+b)^{n−1}+b(a+b)^{n−1} . \end{array}
То есть слагаемых в выражении для n-й степени ровно в два раза больше, чем в выражении для (n−1)-й степени. Что ж, это позволяет нам выписать их число:
\begin{array}{cl} слагаемых (n) &=2⋅слагаемых (n−1)=\\[2mm] &=4⋅слагаемых (n−2)=…=2^n . \end{array}
Все слагаемые имеют вид a^pb^q. А каковы максимальные p и q? Ясно, что p,q≥ 0; ясно также, что p,q≤ n, так как в большей степени числа a и b тут появиться просто не в состоянии. Однако, можно также увидеть, что во всех слагаемых p+q=n. В самом деле: как получается очередное слагамое? Есть n скобок:
(a+b)^n=\underbrace{(a+b)(a+b)…(a+b)}_{n штук}
Из каждой скобки берётся либо a, либо b, и все они перемножаются. Всего скобок n, так что и чисел всего перемножается тоже ровно n. Ну а p и q означают, что мы из p разных скобок взяли число a и из q разных скобок взяли число b. Соответственно, — вуаля! — количество повторений слагаемого a^pb^q зависит от количества способов выбрать из n скобок q раз число b и p=n−q раз число a. А это число способов мы знаем — это не что иное, как число сочетаний q элементов из n имеющихся, равное \binom{n}{q}.

Дальше. Мы знаем, что во всех слагаемых p+q=n (то есть p=n−q), и что 0≤ q≤ n. Какие возможны варианты q? Да любые. В самом деле, пусть мы хотим слагаемое с каким-то конкретным q=q_0, 0≤ q_0≤ n. Возьмём из первых q_0 скобок число b, а из остальных — число a, и перемножим. Будет такое слагаемое в итоговой сумме? Будет. Можно взять b и ноль раз (то есть взять из всех скобок a), и один, и все n (взять из всех скобок b). Что ж, значит, всевозможные наши слагаемые, уже с учётом их повторности, имеют вид
a^{n−q}b^q⋅\binom{n}{q},  q=0,1,2,…,n .
Остаётся их все сложить чудесным значком ∑, чтобы и получить желанный бином Ньютона:
(a+b)^n = ∑_{q=0}^n \binom{n}{q} a^{n−q} b^{q} .
Точно такой же, как и было обещано в формуле (БН). (Аплодисменты.)

Кстати, здесь можно увидеть вот какую штуку. Всего слагаемых было 2^n. Потом мы их сгруппировали, и количество одинаковых слагаемых равнялось биномиальным коэффициентам \binom{n}{q} с разными q. Но если мы всё проделали честно, то сумма всех этих коэффициентов должна дать нам исходное число слагаемых! А значит,
2^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+…+\binom{n}{n−1}+\binom{n}{n} .
Вот так мы попутно ещё и доказали интересную формулу.

6. Указатель

© Aleph, 2014–2016. При использовании материалов ссылка на math.siomax.ru обязательна.
Последняя редакция: , Т. Салуев.