Комбинаторика для олимпиад

Сколько способов выбрать, расставить, разбить? Считаем перестановки и сочетания и учимся вычислять C(n, k) по модулю за O(1).

Сочетание C(n, k) — число способов выбрать k элементов из n без учёта порядка; это центральная величина комбинаторики, она же биномиальный коэффициент.

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

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

Три базовые формулы

Главное различие — учитывается ли порядок. «Расставить 3 книги на полке» — это перестановки (порядок важен). «Выбрать 3 человека в команду» — это сочетания (кто за кем выбран, неважно).

Треугольник Паскаля: C(n, k) для малых n

Когда n невелико, удобна рекуррентная формула C(n, k) = C(n−1, k−1) + C(n−1, k) — это ДП! Каждое число — сумма двух над ним. Так строится треугольник Паскаля.

N = 6
C = [[0] * (N + 1) for _ in range(N + 1)]
for n in range(N + 1):
    C[n][0] = 1                       # C(n, 0) = 1
    for k in range(1, n + 1):
        C[n][k] = C[n - 1][k - 1] + C[n - 1][k]   # правило Паскаля

for n in range(N + 1):
    print([C[n][k] for k in range(n + 1)])

Каждая строка — коэффициенты разложения (a+b)^n. Этот способ — O(N^2) по времени и памяти; он хорош при N до нескольких тысяч и не требует деления (а значит, и обратных элементов).

Вывод:

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]

C(n, k) по модулю за O(1): предподсчёт факториалов

Для больших n (до 10^6) треугольник Паскаля не помещается в память. Тогда применяют формулу C(n,k) = n! · (k!)⁻¹ · ((n−k)!)⁻¹ по модулю. Предварительно считаем все факториалы, а деление на факториалы заменяем умножением на их обратные элементы (привет, прошлый урок!). После предподсчёта каждый C(n, k) — это O(1) (или O(log), если считать обратный на лету).

MOD = 1_000_000_007
N = 100
fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = fact[i - 1] * i % MOD       # факториалы по модулю

def power(b, e, m):
    r = 1; b %= m
    while e:
        if e & 1: r = r * b % m
        b = b * b % m; e >>= 1
    return r

def C(n, k):
    if k < 0 or k > n:
        return 0
    # n! / (k! (n-k)!) = n! * inv(k!) * inv((n-k)!)
    return fact[n] * power(fact[k], MOD - 2, MOD) % MOD \
                   * power(fact[n - k], MOD - 2, MOD) % MOD

print("C(5, 2)        =", C(5, 2))
print("C(10, 3)       =", C(10, 3))
print("C(50, 25) modp =", C(50, 25))

Здесь power(fact[k], MOD-2, MOD) — это обратный элемент к k! по малой теореме Ферма. Проверим: C(5,2) = 10 (выбрать 2 из 5), C(10,3) = 120 — совпадает с прямым подсчётом. А C(50,25) — огромное число, которое мы видим уже «свёрнутым» по модулю. Для частых запросов обратные факториалы тоже предподсчитывают, и тогда каждый C — честный O(1).

Вывод:

C(5, 2)        = 10
C(10, 3)       = 120
C(50, 25) modp = 605552882

Полезные комбинаторные факты

• Симметрия: C(n, k) = C(n, n−k) — выбрать k «за столом» то же, что выбрать n−k «не за столом».
• Сумма строки: C(n,0) + C(n,1) + ... + C(n,n) = 2^n — число всех подмножеств.
• Путь по сетке: число путей из угла в угол сетки a×b (только вправо/вниз) = C(a+b, a).
• Сочетания с повторениями: выбрать k из n типов с повторами = C(n+k−1, k).

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

• Порядок: сочетания или размещения? Самая частая ошибка — спутать «важен ли порядок». Перечитай условие.
• Деление по модулю — только через обратный элемент; обычное деление даёт неверный ответ.
• Граничные k. Возвращай 0 при k < 0 или k > n, иначе выйдешь за массив факториалов.
• Выбор метода. Малые n — треугольник Паскаля (без деления); большие n — факториалы с обратными по модулю.

Итог

• Перестановки (n!) и размещения учитывают порядок; сочетания C(n,k) — нет.
• Малые n: треугольник Паскаля по правилу C(n,k)=C(n−1,k−1)+C(n−1,k) за O(N^2), без деления.
• Большие n: предподсчёт факториалов + обратные элементы дают C(n,k) по модулю быстро.
• Помни симметрию C(n,k)=C(n,n−k) и связь с путями по сетке и подмножествами.