Генератриса

Матеріал з Вікіпедії — вільної енциклопедії.
Версія від 12:17, 1 липня 2019, створена InternetArchiveBot (обговорення | внесок) (Виправлено джерел: 0; позначено як недійсні: 2. #IABot (v2.0beta15))
Перейти до навігації Перейти до пошуку

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

.

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

.

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

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

і

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

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

Властивості

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

Приклади

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

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

Додатково

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

Див. також

Посилання

  • http://slovari.yandex.ru/генератриса/БСЭ/Производящая%20функция/[недоступне посилання з липня 2019] — Стаття у Великій Радянській Енциклопедії
  • Юрій Дрозд (2004). Твірна функція. (PDF). КНУ ім. Т. Г. Шевченка http://www.imath.kiev.ua/~drozd/Discrete.pdf. {{cite book}}: Пропущений або порожній |title= (довідка); Проігноровано |work= (довідка)
  • Бронштейн Е. М. Производящие функции // Соросовский Образовательный Журнал. — 2001. — Т. 7, № 2.
  • Воронин С., Кулагин А. Метод производящих функций // Квант. — 1984. — № 5.
  • Ландо С. К. Лекции по комбинаторике. — МЦНМО, 1994.
  • Ландо С. К. Лекции о производящих функциях. — М. : МЦНМО, 2007. — 144 с. — ISBN 978-5-94057-042-4.
  • В. Феллер. Глава XI. Целочисленные величины. Производящие функции // Введение в теорию вероятностей и её приложения = An introduction to probability theory and its applicatons. — 2-е изд. — М. : Мир, 1964. — С. 270—272.
  • Herbert S. Wilf. Generatingfunctionology. — Academic Press, 1994. — ISBN 0-12-751956-4.