Перестановки, размещения и сочетания

Три кита комбинаторного счёта: перестановки, размещения и сочетания — и как не путать их между собой.

Сочетание — выбор k элементов из n без учёта порядка; размещение — выбор k из n с учётом порядка.

Зачем это нужно

«Сколько способов раздать колоду?», «Сколько вариантов выбрать команду из 5 человек?», «Сколько различных PIN-кодов?» — это задачи на перестановки, размещения и сочетания. Они лежат в основе анализа алгоритмов (число перестановок — это нижняя оценка для сортировки сравнениями), теории вероятностей, криптографии. Главное здесь — научиться задавать правильный вопрос: важен ли порядок? От ответа зависит формула.

Перестановки: расставить все

Перестановка n различных элементов — это способ расставить их по порядку. Сколько таких способов? На первое место — n кандидатов, на второе — оставшиеся n−1, и так далее. По правилу произведения: n · (n−1) · ... · 1 = n! (n факториал).

P(n) = n!

Например, 5 книг на полке можно расставить 5! = 120 способами. Факториал растёт чудовищно быстро: 10! ≈ 3.6 млн, 20! ≈ 2.4·10¹⁸. Поэтому «перебрать все перестановки» — почти всегда плохой алгоритм для больших n.

Размещения: выбрать и расставить часть

Размещение из n по k — это выбор k элементов из n с учётом порядка. На первое место — n вариантов, на второе — n−1, ..., на k-е — n−k+1. Перемножаем k множителей:

A(n, k) = n · (n−1) · ... · (n−k+1) = n! / (n−k)!

Пример: распределить золото, серебро и бронзу среди 8 спортсменов. Порядок важен (золото ≠ серебро): A(8, 3) = 8·7·6 = 336. PIN-код из 4 разных цифр — тоже размещение: A(10, 4).

Сочетания: выбрать часть, порядок не важен

Сочетание из n по k — выбор k элементов из n без учёта порядка. Команда из 3 человек — это сочетание: неважно, в каком порядке мы их назвали. Формула получается из размещений делением на «лишние» перестановки внутри выбранной группы (их k!):

C(n, k) = A(n, k) / k! = n! / (k! · (n−k)!)

Эту величину называют биномиальным коэффициентом и обозначают C(n, k) или «n по k». Пример: выбрать 3 человек из 8 в команду (порядок не важен): C(8, 3) = 56. Сравни с размещениями A(8,3) = 336 — ровно в 3! = 6 раз больше, потому что каждую тройку можно упорядочить шестью способами.

Главный вопрос: важен ли порядок?

Ситуация	Порядок	Что считаем	Формула
Расставить всех n	важен	перестановки	`n!`
Выбрать k и расставить	важен	размещения	`n!/(n−k)!`
Выбрать k (просто группу)	не важен	сочетания	`n!/(k!(n−k)!)`

Проверяем формулы перебором

Для маленьких n можно перебрать все варианты функциями itertools и сверить с формулами из math. Это лучший способ убедиться, что вы взяли правильную формулу.

from itertools import permutations, combinations
import math

n, k = 5, 2

# Перестановки всех n элементов: n!
print("P(5) = 5! =", math.factorial(5))

# Размещения A(5,2): выбор 2 из 5 с учётом порядка
A = math.factorial(n) // math.factorial(n - k)
print("A(5,2) =", A, "| перебор:", len(list(permutations(range(n), k))))

# Сочетания C(5,2): выбор 2 из 5 без учёта порядка
C = math.comb(n, k)
print("C(5,2) =", C, "| перебор:", len(list(combinations(range(n), k))))

# Связь: A(n,k) = C(n,k) * k!
print("Проверка A = C * k!:", A == C * math.factorial(k))

Вывод:

P(5) = 5! = 120
A(5,2) = 20 | перебор: 20
C(5,2) = 10 | перебор: 10
Проверка A = C * k!: True

