Биномиальные коэффициенты и C(n, k) по модулю

Биномиальные коэффициенты: треугольник Паскаля, тождества и главное умение — считать C(n, k) по простому модулю.

Биномиальный коэффициент C(n, k) — число сочетаний из n по k; коэффициент при xk в разложении (1+x)n.

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

Сочетания C(n, k) — самый востребованный объект подсчётных задач, и почти всегда ответ требуют по модулю 10⁹+7. Прямо посчитать C(10⁵, 5·10⁴) нельзя — это число с сотнями тысяч цифр. Но по модулю это делается за O(1) после предподсчёта факториалов и обратных к ним. Этот приём — обязательный навык: на нём держатся задачи про пути, разбиения, вероятности, формулы включения-исключения. Разберём оба пути: маленькие n через треугольник Паскаля и большие n через факториалы по модулю.

Треугольник Паскаля

Главное тождество: C(n, k) = C(n−1, k−1) + C(n−1, k). Интуиция: выбирая k предметов из n, посмотрим на последний предмет. Либо мы его берём — тогда остаётся выбрать k−1 из первых n−1 (это C(n−1,k−1)), либо не берём — выбираем k из n−1 (C(n−1,k)). Случаи не пересекаются — складываем. Это правило суммы в чистом виде, и оно строит знаменитый треугольник.

def pascal(rows):
    triangle = [[1]]
    for _ in range(rows - 1):
        prev = triangle[-1]
        row = [1] + [prev[i] + prev[i + 1] for i in range(len(prev) - 1)] + [1]
        triangle.append(row)
    return triangle

for row in pascal(6):
    print(row)

Вывод:

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

Треугольник даёт все C(n, k) для n до нескольких тысяч за O(n²) — этого хватает, когда n небольшое, а запросов много. Здесь же видно тождество ∑ᵤ C(n,k) = 2n (сумма строки): число всех подмножеств n-элементного множества.

Сочетания по простому модулю через факториалы

Когда n доходит до миллионов, треугольник не помещается. Зато формула C(n,k) = n! / (k! (n−k)!) по простому модулю считается за O(1) после предподсчёта. Идея: деление по модулю — это умножение на обратный, а обратные к факториалам предподсчитываются разом. Алгоритм такой: считаем fact[i] = i! mod p прямым проходом; обратный к самому большому факториалу — по Ферма; остальные обратные факториалы — обратным проходом по тождеству inv_fact[i−1] = inv_fact[i] · i.

MOD = 10**9 + 7
N = 200000

fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = fact[i - 1] * i % MOD

inv_fact = [1] * (N + 1)
inv_fact[N] = pow(fact[N], MOD - 2, MOD)      # обратный по Ферма — один раз
for i in range(N, 0, -1):
    inv_fact[i - 1] = inv_fact[i] * i % MOD   # дешёвый обратный проход

def C(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

print(C(5, 2))                 # 10
print(C(1000, 500))            # огромное число, остаток мал
import math
print(C(40, 20) == math.comb(40, 20) % MOD)  # сверка с точным значением

Вывод:

10
159835829
True

Ключевой трюк — вычислить один обратный по Ферма (для inv_fact[N]) и протянуть остальные обратным проходом: inv_fact[i−1] = inv_fact[i] · i, потому что (i−1)!−1 = i!−1 · i. Так предподсчёт обоих массивов — O(N), а каждый запрос C(n,k) — O(1). Сверка с math.comb по модулю подтверждает корректность.

Сочетания с повторениями

Сочетания с повторениями (метод «звёзд и перегородок»): число способов выбрать k предметов из n типов, допуская повторы, равно C(n + k − 1, k).

Эквивалентная формулировка: сколько неотрицательных целочисленных решений у x₁ + x₂ + … + xₙ = k. Интуиция «звёзд и перегородок»: представим k одинаковых звёздочек в ряд и n−1 перегородку, делящую их на n групп. Любая расстановка задаёт решение (размер группы = значение переменной). Всего объектов k + (n−1), выбираем, где стоят перегородки: C(n+k−1, n−1) = C(n+k−1, k).

import math

def combinations_with_repetition(n, k):
    return math.comb(n + k - 1, k)

# Сколько способов купить 7 мороженых 3 сортов (повторы можно)?
print(combinations_with_repetition(3, 7))   # C(9,7)=36

# проверка перебором: x1+x2+x3 = 7, неотрицательные
count = sum(1 for a in range(8) for b in range(8) for c in range(8)
            if a + b + c == 7)
print(count)

Вывод:

36
36

Разбор задачи: числа Каталана

Биномиальные коэффициенты порождают одну из самых знаменитых последовательностей — числа Каталана: Cₙ = C(2n, n)/(n+1). Они считают невероятно много объектов: правильные скобочные последовательности из n пар, способы триангуляции многоугольника, бинарные деревья из n вершин, пути под диагональю. Появление числа Каталана в задаче — сигнал, что за ней стоит рекурсивная структура. Проверим формулу честным перебором скобочных последовательностей.

import math
from functools import lru_cache

def catalan(n):
    return math.comb(2 * n, n) // (n + 1)

# проверка: число правильных скобочных последовательностей длины 2n
def count_brackets(n):
    @lru_cache(maxsize=None)
    def f(opened, closed):
        if opened == n and closed == n:
            return 1
        total = 0
        if opened < n:
            total += f(opened + 1, closed)        # поставить '('
        if closed < opened:
            total += f(opened, closed + 1)        # поставить ')'
        return total
    return f(0, 0)

print([catalan(n) for n in range(7)])
print([count_brackets(n) for n in range(7)])

Вывод:

[1, 1, 2, 5, 14, 42, 132]
[1, 1, 2, 5, 14, 42, 132]

Формула и перебор дали одну и ту же последовательность 1, 1, 2, 5, 14, 42, 132. По модулю числа Каталана считаются мгновенно через предподсчитанные факториалы: Cₙ = fact[2n] · inv_fact[n] · inv_fact[n+1] (поскольку C(2n,n)/(n+1) = (2n)!/(n!(n+1)!)). Узнавать Каталана в задачах — ценный навык: он экономит вывод сложной рекурренты.

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

• Модуль обязан быть простым. Способ через обратные факториалы работает для простого p (как 10⁹+7). Для составного модуля нужна теорема Люка или иные приёмы.
• k вне диапазона. Всегда обрабатывайте k < 0 и k > n возвратом 0 — иначе словите неверный остаток или выход за массив.
• Размер предподсчёта. Массив должен покрывать максимальный n в запросах (включая n+k−1 для сочетаний с повторениями).
• Не путайте формулы. Без повторов — C(n,k); с повторами — C(n+k−1,k).

Итог

• Тождество Паскаля C(n,k)=C(n−1,k−1)+C(n−1,k) строит треугольник за O(n²) для малых n.
• Для больших n: предподсчёт fact и inv_fact даёт C(n,k) по простому модулю за O(1).
• Трюк: один обратный по Ферма + обратный проход inv_fact[i−1]=inv_fact[i]·i.
• Сочетания с повторениями — C(n+k−1, k) по методу звёзд и перегородок.