Генератриса

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

У комбінаториці генератри́са (більш вживаний синонімтвірна функція [1], з англ.generating function, рос. - производящая функция ) послідовності — це формальний степеневий ряд

.

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

.

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

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

і

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

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

Властивості[ред.ред. код]

  • (Експоненціальна) генератриса (твірна функція) суми (чи різниці) двох послідовностей дорівнює сумі (чи різниці) відповідних (експоненціальних) генератрис.
  • Якщо і — генератриси послідовностей і , то , де .
  • Якщо і — експоненційні генератриси послідовностей і , то , де .

Приклади[ред.ред. код]

Нехай дорівнює кількості варіантів представлення числа у вигляді , где — невід'ємні цілі числа і фіксовано, тоді

Тепер число можна знайти як коефіцієнт при в розкладі по степеняx . Для цього можна скористатися визначенням біноміальних коефіцієнтів або ж безпосередньо взяти n разів похідну в нулі:

Додатково[ред.ред. код]

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]