Комбинаторика: перестановки, размещения, сочетания

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

Правило умножения: главный принцип счёта#

Если первое действие можно сделать $m$ способами, а второе — $n$ способами, то пару «первое + второе» — $m\cdot n$ способами. Это правило умножения, и оно настолько очевидно, что его стыдно формулировать, пока вы не поймали себя на ошибке против него. Пицца: 3 размера $\times$ 7 начинок $\times$ 4 сыра $=84$ варианта. Никакой магии — просто каждый выбор размера сочетается с каждым выбором начинки.

Рядом живёт правило сложения. Если действие можно выполнить одним из двух непересекающихся способов — так или иначе — то всего способов $m+n$. В кафе есть 4 супа и 5 салатов: выбрать «одно первое блюдо» можно $4+5=9$ способами, а «суп и салат» — $4\cdot 5=20$. Заметьте разницу в формулировках: союз «или» намекает на сложение, союз «и» — на умножение.

Факториал и перестановки#

Сколькими способами можно расставить 6 книг на полке? Первое место — 6 кандидатов, второе — 5, третье — 4, и так до единицы. По правилу умножения: $6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=720$. Такое произведение встречается так часто, что для него придумали отдельный знак — факториал:

Упорядочивание $n$ различных объектов называют перестановками. Число перестановок равно $n!$: объект $P_n=n!$ — это просто «все разложили по местам». Рост факториала чудовищен: $5!=120$, $10!=3628800$, а $20!$ уже больше квадриллиона. Поэтому любой, кто «проверит все варианты» перебором двадцати элементов, будет проверять очень долго.

А если объекты повторяются? Слово «МАМА» из четырёх букв: если бы все буквы были различны, было бы $4!=24$ перестановки. Но две буквы «М» неразличимы — меняя их местами, нового слова не получаем, а таких дублей ровно $2!$. То же с буквами «А». Делим:

Для «МАМА»: $\frac{4!}{2!2!}=6$. Проверьте вручную: МАМА, МААМ, ММАА, АМАМ, АММА, ААММ — ровно шесть. Возьмём слово посложнее — «КОЛОБОК», семь букв: К встречается дважды, О — трижды, Л и Б по одному. Получаем $\frac{7!}{2!3!}=\frac{5040}{12}=420$ различных «слов».

Размещения: порядок важен#

Выбираем $k$ объектов из $n$ различных, и порядок выбора имеет значение — кто первый, кто второй. Такие выборки называются размещениями, их число обозначается $A_n^k$. Логика та же, что с полкой: на первое место $n$ кандидатов, на второе $n-1$, и так $k$ раз:

Забег на 8 финалистов, но медали только три — золото, серебро, бронза. Тройка {Иванов, Петров, Сидоров} и тройка {Петров, Иванов, Сидоров} — это разные исходы, медали-то разные. Значит, считаем размещения: $A_8^3=8\cdot 7\cdot 6=336$. Тот же ответ даёт формула: $\frac{8!}{5!}=\frac{40320}{120}=336$.

Ещё один частый гость задач — четырёхзначный PIN-код из неповторяющихся цифр: $A_{10}^4=10\cdot 9\cdot 8\cdot 7=5040$. Если цифры могут повторяться, вариантов больше — $10^4=10000$: правило умножения с возвращением на каждом шаге.

Сочетания: порядок не важен#

Теперь выбираем $k$ из $n$, но порядок безразличен: делегация из трёх человек — есть делегация, и неважно, кого назвали первым. Это сочетания. Разница с размещениями ровно одна: внутри каждой выбранной тройки можно произвольно переставлять элементы — таких перестановок $k!$, и все они склеиваются в один исход. Делим размещения на $k!$:

Два примера, где сочетания работают безотказно. Рукопожатия: десять знакомых жмут друг другу руки, каждая пара — один раз. Пара не имеет порядка, значит $C_{10}^2=\frac{10\cdot 9}{2}=45$. Лотерея «6 из 45»: угадать шесть номеров из сорока пяти — $C_{45}^6=8145060$ комбинаций. Вот почему джекпот достаётся единицам: вероятность купить выигрышный билет около $1,2\cdot 10^{-7}$.