Перебор и формулы совпали до последнего: размещений 20, сочетаний 10, и связь A = C · k! подтвердилась. Видишь логику? Размещений ровно вдвое больше сочетаний, потому что каждую пару можно упорядочить 2! = 2 способами. itertools.permutations учитывает порядок, combinations — нет: это код-эквивалент нашего главного вопроса.

Полезные свойства сочетаний

Симметрия: C(n, k) = C(n, n−k). Выбрать k «в команду» — то же, что выбрать n−k «в запас». Например, C(8, 3) = C(8, 5) = 56.
Крайние случаи: C(n, 0) = C(n, n) = 1 (пустую группу и всю группу выбрать можно единственным способом).
Сумма всех: C(n,0) + C(n,1) + ... + C(n,n) = 2^n — это все подмножества n-элементного множества (привет, булеан!).

Комбинаторный взрыв: почему перебор — не всегда выход

Правило произведения объясняет, откуда в алгоритмах берётся «комбинаторный взрыв». Если задача состоит из k независимых выборов по m вариантов каждый, полный перебор делает m^k шагов — число, растущее устрашающе быстро. Это прямое следствие правила произведения, и оно определяет, какие задачи решаются «в лоб», а какие нет.

Классический пример — задача коммивояжёра: объехать n городов кратчайшим маршрутом. Маршрутов (n−1)! — для 10 городов это уже 362 880, для 15 — больше 87 миллиардов, для 20 — астрономические 10^17. Никакой компьютер не переберёт их все. Поэтому комбинаторика — это не только «как посчитать варианты», но и трезвая оценка «реально ли их перебрать». Когда вариантов экспоненциально много, нужны умные алгоритмы (жадные, динамическое программирование, эвристики), а не грубая сила. Умение прикинуть число вариантов до написания кода спасает от программ, которые «зависнут на сто лет».

Перестановки с повторениями: анаграммы слова

А что, если среди элементов есть одинаковые? Сколько различных «слов» (анаграмм) можно составить из букв слова «МАМА»? Наивно — 4! = 24, но буквы повторяются: две «М» и две «А» неразличимы между собой, поэтому многие перестановки совпадают. Правильная формула делит 4! на факториалы количеств каждой повторяющейся буквы: 4! / (2! · 2!) = 6.

import math
from collections import Counter
from itertools import permutations

word = "МАМА"
counts = Counter(word)              # {'М': 2, 'А': 2}
total = math.factorial(len(word))
for c in counts.values():
    total //= math.factorial(c)     # делим на факториалы повторов

print("Различных анаграмм по формуле:", total)
print("Проверка перебором:", len(set(permutations(word))))

Вывод:

Различных анаграмм по формуле: 6
Проверка перебором: 6

Формула и перебор согласны: всего 6 различных анаграмм. Этот случай называют перестановками с повторениями, и формула n! / (k₁! · k₂! · ...) постоянно встречается — от подсчёта маршрутов на решётке до задач о расстановке одинаковых объектов. Деление на факториалы повторов — тот же приём «убрать переучёт», что и при переходе от размещений к сочетаниям.

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

Путать размещения и сочетания. Главный вопрос — «важен ли порядок?». Призовые места — важен (размещения). Состав команды — не важен (сочетания).
Считать пароли как сочетания. В пароле/PIN порядок важен, и символы могут повторяться — это вообще правило произведения (k^n при повторах), а не сочетания.
Забывать про симметрию. Считать C(100, 98) «в лоб» тяжело, а через C(100, 2) — мгновенно. Это одно и то же число.

Итог

Перестановки: расставить все n элементов — n!.
Размещения: выбрать k из n с учётом порядка — n!/(n−k)!.
Сочетания: выбрать k из n без учёта порядка — n!/(k!(n−k)!).
Ключевой вопрос — важен ли порядок; A(n,k) = C(n,k)·k!.