Производящие функции

Обыкновенные производящие функции

Последовательность {aₙ} ↔ f(x) = Σₙ₌₀^∞ aₙxⁿ.

Операции над последовательностями ↔ операции над функциями.

Свёртка: (a*b)ₙ = Σₖ₌₀ⁿ aₖbₙ₋ₖ ↔ f(x)·g(x).

Число разбиений числа n в части 1,2,3,...: ∏ₖ₌₁^∞ 1/(1−xᵏ) = Σₙ p(n)xⁿ.

Число разбиений в нечётные части = число разбиений в различные части (замечательное тождество Эйлера).

Экспоненциальные производящие функции

Для меченых объектов: f(x) = Σₙ aₙxⁿ/n!.

Произведение ЭПФ: a*b_n = C(n,k)aₖbₙ₋ₖ (выбор k меченых мест).

Число перестановок без фиксированных точек: D_n = n! Σ (−1)ᵏ/k!. ЭПФ: e^{−x}/(1−x).

Линейные рекуррентности и дроби

Последовательность линейно рекуррентна ⟺ её ОПФ — рациональная функция.

F(n) (Фибоначчи) → f(x) = x/(1−x−x²) = x/((1−φx)(1−ψx)). Разложение на простые дроби → формула Бине.

Аналитические методы

Метод седловой точки (Лапласа): для коэффициента [xⁿ]f(x) при больших n — асимптотика через седловую точку f.

Применение: p(n) ~ e^{π√(2n/3)}/(4n√3) — из формулы Харди–Рамануджана через функцию η Дедекинда.

Генерирующие функции для задач анализа алгоритмов

Производящие функции систематически применяются в анализе алгоритмов (книга «Аналитическая комбинаторика» Флажоле и Седжвика). Символические методы: функция для деревьев T(z) удовлетворяет T(z) = z·exp(T(z)) для меченых корневых деревьев — это функциональное уравнение. Число корневых деревьев с n вершинами: [zⁿ]T(z) = nⁿ⁻¹/n! (опять формула Кэли).

Метод аналитического продолжения: Асимптотика коэффициентов [zⁿ]f(z) определяется особыми точками f(z). Для рациональных f: полюсы дают показательный рост. Для алгебраических f: ветвевые точки дают степенной множитель. Теорема переноса Флажоле-Одлыжко: около квадратного корневого особого точки z₀: f(z) ~ C(1−z/z₀)^{-α} ⟹ [zⁿ]f(z) ~ C·nˢ⁻¹/Γ(α)·z₀⁻ⁿ.

Случайные структуры через производящие функции

Случайное дерево: Если T — случайное корневое дерево с n вершинами (равномерно), то E[высота] = O(√n) для деревьев Кэли и O(log n) для BST из случайных перестановок. Производящие функции позволяют вычислять эти ожидания точно.

Задача об уборщике: Из колоды из n карт тянем по одной, пока не попадётся туз. Ожидаемое число ходов: (n+1)/(k+1), где k — число тузов. Формула через производящие функции «дискретной равномерной статистики порядка».

Оценки для нетривиальных перечислительных задач

Число правильных раскрасок цикла Cₙ в m цветов: P(Cₙ, m) = (m−1)ⁿ + (−1)ⁿ(m−1). Это получается из хроматического полинома через формулу включений-исключений или передаточную матрицу: [[m−1, −1],[1, 0]]ⁿ.

Число Латинских квадратов порядка n — одна из самых быстро растущих комбинаторных функций: L(n) ~ (n/e²)^{n²} (асимптотика ван дер Вардена). Точных значений известно мало (до n=11). Каждый Латинский квадрат соответствует системе ортогональных латинских квадратов, используемых в конструкции блочных кодов и дизайне экспериментов.

Блочные схемы и дизайн экспериментов

