Генератриса

У комбінаториці генератри́са або твірна функція (англ. generating function) послідовності ${\displaystyle \{a_{n}\}}$ — це формальний степеневий ряд

${\displaystyle f(x)=\sum _{n=0}^{\infty }a_{n}x^{n}}$.

Експоненційна генератриса (твірна функція) — це формальний степеневий ряд

${\displaystyle \sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}}$.

Доволі часто генератриса (твірна функція) послідовності ${\displaystyle \{a_{n}\}}$ є одночасно рядом Тейлора відомої аналітичної функції, і це можна використовувати при дослідженні властивостей самої послідовності. Тим не менше, генератрисі необов'язково відповідає аналітична функція.

Наприклад, два ряди

${\displaystyle \sum _{n=0}^{\infty }(3^{n})^{n}x^{n}}$ і ${\displaystyle \sum _{n=0}^{\infty }(2^{n})^{n}x^{n}}$

мають радіус збіжності нуль, тобто розбігаються в усіх точках, крім нуля, а в нулі обидва дають 1, тобто як функції вони збігаються; тим не менше, як генератриси (тобто формальні ряди) вони різні.

Генератриси (твірні функції) надають можливість просто описувати складні послідовності в комбінаториці, а іноді допомагають знайти для них явні формули. Метод генератрис був розроблений Ейлером у 50-х роках XVIII століття.

Властивості

• (Експоненціальна) генератриса (твірна функція) суми (чи різниці) двох послідовностей дорівнює сумі (чи різниці) відповідних (експоненціальних) генератрис.
• Якщо ${\displaystyle A(x)=\sum _{n=0}^{\infty }a_{n}x^{n}}$ і ${\displaystyle B(x)=\sum _{n=0}^{\infty }b_{n}x^{n}}$ — генератриси послідовностей ${\displaystyle \{a_{n}\}}$ і ${\displaystyle \{b_{n}\}}$, то ${\displaystyle A(x)B(x)=\sum _{n=0}^{\infty }c_{n}x^{n}}$, де ${\displaystyle c_{n}=\sum _{k=0}^{n}a_{k}b_{n-k}}$.
• Якщо ${\displaystyle A(x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}}$ і ${\displaystyle B(x)=\sum _{n=0}^{\infty }b_{n}{\frac {x^{n}}{n!}}}$ — експоненційні генератриси послідовностей ${\displaystyle \{a_{n}\}}$ і ${\displaystyle \{b_{n}\}}$, то ${\displaystyle A(x)B(x)=\sum _{n=0}^{\infty }c_{n}{\frac {x^{n}}{n!}}}$, де ${\displaystyle c_{n}=\sum _{k=0}^{n}{n \choose k}a_{k}b_{n-k}}$.

Приклади

Нехай ${\displaystyle B_{n}}$ дорівнює кількості варіантів представлення числа ${\displaystyle n}$ у вигляді ${\displaystyle k_{1}+k_{2}+\cdots +k_{m}}$, де ${\displaystyle \{k_{i}\}}$ — невід'ємні цілі числа і ${\displaystyle m}$ фіксовано, тоді

${\displaystyle \sum _{n=0}^{\infty }B_{n}x^{n}=(1+x+x^{2}+\cdots )^{m}=(1-x)^{-m}}$

Тепер число ${\displaystyle B_{n}}$ можна знайти як коефіцієнт при ${\displaystyle x^{n}}$ в розкладі ${\displaystyle (1-x)^{-m}}$ по степенях ${\displaystyle x}$. Для цього можна скористатися визначенням біноміальних коефіцієнтів або ж безпосередньо взяти n разів похідну в нулі:

${\displaystyle B_{n}=(-1)^{n}{-m \choose n}=m(m+1)\cdots (m+n-1)/n!={m+n-1 \choose n}.}$

Додатково

Переклад «генератриса» терміну «generating function» з англійської є не досить вдалим. Краще використовувати натомість більш вживаний термін в українській математичній літературі — «твірна функція», якому відповідає російське «производящая функция» [1]^{[недоступне посилання з липня 2019]}.

Див. також

• Генератриса цілочисельної випадкової величини
• Рекурентне співвідношення

Посилання

• Карташов М. В. Імовірність, процеси, статистика. — Київ : ВПЦ Київський університет, 2007. — 504 с.
• Дрозд Ю. А. (2004). Дискретна математика (PDF). Київ: РВЦ “Київський університет„. с. 70. (укр.)
• Бронштейн Е. М. Производящие функции // . — 2001. — Т. 7, № 2.
• Воронин С., Кулагин А. Метод производящих функций // Квант. — 1984. — № 5.
• Ландо С. К. Лекции по комбинаторике. — МЦНМО, 1994.
• Ландо С. К. Лекции о производящих функциях. — М. : МЦНМО, 2007. — 144 с. — .
• В. Феллер. Глава XI. Целочисленные величины. Производящие функции // Введение в теорию вероятностей и её приложения = An introduction to probability theory and its applicatons. — 2-е изд. — М. : Мир, 1964. — С. 270—272.
• Herbert S. Wilf. Generatingfunctionology. — Academic Press, 1994. — .