Дискретная математика и комбинаторика

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

Вопрос кажется школьным, пока не выясняется, что за ним прячутся:

• сколько тестов нужно, чтобы покрыть все парные комбинации параметров конфигурации;
• сколько строк вернёт запрос — от этого зависит, выберет ли планировщик hash join или nested loop;
• сколько попыток нужно для поиска коллизии SHA-256 (и почему 2^128, а не 2^256);
• сколько глобальных состояний у распределённого протокола и хватит ли памяти model checker’у;
• сколько различных деревьев разбора допускает грамматика.

Все они решаются одним набором приёмов. Статья опирается на язык множеств из статьи Теория множеств и на аппарат индукции из статьи Математическая логика и доказательства.

1. Карта территории

Комбинаторика тут фундамент: без неё не оценить ни число графов, ни размер пространства ключей, ни стоимость перебора. Небольшая историческая канва, чтобы понимать имена в формулах:

2. Три идеи, из которых растёт всё остальное

Правило суммы. Если объект выбирается либо из A, либо из B и множества не пересекаются, способов ровно |A| + |B|. Для попарно непересекающихся A1..An:

|A1 ∪ A2 ∪ ... ∪ An| = |A1| + |A2| + ... + |An|

Слово «непересекающихся» — не формальность, а точка, где ломается большинство неверных решений. Когда пересечение есть, правило суммы превращается в формулу включений-исключений (раздел 6).

Правило произведения. Если объект строится последовательностью выборов и на шаге i есть ровно k_i вариантов независимо от предыдущих решений, всего объектов k_1 * k_2 * ... * k_n. Интуиция — дерево решений: ветвление на каждом уровне перемножается.

Биекция — самый мощный приём: не формула, а перекодировка. Если между трудно считаемым X и легко считаемым Y есть биекция, то |X| = |Y|. Классика: подмножеств n-элементного множества столько же, сколько двоичных строк длины n, то есть 2^n — никаких сумм биномиальных коэффициентов. Программисту идея знакома как «поменять представление»: битовая маска вместо множества, индекс вместо объекта, канонизация вместо сравнения.

Ниже — рабочая шпаргалка по выбору схемы счёта; каждую ветвь разберём отдельно.

3. Четыре базовые схемы выборки

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

* * | | * * * | *      ->  ящики: 2, 0, 3, 1

import math
from itertools import product, permutations, combinations, combinations_with_replacement

n, k = 5, 3
# Проверка формул брутфорсом — лучший способ не перепутать схему.
assert len(list(product(range(n), repeat=k))) == n**k
assert len(list(permutations(range(n), k))) == math.perm(n, k)
assert len(list(combinations(range(n), k))) == math.comb(n, k)
assert len(list(combinations_with_replacement(range(n), k))) == math.comb(n + k - 1, k)
print(n**k, math.perm(n, k), math.comb(n, k), math.comb(n + k - 1, k))  # 125 60 10 35

math.comb/math.perm (Python 3.8+) считают точно в целых числах, без промежуточного переполнения — см. документацию math; itertools даёт ленивые генераторы всех четырёх схем. Правило гигиены: прежде чем доверять выведенной формуле, прогоняйте её против перебора на n = 0..6 — три минуты работы ловят почти все ошибки вида «забыл поделить на k!».

Мультиномиальный коэффициент. Сколько различных перестановок у слова «АБРАКАДАБРА» (А×5, Б×2, Р×2, К, Д)? Считаем все 11! перестановок, как если бы буквы различались, и делим на внутренние перестановки каждой группы, ничего не меняющие:

n! / (k1! * k2! * ... * km!)   ->   11!/(5!·2!·2!·1!·1!) = 83160

Это приём «пересчитал — подели» (overcounting and dividing), и он же объясняет, откуда в C(n,k) берётся деление на k!.

4. Биномиальные коэффициенты

C(n,k) — число k-элементных подмножеств n-элементного множества, самая частая величина прикладной комбинаторики. Формулу n!/(k!(n-k)!) легко запомнить и трудно применять; держать в голове полезнее комбинаторный смысл — тогда тождества доказываются без алгебры.

Правило Паскаля: C(n,k) = C(n-1,k-1) + C(n-1,k). Доказательство в строку: зафиксируем элемент x; подмножества размера k делятся на содержащие x (остальные k-1 берём из n-1) и не содержащие (k из n-1). Правило суммы — и всё.

