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

Правила суммы и произведения, перестановки, размещения и сочетания — азбука счёта, без которой не сосчитать ничего.

Правило произведения: если первое действие можно выполнить n способами, а второе (независимо) m способами, то пару действий — n · m способами.

Зачем это в олимпиадах

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

Два правила счёта

Правило суммы: если объект можно выбрать либо из первого набора (n вариантов), либо из второго (m вариантов), и наборы не пересекаются, то всего n + m вариантов. Ключевое слово — «либо…либо» (выбор одного из взаимоисключающих случаев).

Правило произведения: если объект строится из нескольких независимых шагов, число вариантов перемножается. Ключевое слово — «и…и» (последовательность шагов). Например, номер из 3 цифр и 2 букв: 10·10·10 · 33·33 вариантов.

from itertools import product

# Сколько строк длины 2 из алфавита {a, b, c}? Правило произведения: 3*3 = 9
alphabet = "abc"
strings = ["".join(p) for p in product(alphabet, repeat=2)]
print(len(strings))
print(strings)

Вывод:

9
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

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

Перестановка n различных объектов — упорядоченное расположение всех их. Число перестановок равно n! = 1 · 2 · … · n.

Интуиция через правило произведения: на первое место — n кандидатов, на второе — n−1 (один уже занят), …, на последнее — один. Перемножаем: n!. Факториал растёт чудовищно быстро: 20! ≈ 2.4·10¹⁸, поэтому в задачах его берут по модулю.

from itertools import permutations
import math

print(math.factorial(5))                 # 5! = 120
perms = list(permutations([1, 2, 3]))    # все перестановки
print(len(perms))                        # 3! = 6
print(perms)

Вывод:

120
6
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

Размещения

Размещение из n по k — упорядоченный выбор k объектов из n. Их число A(n, k) = n! / (n − k)! = n · (n−1) · … · (n−k+1).

Это «перестановка, но не до конца»: заполняем k позиций, на первую n вариантов, на вторую n−1 и так k множителей. Порядок важен: (1,2) и (2,1) — разные размещения.

import math
from itertools import permutations

def arrangements(n, k):
    return math.perm(n, k)        # n!/(n-k)!

print(arrangements(5, 2))         # 5*4 = 20
# проверим перебором: упорядоченные пары из {0,1,2,3,4}
print(len(list(permutations(range(5), 2))))

Вывод:

20
20

Сочетания

Сочетание из n по k — выбор k объектов из n без учёта порядка. Их число C(n, k) = n! / (k! · (n−k)!).

Связь с размещениями интуитивна: размещений в k! раз больше, потому что каждое неупорядоченное подмножество из k элементов даёт k! упорядоченных. Делим: C(n,k) = A(n,k)/k!. Сочетания — самый частый объект комбинаторики, их также называют биномиальными коэффициентами.

import math
from itertools import combinations

print(math.comb(5, 2))            # 10
print(list(combinations(range(5), 2)))  # неупорядоченные пары
# симметрия: C(n,k) = C(n, n-k)
print(math.comb(10, 3), math.comb(10, 7))

Вывод:

10
[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
120 120

Свойство C(n,k) = C(n,n−k) отражает выбор «кого взять» против «кого не взять» — это одно и то же. В коде Python есть готовые math.factorial, math.perm, math.comb; на олимпиаде по Python ими пользуются напрямую, но понимать вывод формул обязательно.

Разбор типовой задачи: маршруты в сетке

Классика: из левого нижнего угла прямоугольной сетки m×n в правый верхний, двигаясь только вправо и вверх. Сколько путей? Любой путь — это последовательность из m шагов «вправо» и n шагов «вверх», всего m+n шагов. Путь однозначно задаётся выбором, на каких из m+n позиций стоят шаги «вправо». Значит ответ — C(m+n, m).

import math

def grid_paths(m, n):
    return math.comb(m + n, m)

print(grid_paths(2, 2))   # 6 путей в сетке 2x2

# проверим прямым перебором (рекурсия по клеткам)
def count_paths(m, n):
    if m == 0 or n == 0:
        return 1
    return count_paths(m - 1, n) + count_paths(m, n - 1)

print(count_paths(2, 2))
print(grid_paths(10, 10), count_paths(10, 10))

Вывод:

6
6
184756 184756

Формула C(m+n, m) совпала с честным перебором — и считается мгновенно даже для больших сеток, где перебор уже не справится.

Разбор задачи: перестановки с повторами (анаграммы)

Сколько различных «слов» можно составить, переставляя буквы слова MISSISSIPPI? Если бы все 11 букв были разными, ответ — 11!. Но одинаковые буквы неразличимы: перестановки внутри группы одинаковых букв дают то же слово. Поэтому делим 11! на факториалы кратностей каждой буквы. Это формула перестановок мультимножества: n! / (n₁! · n₂! · …).

from math import factorial
from collections import Counter

def multiset_permutations(word):
    counts = Counter(word)
    result = factorial(len(word))
    for c in counts.values():
        result //= factorial(c)
    return result

print(multiset_permutations("MISSISSIPPI"))   # M:1, I:4, S:4, P:2
# проверка на коротком слове перебором
from itertools import permutations
print(multiset_permutations("AAB"), len(set(permutations("AAB"))))

Вывод:

34650
3 3

Для MISSISSIPPI (буквы M:1, I:4, S:4, P:2) получаем 11!/(1!·4!·4!·2!) = 34650 различных анаграмм. Проверка на AAB совпала с честным перебором уникальных перестановок (3). Деление на факториалы кратностей — прямое следствие правила произведения: лишние nᵢ! перестановок одинаковых букв надо «схлопнуть».

Подводные камни

Порядок важен или нет? Главный вопрос комбинаторики. Важен — размещения/перестановки; не важен — сочетания. Перепутать = ответ в k! раз неверный.
Сумма vs произведение. «Либо» → складываем, «и потом» → умножаем. Не смешивайте.
Факториал переполняет. В C++ 20! уже за пределами 64 бит. В Python целые длинные — переполнения нет, но в задачах ответ всё равно берут по модулю.
Граничные значения. C(n, 0) = C(n, n) = 1, C(n, k) = 0 при k > n. Не забывайте обрабатывать.

Итог

Правило суммы — для взаимоисключающих случаев, правило произведения — для независимых шагов.
Перестановки: n!; размещения: A(n,k)=n!/(n−k)!; сочетания: C(n,k)=n!/(k!(n−k)!).
Сочетания не учитывают порядок: C(n,k)=A(n,k)/k! и C(n,k)=C(n,n−k).
Многие задачи (маршруты в сетке) сводятся к одному биномиальному коэффициенту.