Аппарат формальных степенных рядов есть достаточно универсальный метод порождения и пересчета комбинаторных конфигураций.

Определение: Порождающая функция для множества (для числа) всех комбинаторных конфигураций данного типа, построенных на основе множества М={x₁,x₂,…,x_n} есть функция f(t,x₁,…,x_n) (функция g(t)), в формальном разложении которой в ряд по степеням t коэффициент при t^r есть все комбинаторные конфигурации (число всех комбинаторных конфигураций) из n элементов по r каждой конфигурации.

Пример: M={x₁,x₂,x₃}. |M| = 3.
Функция f(t,x₁,x₂,x₃) = ∏(1+x_kt) = (1+x₁t)(1+x₂t)(1+x₃t) = t⁰ + (x₁ + x₂ + x₃)¹ + (x₁x₂ + x₁x₃ + x₂x₃)t² + x₁x₂x₃t³ есть порождающая функция для сочетаний из трех элементов n=3 по r последовательно равных 0,1,2,3.

x₁ = x₂ = x₃ = 1
g(t) = f(t,1,1,1) = ∏(1+t) = 1 + 3t + 3t² + t³
g(t) есть порождающая функция для числа сочетаний элементов.

Комментарии запрещены.