Геометрическая интерпретация — монотонные пути на решётке. Путь из начала координат в узел (i, j) шагами «вправо/вверх» — это последовательность из i+j шагов, где надо выбрать, какие i будут «вправо»; значит, путей C(i+j, i). Число путей в узел равно сумме путей в соседей слева и снизу — то самое правило Паскаля.

Бином Ньютона:        (x + y)^n = сумма по k: C(n,k) * x^k * y^(n-k)
Сумма строки:         сумма по k: C(n,k) = 2^n           (все подмножества)
Знакопеременная:      сумма по k: (-1)^k * C(n,k) = 0    (при n >= 1)
Симметрия:            C(n,k) = C(n, n-k)
Поглощение:           k * C(n,k) = n * C(n-1, k-1)
Хоккейная клюшка:     сумма по i от k до n: C(i,k) = C(n+1, k+1)
Свёртка Вандермонда:  сумма по k: C(m,k) * C(n, r-k) = C(m+n, r)

«Хоккейная клюшка» даёт число троек i < j < k и постоянно всплывает при подсчёте операций во вложенных циклах. Вандермонд — это «выбираем r человек из двух групп, перебирая, сколько взяли из первой».

Как считать в коде. Наивное factorial(n)//(factorial(k)*factorial(n-k)) работает в Python, но в C/C++/Go/Java 64-битный n! переполняется уже при n = 21 — задолго до переполнения самого ответа.

def comb_iterative(n: int, k: int) -> int:
    """C(n,k) без больших промежуточных чисел. O(k) времени, O(1) памяти.

    На i-м шаге result * (n-k+i) гарантированно делится на i нацело,
    поэтому целочисленное деление не теряет точность.
    """
    if k < 0 or k > n:
        return 0
    k = min(k, n - k)                     # симметрия уменьшает число итераций
    result = 1
    for i in range(1, k + 1):
        result = result * (n - k + i) // i
    return result

from math import lgamma
def log_comb(n: int, k: int) -> float:
    """ln C(n,k) — не переполняется даже при n = 10**9."""
    return lgamma(n + 1) - lgamma(k + 1) - lgamma(n - k + 1)

print(comb_iterative(52, 5))   # 2598960 — число покерных рук
print(log_comb(1000, 500))     # 689.47; само C(1000,500) имеет 300 цифр

В задачах по модулю простого p используют предвычисленные факториалы и обратные элементы по малой теореме Ферма (pow(a, p-2, p)): предподсчёт O(N), запрос O(1). Обратные элементы живут в теории групп — см. Абстрактная алгебра. Про потерю точности в вещественных вычислениях подробнее в статье Численные методы.

5. Шары и ящики: «двенадцатеричный путь»

Огромная доля задач сводится к схеме «разложить n шаров по k ящикам». Ответ зависит от трёх признаков: различимы ли шары, различимы ли ящики и какое ограничение наложено (любое / инъекция — не более одного шара / сюръекция — ни один ящик не пуст). Ричард Стэнли назвал получившиеся 12 клеток twelvefold way (Enumerative Combinatorics, vol. 1).

S(n,k) — числа Стирлинга второго рода: число разбиений n различимых объектов на k непустых неразличимых блоков. Рекуррентность строится тем же приёмом «зафиксируй элемент»:

S(n,k) = k * S(n-1,k)  +  S(n-1,k-1)
         кладём n-й в     n-й образует
         один из k блоков  новый блок

from functools import lru_cache

@lru_cache(maxsize=None)
def stirling2(n: int, k: int) -> int:
    """Числа Стирлинга 2-го рода. O(n*k) времени и памяти."""
    if n == k:
        return 1
    if n == 0 or k == 0:
        return 0
    return k * stirling2(n - 1, k) + stirling2(n - 1, k - 1)

def bell(n: int) -> int:                 # число всех разбиений множества
    return sum(stirling2(n, k) for k in range(n + 1))

print([bell(i) for i in range(8)])       # [1, 1, 2, 5, 15, 52, 203, 877]
print(stirling2(10, 3), bell(20))        # 9330 51724158235372

B(20) ≈ 5.2e13 — вот почему «переберём все способы сгруппировать 20 сущностей» не является планом. Где это встречается: число способов разбить сервисы на bounded-контексты, число кластеризаций n точек (отсюда NP-трудность кластеризации и эвристичность k-means), число группировок колонок в составные индексы. Любую полученную целочисленную последовательность стоит проверить на OEIS — по первым 5–6 членам найдётся формула и литература.

6. Формула включений-исключений

