Правило умножения и перестановки

Считаем число способов выбрать и упорядочить объекты — основа всей комбинаторики.

Перестановка — упорядоченное расположение всех $n$ различных объектов; их число равно $n!$.

Чтобы вычислять вероятности по формуле $P=m/n$, надо уметь считать $m$ и $n$. Этим занимается комбинаторика — искусство подсчёта без перечисления. Зачем уметь считать, не перечисляя? Потому что числа исходов в реальных задачах астрономические: способов раздать колоду из 52 карт больше, чем атомов в наблюдаемой Вселенной. Перечислить их физически невозможно, а формула даёт ответ мгновенно. Комбинаторика — это набор приёмов, превращающих вопрос «сколько способов?» в короткое выражение. И поскольку классическая вероятность есть отношение «благоприятных способов» к «всем способам», без комбинаторики мы не сможем посчитать почти ни одной содержательной вероятности. Начнём с фундамента: правила умножения и перестановок.

Правило умножения

Если первый выбор можно сделать $a$ способами, а второй (при любом первом) — $b$ способами, то пару выборов можно сделать $a\cdot b$ способами. Например, обед из 3 супов и 4 вторых блюд даёт $3\cdot 4=12$ комбинаций. Это правило обобщается на любое число шагов и лежит в основе остальных формул.

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

Сколькими способами можно выстроить $n$ различных книг на полке? Первое место — $n$ вариантов, второе — $n-1$ (одна книга уже стоит), и так далее. По правилу умножения получаем

$$n!=n\cdot(n-1)\cdot(n-2)\cdots 2\cdot 1.$$

Это число называют факториалом. По соглашению $0!=1$. Проверим формулу прямым перебором всех перестановок с помощью itertools.permutations.

import math, itertools

for n in range(1, 8):
    items = list(range(n))
    count = sum(1 for _ in itertools.permutations(items))
    print(f"n={n}: перебор={count:>5}, n!={math.factorial(n):>5}")

Вывод:

n=1: перебор=    1, n!=    1
n=2: перебор=    2, n!=    2
n=3: перебор=    6, n!=    6
n=4: перебор=   24, n!=   24
n=5: перебор=  120, n!=  120
n=6: перебор=  720, n!=  720
n=7: перебор= 5040, n!= 5040

Перебор и формула совпадают идеально — здесь нет случайности, мы просто пересчитали все варианты.

Как быстро растёт факториал

Факториал растёт чудовищно быстро: $10!$ уже больше трёх миллионов, а $20!$ превышает $2\cdot 10^{18}$. Поэтому полный перебор перестановок реален лишь для маленьких $n$ — для больших нужна формула, и именно поэтому комбинаторика так ценна.

Случайная перестановка и тасование

Функция random.shuffle равновероятно перемешивает список — каждая из $n!$ перестановок равновозможна. Проверим равномерность на трёх элементах: каждая из $3!=6$ перестановок должна встречаться примерно в $\frac{1}{6}$ случаев.

import random
from collections import Counter
random.seed(0)

cnt = Counter()
for _ in range(600000):
    deck = [1, 2, 3]
    random.shuffle(deck)
    cnt[tuple(deck)] += 1
for perm in sorted(cnt):
    print(perm, round(cnt[perm] / 600000, 4))

Вывод:

(1, 2, 3) 0.1664
(1, 3, 2) 0.1671
(2, 1, 3) 0.1665
(2, 3, 1) 0.1668
(3, 1, 2) 0.1664
(3, 2, 1) 0.1668

Все шесть долей близки к $\frac{1}{6}\approx 0{,}1667$ — тасование действительно равномерно.

Как работает под капотом

Функция itertools.permutations генерирует перестановки лениво, не храня все сразу, поэтому даже большие переборы не съедают память. А random.shuffle реализует алгоритм Фишера—Йетса: он проходит список с конца и меняет каждый элемент со случайным из ещё не обработанных. Можно доказать, что при честном генераторе все $n!$ исходов получаются с равной вероятностью — что мы и увидели в эксперименте.

Частые ошибки

Первая ошибка — забыть, что $0!=1$; это соглашение делает формулы согласованными (пустую полку можно «расставить» ровно одним способом — оставить пустой). Вторая — применять $n!$, когда часть объектов одинакова: перестановки с повторами считаются иначе, через деление на факториалы кратностей. Третья — путать «выбрать и упорядочить все» (перестановки) с «выбрать часть» (размещения и сочетания из следующих уроков).

Итог

• Правило умножения: число способов последовательных выборов перемножается.
• Число перестановок $n$ различных объектов равно $n!$.
• $0!=1$, а факториал растёт быстрее любой степени.
• Тасование Фишера—Йетса даёт равновероятную случайную перестановку.