Перегляд вихідного коду сторінки Генератриса

У [[комбінаторика|комбінаториці]] '''генератри́са''' або '''твірна функція''' ({{lang-en|generating function}}) послідовності <math>\{ a_n \}</math>&nbsp;— це формальний [[степеневий ряд]]
: <math>f(x) = \sum_{n=0}^\infty a_n x^n</math>.

'''Експоненційна генератриса (твірна функція)'''&nbsp;— це формальний степеневий ряд
: <math>\sum_{n=0}^\infty a_n \frac{x^n}{n!}</math>.

Доволі часто генератриса (твірна функція) послідовності <math>\{ a_n \}</math> є одночасно [[ряд Тейлора|рядом Тейлора]] відомої [[аналітична функція|аналітичної функції]], і це можна використовувати при дослідженні властивостей самої послідовності.
Тим не менше, генератрисі необов'язково відповідає аналітична функція.

Наприклад, два ряди
: <math>\sum_{n=0}^\infty (3^n)^n x^n</math> і <math>\sum_{n=0}^\infty (2^n)^n x^n</math>
мають [[радіус збіжності]] нуль, тобто розбігаються в усіх точках, крім нуля, а в нулі обидва дають 1, тобто як функції вони збігаються; тим не менше, як генератриси (тобто формальні ряди) вони різні.

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

== Властивості ==
* (Експоненціальна) генератриса (твірна функція) суми (чи різниці) двох послідовностей дорівнює сумі (чи різниці) відповідних (експоненціальних) генератрис.
* Якщо <math>A(x)=\sum_{n=0}^\infty a_n x^n</math> і <math>B(x)=\sum_{n=0}^\infty b_n x^n</math>&nbsp;— генератриси послідовностей <math>\{a_n\}</math> і <math>\{b_n\}</math>, то <math>A(x)B(x)=\sum_{n=0}^\infty c_n x^n</math>, де <math>c_n = \sum_{k=0}^n a_k b_{n-k}</math>.
* Якщо <math>A(x)=\sum_{n=0}^\infty a_n \frac{x^n}{n!}</math> і <math>B(x)=\sum_{n=0}^\infty b_n \frac{x^n}{n!}</math>&nbsp;— експоненційні генератриси послідовностей <math>\{a_n\}</math> і <math>\{b_n\}</math>, то <math>A(x)B(x)=\sum_{n=0}^\infty c_n \frac{x^n}{n!}</math>, де <math>c_n = \sum_{k=0}^n {n\choose k} a_k b_{n-k}</math>.

== Приклади ==

Нехай <math>B_n</math> дорівнює кількості варіантів представлення числа <math>n</math> у вигляді <math>k_1+k_2+\cdots+k_m</math>, де <math>\{k_i\}</math>&nbsp;— невід'ємні [[цілі числа]] і <math>m</math> фіксовано, тоді
: <math>\sum_{n=0}^\infty B_nx^n=(1+x+x^2+\cdots)^m=(1-x)^{-m}</math>
Тепер число <math>B_n</math> можна знайти як коефіцієнт при <math>x^n</math> в розкладі <math>(1-x)^{-m}</math> по степенях <math>x</math>. Для цього можна скористатися визначенням [[біноміальний коефіцієнт|біноміальних коефіцієнтів]] або ж безпосередньо взяти ''n'' разів [[похідна|похідну]] в нулі:
: <math>B_n=(-1)^n {-m\choose n} = m(m+1)\cdots(m+n-1)/n! = {m+n-1 \choose n}.</math>

== Додатково ==
Переклад «'''генератриса'''» терміна «'''generating function'''» з англійської є не досить вдалим. Краще використовувати натомість більш вживаний термін в українській математичній літературі&nbsp;— «'''твірна функція'''», якому відповідає російське «'''производящая функция'''» [http://mi.unicyb.kiev.ua/uploads/Articles/tvirna_function.doc]{{Недоступне посилання|date=липень 2019 |bot=InternetArchiveBot }}.

== Див. також ==
* [[Генератриса цілочисельної випадкової величини]]
* [[Рекурентне співвідношення]]

== Посилання ==
* {{Карташов.Імовірність процеси статистика}}
* {{Дрозд.Дискретна математика}}
* {{стаття|автор=Бронштейн Е. М.|назва=Производящие функции|видання=[[Соросовский Образовательный Журнал]]|рік=2001|том=7|номер=2|сторінок=103—108|посилання=http://www.pereplet.ru/nauka/Soros/pdf/0102_103.pdf}}
* {{стаття|автор=Воронин С., Кулагин А.|назва=Метод производящих функций|видання=[[Квант (журнал)|Квант]]|номер=5|рік=1984|посилання=http://kvant.mccme.ru/1984/05/metod_proizvodyashchih_funkcij.htm}}
* {{книга|автор=Ландо С. К.|посилання=http://www.mccme.ru/ium/ancient/combs93.html|назва=Лекции по комбинаторике|видавництво=[[МЦНМО]]|рік=1994}}
* {{книга |автор=Ландо С. К. |назва=Лекции о производящих функциях |издание=3-е изд., испр. |місто={{М.}} |видавництво=[[МЦНМО]] |рік=2007 |сторінок=144 |посилання=http://school-collection.edu.ru/catalog/res/d62ef84c-a780-11dc-945c-d34917fee0be/view |isbn=978-5-94057-042-4}}
* {{книга|автор=В. Феллер. |назва=Введение в теорию вероятностей и её приложения |оригінал=An introduction to probability theory and its applicatons |перекладач=Пер. с англ. Р. Л. Добрушина, А. А. Юшкевича,  С. А. Молчанова; С предисловием А. Н. Колмогорова; Под ред. Е. Б. Дынкина |частина=Глава XI. Целочисленные величины. Производящие функции |місто={{М.}} |видавництво=Мир |видання=2-е изд |рік=1964 |сторінки=270—272}}
* {{книга|автор=Herbert S. Wilf.|назва=Generatingfunctionology|рік=1994|видавництво=Academic Press|isbn=0-12-751956-4|посилання=http://www.math.upenn.edu/~wilf/DownldGF.html}}

[[Категорія:Комбінаторика]]
[[Категорія:Многочлени]]
[[Категорія:Теорія масового обслуговування]]
[[Категорія:Теорія ймовірностей]]