Когда множества пересекаются, складываем, вычитаем перепосчитанное, возвращаем вычтенное лишний раз — со знакочередованием:

|A ∪ B| = |A| + |B| − |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

Общий вид: |A1 ∪ ... ∪ An| = сумма по непустым подмножествам S индексов
                             (−1)^(|S|+1) * |пересечение A_i, i из S|

Почему знаки такие: элемент, попадающий ровно в m множеств, учтён C(m,1) − C(m,2) + C(m,3) − ... раз, а это по знакопеременному тождеству равно 1 − (1−1)^m = 1. Каждый элемент объединения посчитан ровно один раз.

from itertools import combinations
from math import lcm

def count_divisible_by_none(limit: int, divisors: list[int]) -> int:
    """Сколько чисел 1..limit не делятся ни на один делитель из списка.
    O(2^m * m), где m = len(divisors) — экспонента по числу множеств."""
    total = limit
    for size in range(1, len(divisors) + 1):
        sign = -1 if size % 2 else 1
        for subset in combinations(divisors, size):
            total += sign * (limit // lcm(*subset))
    return total

print(count_divisible_by_none(100, [2, 3, 5]))   # 26, то есть |A∪B∪C| = 74

Это решето Эратосфена, записанное формулой, и частный случай обращения Мёбиуса; функция Эйлера phi(n) получается тем же приёмом по простым делителям. Отсюда же число сюръекций:

Surj(n,k) = сумма по j от 0 до k: (−1)^j * C(k,j) * (k−j)^n = k! * S(n,k)

Прикладной смысл: Surj(n,k) / k^n — вероятность, что при раскидывании n запросов по k воркерам ни один воркер не простаивает.

Trade-off. Формула точна, но стоит O(2^m); при m > 25 она неприменима, и в проде её заменяют вероятностными скетчами: HyperLogLog оценивает мощность объединения за килобайты памяти с ошибкой около 2 % (Flajolet et al., 2007), MinHash оценивает коэффициент Жаккара, а неравенства Бонферрони дают гарантированные границы при обрыве ряда (нечётное число слагаемых — оценка сверху, чётное — снизу). Ловушка: считать |A ∪ B| как |A| + |B| − оценка(|A∩B|) на скетчах нельзя — вычитание близких больших чисел убивает относительную точность. Поэтому HyperLogLog объединяет регистры напрямую.

7. Принцип Дирихле и парадокс дней рождений

Принцип Дирихле: если n+1 предметов разложить по n ящикам, где-то окажется два. Обобщённо — найдётся ящик с не менее чем ceil(n/k) предметами. Утверждение тривиально, следствия фундаментальны:

• Хеш-коллизии неизбежны. Функция из бесконечного множества строк в 64-битные хеши обязана склеивать; вопрос лишь в том, как быстро злоумышленник найдёт коллизию.
• Универсального сжатия не существует. Биекции из {0,1}^n в {0,1}^(n-1) нет, значит любой компрессор, укорачивающий часть файлов, обязан удлинять другие.
• Конфликт-промахи в кеше. При ассоциативности w найдутся w+1 горячих адреса в одном set, гарантированно вытесняющие друг друга.

Практически важнее вероятностная версия: коллизия появляется не после N попыток, а уже после ~sqrt(N).

P(нет коллизий среди k значений из N) = произведение по i от 0 до k-1: (1 − i/N)
                                      ≈ exp(−k(k−1) / (2N))
Порог 50 %: k ≈ 1.177 * sqrt(N)

import math

def birthday_collision_prob(k: int, N: int) -> float:
    """Вероятность хотя бы одной коллизии при k случайных значениях из N вариантов."""
    if k > N:
        return 1.0
    # В логарифмах: прямое произведение теряет точность при больших k.
    return 1.0 - math.exp(sum(math.log1p(-i / N) for i in range(k)))

print(round(birthday_collision_prob(23, 365), 4))       # 0.5073 — те самые 23 человека
print(round(birthday_collision_prob(77163, 2**32), 4))  # 0.5    — 32 бита ломаются на 77 тысячах
print(birthday_collision_prob(10**6, 2**64))            # 2.7e-08 — 64 бита ещё держатся

Криптографическое следствие, которое обязан знать каждый: стойкость хеша к коллизиям равна половине его длины в битах. У SHA-256 это 128 бит, у SHA-1 — 80, и именно поэтому SHA-1 пал: атака SHAttered стоила примерно 2^63 операций (shattered.io). Отсюда же практическое правило: UUIDv4 со 122 случайными битами безопасен для миллиардов записей, а 64-битный идентификатор — нет. Вероятностная сторона подробнее разобрана в статье Теория вероятностей и статистика.

8. Рекуррентности: счёт по индукции

Когда прямой формулы нет, объект описывают рекуррентно — той же идеей, что динамическое программирование. Пример: сколько двоичных строк длины n не содержат подстроки «11»? Классифицируем по последнему символу: строка на 0 продолжает любую допустимую длины n-1; строка на 1 требует перед собой 0, то есть любую допустимую длины n-2.

a(n) = a(n-1) + a(n-2),   a(0) = 1, a(1) = 2      -> Фибоначчи со сдвигом

Тот же счёт естественно рисуется как автомат, где состояние — последний символ, а число строк длины n — число путей длины n:

Это мост к трансфер-матрицам: число слов длины n равно сумме элементов n-й степени матрицы переходов. Приём работает для любого регулярного ограничения (связь с автоматами — в статье Автоматы, формальные языки и грамматики) и даёт O(m^3 log n) вместо O(n).

import numpy as np
from itertools import product

# T[i][j] = 1, если из состояния i можно перейти в j. Состояния: 0 -> последний 0, 1 -> последний 1.
T = np.array([[1, 1],
              [1, 0]], dtype=object)     # object -> длинная арифметика, без переполнения
ones = np.array([1, 1], dtype=object)

def count_words(n: int) -> int:
    """Число двоичных строк длины n без '11'. O(log n) умножений матриц 2x2."""
    if n == 0:
        return 1
    return int(ones @ np.linalg.matrix_power(T, n - 1) @ ones)

def brute(n: int) -> int:
    return sum(1 for s in product("01", repeat=n) if "11" not in "".join(s))

assert [count_words(n) for n in range(1, 13)] == [brute(n) for n in range(1, 13)]
print([count_words(n) for n in range(1, 10)])   # [2, 3, 5, 8, 13, 21, 34, 55, 89]
print(len(str(count_words(1000))))              # 210 десятичных цифр

Числа Каталана

Cat(n) считает сразу десяток вещей, каждая из которых встречается в коде: правильные скобочные последовательности из n пар (валидация выражений в парсере), бинарные деревья поиска на n узлах, расстановки скобок в произведении n+1 матриц (matrix chain multiplication), триангуляции выпуклого (n+2)-угольника, монотонные пути под диагональю.

Cat(n) = C(2n, n) / (n + 1)
Cat(n+1) = сумма по i от 0 до n: Cat(i) * Cat(n - i)
Cat: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...

Формула доказывается «принципом отражения» Андре: из всех C(2n,n) путей вычитаем плохие (пересекающие диагональ), а плохие биективно отображаются в пути со сдвинутым концом, которых C(2n, n+1). Разность и даёт ответ — образцовое биективное доказательство.

import math
from functools import lru_cache

def catalan_direct(n: int) -> int:
    return math.comb(2 * n, n) // (n + 1)

@lru_cache(maxsize=None)
def catalan_rec(n: int) -> int:
    """Свёрточная рекуррентность: та же структура, что у DP matrix-chain, O(n^2)."""
    return 1 if n <= 1 else sum(catalan_rec(i) * catalan_rec(n - 1 - i) for i in range(n))

assert [catalan_direct(i) for i in range(10)] == [catalan_rec(i) for i in range(10)]
print(catalan_direct(20))   # 6564120420

Практический вывод: если ваш DP имеет вид «перебрать точку разбиения и перемножить ответы слева и справа», вы считаете каталановскую структуру, и число вариантов растёт как 4^n / n^1.5. Перебор невозможен, DP по интервалам за O(n^3) — вполне.

9. Производящие функции: алгебра вместо изобретательности

Производящая функция превращает последовательность a0, a1, a2, ... в формальный ряд A(x) = a0 + a1*x + a2*x^2 + .... Смысл: операции над последовательностями становятся арифметикой над рядами — сдвиг это умножение на x, свёртка это произведение рядов, частичные суммы это деление на (1−x). Дальше решаем алгебраическое уравнение и извлекаем коэффициент.

Для Фибоначчи из F(n) = F(n-1) + F(n-2) получается F(x) = x / (1 − x − x^2); разложение на простейшие дроби даёт формулу Бине и сразу асимптотику F(n) ~ phi^n / sqrt(5), где phi = 1.618....

Второй пример — «сколькими способами набрать сумму n монетами номиналов 1, 2, 5»:

G(x) = 1/(1−x) * 1/(1−x^2) * 1/(1−x^5)

Каждый множитель отвечает за «сколько монет данного номинала взять», перемножение рядов и есть перебор комбинаций, коэффициент при x^n — ответ. Это ровно алгоритм «неограниченный рюкзак», записанный как умножение многочленов:

def coin_ways(target: int, coins: list[int]) -> list[int]:
    """Коэффициенты производящей функции = классический DP по монетам.
    O(target * len(coins)) времени, O(target) памяти."""
    dp = [0] * (target + 1)
    dp[0] = 1
    for c in coins:                       # умножаем ряд на 1/(1 - x^c)
        for s in range(c, target + 1):
            dp[s] += dp[s - c]
    return dp

ways = coin_ways(20, [1, 2, 5])
print(ways[10], ways[20])   # 10 29

Порядок циклов задаёт семантику: внешний цикл по монетам считает сочетания (порядок не важен), внешний цикл по сумме — композиции («1+2» и «2+1» различны). Это самая частая ошибка в задачах на монеты, и комбинаторная интерпретация объясняет её мгновенно. Систематическое изложение — «generatingfunctionology» Уилфа и Analytic Combinatorics Флажоле и Седжвика, где производящие функции превращены в машину автоматического вывода асимптотик алгоритмов.

10. Асимптотика: почему всё взрывается

Инженеру важнее порядок роста, чем точное значение.

Формула Стирлинга:  n! ≈ sqrt(2*pi*n) * (n/e)^n
                    ln(n!) = n*ln(n) − n + 0.5*ln(2*pi*n) + O(1/n)

Через энтропию:     C(n, k) ≈ 2^(n * H(k/n)) / sqrt(2*pi*n*p*(1-p))
                    H(p) = −p*log2(p) − (1−p)*log2(1−p)
Центральный:        C(2n, n) ≈ 4^n / sqrt(pi * n)

H(p) — двоичная энтропия, та же, что в теории информации. Совпадение не случайно: log2 C(n, pn) — число бит для кодирования подмножества и одновременно предел сжатия последовательности с долей единиц p. Комбинаторика и теория информации — одна математика в двух костюмах.

import math

def log2_comb(n, k):
    return (math.lgamma(n+1) - math.lgamma(k+1) - math.lgamma(n-k+1)) / math.log(2)

def entropy_bound(n, k):
    p = k / n
    return n * (-p*math.log2(p) - (1-p)*math.log2(1-p))

for n in (100, 10_000, 1_000_000):
    print(n, round(log2_comb(n, n//4), 2), round(entropy_bound(n, n//4), 2))
# 100 77.68 81.13
# 10000 8106.02 8112.78
# 1000000 811268.04 811278.12

Разрыв растёт всего как ~0.5*log2(n), то есть относительная погрешность энтропийной оценки стремится к нулю — для больших n 2^(n*H(p)) прекрасно работает «на салфетке».

Практический вывод: битмаск-DP по 2^n реально работает до n ≈ 22–25, перебор перестановок — до n ≈ 11–12. Всё, что больше, требует другой идеи, а не более быстрого процессора; формальная теория этой границы — в статье Теория сложности.

11. Симметрии: лемма Бёрнсайда

Отдельный класс задач — «сколько объектов с точностью до симметрии»: сколько различных ожерелий из n бусин, если поворот не создаёт нового объекта; сколько неизоморфных конфигураций. Лемма Бёрнсайда (она же Коши–Фробениуса): число орбит равно среднему числу неподвижных точек по элементам группы, (1/|G|) * сумма по g из G: |Fix(g)|. Для поворотов ожерелья это даёт N(n,k) = (1/n) * сумма по делителям d числа n: phi(d) * k^(n/d).

from math import gcd

def euler_phi(m: int) -> int:
    return sum(1 for i in range(1, m + 1) if gcd(i, m) == 1)

def necklaces(n: int, k: int) -> int:
    """Ожерелья длины n из k цветов с точностью до поворота."""
    return sum(euler_phi(d) * k**(n // d) for d in range(1, n + 1) if n % d == 0) // n

print([necklaces(n, 2) for n in range(1, 9)])   # [2, 3, 4, 6, 8, 14, 20, 36]

В проде это подсчёт неизоморфных конфигураций при генерации тестов, дедупликация геометрических и химических структур, канонизация ключей кеша, редукция симметрий в model checking.

12. Где это встречается в разработке

Комбинаторное тестирование. Конфигурация из 10 параметров по 4 значения даёт 4^10 ≈ 10^6 комбинаций — полный перебор невозможен. Эмпирика NIST показывает, что большинство дефектов вызывается взаимодействием 2–3 параметров, а покрывающий массив силы 2 (pairwise) для этого случая содержит порядка 30 тестов: сокращение на четыре порядка при потере малой доли дефектов. См. NIST ACTS.

Планировщик запросов. Селективности независимых предикатов перемножаются (правило произведения), для OR работает включение-исключение. Число порядков соединения n таблиц факториально по перестановкам и каталановское по форме дерева, поэтому PostgreSQL при большом числе таблиц переключается с полного перебора на генетический оптимизатор (GEQO). Допущение независимости предикатов — источник катастрофических недооценок на коррелированных колонках, отсюда CREATE STATISTICS.

Криптография. Всё сводится к «сколько вариантов у атакующего»: пространство паролей алфавит^длина, стойкость к коллизиям 2^(бит/2), число подключей в атаке «встреча посередине». Оценивать энтропию надо по реальному распределению: «Password1!» формально это 10 символов из 70, фактически около 20 бит.

Machine learning. Число полиномиальных признаков степени d от p исходных равно C(p+d, d) — отсюда «проклятие размерности». Hashing trick отображает признаки в фиксированное число бакетов, и число коллизий предсказывается задачей о шарах и ящиках. Число подмножеств признаков 2^p объясняет, почему полный feature selection невозможен и используются жадные и регуляризационные методы.

Верификация. Система из k компонентов по m состояний имеет до m^k глобальных состояний — state explosion problem. Симметрийная редукция и частичные порядки сокращают пространство на порядки; это стандартный приём в TLA+ и SPIN.

13. Типичные заблуждения

1. «Порядок не важен — делим на k!» Делить можно, только если каждая неупорядоченная конфигурация получена ровно k! раз. При одинаковых элементах нужен мультиномиальный коэффициент или лемма Бёрнсайда.
2. «Правило суммы всегда работает». Только для непересекающихся случаев; иначе ответ завышен.
3. «Вероятности перемножаются». Только при независимости — см. проблему коррелированных предикатов в оптимизаторах БД.
4. «Коллизия наступит примерно после N вставок». Нет, после sqrt(N). Разница между 2^32 и 2^16 — это разница между «никогда» и «сегодня к обеду».
5. «Формула проверена на n = 3, значит верна». Мелкие случаи вырождены; проверяйте на n = 0, 1 и n = 5..7 брутфорсом.
6. «C(n,k) считаем через факториалы». В языках с фиксированной разрядностью это переполняется задолго до переполнения результата — нужны итеративная формула или логарифмы.
7. «У нас маленькие n, асимптотика неважна». 13! уже больше 6 миллиардов: «маленькое n» в комбинаторике означает n ≤ 10.

14. Итог и что почитать

• Вся элементарная комбинаторика вырастает из трёх идей: правило суммы, правило произведения и построение биекции. Формулы — производные от них, а не самостоятельные сущности.
• Четыре схемы выборки покрывают большинство бытовых задач; шары-и-ящики и twelvefold way — более общая рамка.
• Включения-исключения дают точный ответ ценой O(2^m); в проде их заменяют скетчами.
• Принцип Дирихле порождает фундаментальные ограничения (коллизии, сжатие, кеш), а birthday bound определяет реальную стойкость хешей: половина длины в битах.
• Рекуррентности и производящие функции — систематическая замена изобретательности алгеброй и теоретическая изнанка динамического программирования.
• Асимптотика отвечает на инженерный вопрос «до какого n это вообще перебирается»: 2^n — до ~25, n! — до ~12.

Источники: Graham, Knuth, Patashnik, Concrete Mathematics (страница книги) — эталонный учебник вычислительной комбинаторики; Stanley, Enumerative Combinatorics vol. 1 (math.mit.edu/~rstan/ec) — источник twelvefold way; Wilf, generatingfunctionology (бесплатный PDF); Flajolet, Sedgewick, Analytic Combinatorics (бесплатный PDF); van Lint, Wilson, A Course in Combinatorics; OEIS; документация Python — itertools и math.

Что дальше

Комбинаторика естественно перетекает в теорию графов: граф — это конечное множество вершин плюс множество пар, и почти каждый вопрос о графах («сколько остовных деревьев», «сколько раскрасок», «есть ли гамильтонов цикл») решается уже знакомыми инструментами — включениями-исключениями, рекуррентностями и оценками роста.

Теория графов: структуры, свойства и теоремы