Свойства сочетаний и бином Ньютона#

У сочетаний есть удобные свойства, которые экономят время. Симметрия: $C_n^k=C_n^{n-k}$ — выбрать 3 из 10 столько же усилий, сколько оставить 7. Правило Паскаля: $C_n^k+C_n^{k+1}=C_{n+1}^{k+1}$ — именно оно рисует знаменитый треугольник Паскаля, где каждое число равно сумме двух над ним.

Главная сцена для сочетаний — бином Ньютона. Раскройте $(a+b{)}^3$ вручную: $a^3+3a^{2}b+3a{b}^2+b^3$. Откуда тройки? Каждое слагаемое — это выбор, в каком из трёх множителей взять $b$: одно $b$ можно разместить $C_3^1=3$ способами, два — $C_3^2=3$. В общем виде:

Подставьте $a=b=1$: получится $2^n={\sum }_{k=0}^n{C}_n^k$ — сумма всех сочетаний равна числу подмножеств конечного множества. Красиво: формула связывает «выборы» и «подмножества», две внешне разные вещи.

Почему это важно для теории вероятностей? В схеме Бернулли вероятность получить ровно $k$ успехов в $n$ испытаниях содержит множитель $C_n^k$ — число способов, на которых успехи могли случиться. Не поладите с сочетаниями — споткнётесь на каждой второй задаче курса. Тренируйтесь на тренажёре задач по комбинаторике: он генерирует упражнения с автоматической проверкой.

Три типичные ошибки

• Порядок важен, а считают $C_n^k$. Классика: «победитель, призёр и участник» — это $A_n^3$, не $C_n^3$.
• Порядок не важен, а считают $A_n^k$. Ответ получается в $k!$ раз больше правильного. Лекарство — вопрос из врезки выше.
• Смешивают «или» и «и». «Суп или салат» — сложение; «суп и салат» — умножение. Прочитайте задачу вслух и подчеркните союзы.

Прогоним комбинаторику через составную задачу — такие открывают контрольные. Из группы, где 10 девушек и 6 юношей, нужно выбрать четверых в совет факультета, среди которых ровно две девушки. Разбиваем выбор на два независимых действия: две девушки из десяти и два юноши из шести. Сочетания: $C_{10}^2=\frac{10\cdot 9}{2}=45$ и $C_6^2=\frac{6\cdot 5}{2}=15$. Каждый женский состав сочетается с каждым мужским, работает правило «и» — умножение: $45\cdot 15=675$ команд.

1. 1
   Случай «ровно две девушки»: $C_{10}^2\cdot C_6^2=45\cdot 15=675$.
2. 2
   Случай «ровно три девушки»: $C_{10}^3\cdot C_6^1=120\cdot 6=720$.
3. 3
   Случай «все четыре девушки»: $C_{10}^4=210$ — юношей не выбираем вовсе.
4. 4
   Складываем: $675+720+210=1605$ советов. Для сравнения: без ограничения всего $C_{16}^4=1820$ вариантов.
5. 5
   Проверка через противоположное: «одна или ноль девушек» — это $C_{10}^1{C}_6^3+C_6^4=10\cdot 20+15=215$, и $1820-215=1605$. Сошлось двумя путями.

• «Ровно» — разбей на случаи; внутри случая умножай (правило «и»), между случаями складывай (правило «или»).
• «Хотя бы» — иди через противоположное: «ноль» считается в одну строку.
• Состав из двух групп — два сочетания и произведение между ними.
• Ответ вышел дробным? В задачах на выбор предметов так не бывает — где-то потерян или лишний множитель.
• Перед сдачей работы — десяток задач в тренажёре по комбинаторике: заодно освежите факториал во всех ролях.