Генератриса

Матеріал з Вікіпедії — вільної енциклопедії.

У комбінаториці генератри́са послідовності {an} — це формальний степеневий ряд

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

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

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

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

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

\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 —генератриси послідовностей {an} і {bn}, то 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!} — експоненційні генератриси послідовностей {an} і {bn}, то 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}.

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

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

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

Тепер число Bn можна знайти як коефіцієнт при xn в розкладі (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}.