Сбалансированная неполная блочная схема (BIBS (v,b,r,k,λ)): v объектов, b блоков, каждый объект в r блоках, каждый блок из k объектов, каждая пара в λ блоках. Необходимое условие: λ(v−1) = r(k−1), bk = vr. Проективные плоскости PG(2,q) реализуют BIBS с v = b = q²+q+1, r = k = q+1, λ = 1. Применение в сельскохозяйственных опытах, клинических испытаниях, планировании компьютерных экспериментов.

Кодирование в конечных полях

Конечное поле GF(pⁿ) — поле с pⁿ элементами (p — простое). Конструкция: GF(pⁿ) = ℤ_p[x]/(f(x)), где f — неприводимый многочлен степени n над ℤ_p. Группа GF(pⁿ)* = ℤ_{pⁿ−1} — циклическая. Примитивный элемент g: порождает всю мультипликативную группу. Дискретный логарифм: решить gˣ = a — вычислительно сложная задача, основа криптографии (ECDSA, Диффи-Хеллман в эллиптических кривых). Алгоритм вычисления дискретного логарифма: Pohlig-Hellman, BSGS, Index Calculus.

Комбинаторные доказательства тождеств

Тождество Вандермонда: C(m+n,r) = Σ C(m,k)C(n,r-k). Комбинаторное доказательство: разбить группу m+n людей на r — выбрать k из первых m и r-k из вторых n. Тождество Пасаля: C(n+1,k) = C(n,k) + C(n,k-1) — элемент включён или нет. Тождество Хоккейной клюшки: Σᵢ₌₀^r C(n+i,i) = C(n+r+1,r). Комбинаторное: выбрать r из {1,...,n+r+1} и посмотреть на наибольший невыбранный.

Теорема Поллярда и алгебраическая комбинаторика

Полиномиальные методы в комбинаторике: Nullstellensatz Комбинаторный (Алон): если сумма степеней полинома по переменным f(x₁,...,xₙ) = Σ cₐxᵃ имеет ненулевой коэффициент при xₐ: aᵢ = dᵢ и дано Sᵢ с |Sᵢ| > dᵢ, то ∃ sᵢ ∈ Sᵢ: f(s₁,...,sₙ) ≠ 0. Применение: граница Хэмминга из ТА, теорема Эрдёша-Ко-Радо через многочлены, дизайн кодов с геометрическими свойствами.

Числа Каталана и их комбинаторные интерпретации

Cₙ = C(2n,n)/(n+1) = 1,1,2,5,14,42,132,... Считают: правильно расставленных скобок, BST с n вершинами, нево-пересекающихся разбиений, монотонных маршрутов под диагональю, триангуляций (n+2)-угольника. ОПФ: C(x) = (1−√(1−4x))/2x. Рекуррентность: Cₙ₊₁ = ΣCₖCₙ₋ₖ — свёрточная. Также: числа Нарайяны Nₙ,ₖ = C(n,k)C(n,k-1)/n — уточнение Каталана по числу пиков в маршруте Дика.

Численный пример: числа Фибоначчи через ОПФ

Задача: Вычислить F₈ через производящую функцию и формулу Бине.

Шаг 1: Рекуррентность Fₙ=Fₙ₋₁+Fₙ₋₂, F₀=0, F₁=1. ОПФ: F(x)=x/(1−x−x²).

Шаг 2: Частичные дроби: 1−x−x²=−(x−r₁)(x−r₂), корни r₁=(−1+√5)/2, r₂=(−1−√5)/2. Формула Бине: Fₙ=(φⁿ−ψⁿ)/√5, где φ=(1+√5)/2≈1.618, ψ=(1−√5)/2≈−0.618.

Шаг 3: F₈=(1.618⁸−(−0.618)⁸)/√5. Считаем: 1.618⁸≈46.98; (−0.618)⁸=(0.618)⁸≈0.022 (чётная степень, положительна).

Шаг 4: F₈=(46.98−0.022)/2.236≈46.96/2.236≈21. Проверка: 0,1,1,2,3,5,8,13,21 → F₈=21. ✓ Число Каталана C₄=14 — число BST на 4 вершинах, следующее значение: C₅=42.