Генератриса

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

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

\sum_{n=0}^\infty a_n x^n.

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

\sum_{n=0}^\infty a_n \frac{x^n}{n!}.

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

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

\sum_{n=0}^\infty (3^n)^n x^n і \sum_{n=0}^\infty (2^n)^n x^n

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

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

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

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

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

Нехай B_n дорівнює кількості варіантів представлення числа n у вигляді k_1+k_2+\cdots+k_m, где \{k_i\} — невід'ємні цілі числа і m фіксовано, тоді

\sum_{n=0}^\infty B_nx^n=(1+x+x^2+\cdots)^m=(1-x)^{-m}

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

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

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

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

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

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