У комбінаториці генератри́са або твірна функція () послідовності — це формальний степеневий ряд .
Експоненційна генератриса (твірна функція) — це формальний степеневий ряд .
Доволі часто генератриса (твірна функція) послідовності є одночасно рядом Тейлора відомої аналітичної функції, і це можна використовувати при дослідженні властивостей самої послідовності. Тим не менше, генератрисі необов'язково відповідає аналітична функція.
Наприклад, два ряди і мають радіус збіжності нуль, тобто розбігаються в усіх точках, крім нуля, а в нулі обидва дають 1, тобто як функції вони збігаються; тим не менше, як генератриси (тобто формальні ряди) вони різні.
Генератриси (твірні функції) надають можливість просто описувати складні послідовності в комбінаториці, а іноді допомагають знайти для них явні формули. Метод генератрис був розроблений Ейлером у 50-х роках XVIII століття.
Властивості (Експоненціальна) генератриса (твірна функція) суми (чи різниці) двох послідовностей дорівнює сумі (чи різниці) відповідних (експоненціальних) генератрис. Якщо і — генератриси послідовностей і , то , де . Якщо і — експоненційні генератриси послідовностей і , то , де .
Приклади
Нехай дорівнює кількості варіантів представлення числа у вигляді , де — невід'ємні цілі числа і фіксовано, тоді
Тепер число можна знайти як коефіцієнт при в розкладі по степенях . Для цього можна скористатися визначенням біноміальних коефіцієнтів або ж безпосередньо взяти n разів похідну в нулі:
Додатково Переклад «генератриса» терміна «generating function» з англійської є не досить вдалим. Краще використовувати натомість більш вживаний термін в українській математичній літературі — «твірна функція», якому відповідає російське «производящая функция» .
Див. також Генератриса цілочисельної випадкової величини Рекурентне співвідношення
Посилання