Производящие функции для комбинаторных конфигураций и их числа

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

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

Пример: M={x1,x2,x3}. |M| = 3.
Функция f(t,x1,x2,x3) = ∏(1+xkt) = (1+x1t)(1+x2t)(1+x3t) = t0 + (x1 + x2 + x3)1 + (x1x2 + x1x3 + x2x3)t2 + x1x2x3t3 есть порождающая функция для сочетаний из трех элементов n=3 по r последовательно равных 0,1,2,3.

x1 = x2 = x3 = 1
g(t) = f(t,1,1,1) = ∏(1+t) = 1 + 3t + 3t2 + t3
g(t) есть порождающая функция для числа сочетаний элементов.


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





Статистика

Рейтинг@Mail.ru