3.3 Решение рекуррентных соотношений с помощью производящих функций
Основы перечислительной комбиаторики
3.3 Решение рекуррентных соотношений с помощью производящих функций
модуль 3.3 шаг 3
Получить для рекуррентной числовой последовательности \(a_n\), заданной рекуррентным соотношением
\[a_{n+1}=a_n=2^n, \quad a_0=0\]явное выражение для обыкновенной производящей функции
\[f(z)=a_0+a_1z+a_2z^2+...\]Решение
Василий Гурьев
\[a_0=0 \quad |\cdot z^0\] \[a_1=a_0+2^1 \quad |\cdot z^1\] \[a_2=a_1+2^2 \quad |\cdot z^2\]…
\[a_n=a_{n-1}+2^n \quad |\cdot z^n\]Складываем левые и правые части равенств.
\[\sum_{n=0}a_nz^n=\sum_{n=0}a_nz^{n+1}+\sum_{n=0}2^nz^n-1\]До \(\sum_{n=0}2^nz^n\) не хватало единицы, поэтому мы её прибавили и вычли.
Меняем суммы на производящие функции.
\[f(z)=zf(z)+\frac{1}{1-2z}-1\] \[f(z)(1-z)=\frac{1-(1-2z)}{1-2z}\] \[f(z)=\frac{2z}{(1-2z)(1-z)}\]Ответ
z/((1-2*z)*(1-z))
модуль 3.3 шаг 6
Получить c помощью найденной в предыдущем упражнении обыкновенной производящей функции \(f(z)\) для рекуррентной числовой последовательности \(a_n\), заданной рекуррентным соотношением
\[a_{n+1}=a_n+2^n, \quad a_0=0\]явное выражение для коэффициентов \(a_n\).
Решение
Ответ
2^n-1
модуль 3.3 шаг 8
Решить с помощью обыкновенных производящих функций следующее линейное рекуррентное соотношение с постоянными коэффициентами:
\[a_{n+2}=4a_{n+1}-4a_n, \quad a_0=a_1=1.\]Решение
\[\sum_{n=0}^{+\infty}a_{n+2}z^{n+2}=\sum_{n=0}^{+\infty}4a_{n+1}z^{n+2}-\sum_{n=0}^{+\infty}4a_nz^{n+2}\] \[f(z)-a_0-a_1z=4z\sum_{n=0}^{+\infty}a_{n+1}z^{n+1}-4z\sum_{n=0}^{+\infty}4a_nz^n\] \[f(z)-a_0-a_1z=4z(f(z)-a_0)-4z^2f(z)\] \[f(z)(1-4z+4z^2)=1-3z => f(z)=\frac{1-3z}{(2z-1)^2}=(1-3z)\sum_{n=0}^{+\infty}\left( \binom{2}{n} \right)(2z)^n\] \[a_n=\left( \binom{2}{n} \right)2^n-3\left( \binom{2}{n-1} \right)2^{n-1}=\binom{n+1}{n}2^n-3\binom{n}{n-1}2^{n-1}=2^n(n-1)-3n2^{n-1}=2^{n-1}(2-n)\]Ответ
3*2^(n-1)-(n+1)*2^(n-1)
модуль 3.3 шаг 15
Решить с помощью экспоненциальных производящих функций линейное рекуррентное соотношение с переменными коэффициентами
\[a_{n+1}=2(n+1)a_n+(n+1)!, \quad a_0=0.\]Решение
Умножаем рекуррентное соотношение на \(\frac{z^{n+1}}{(n+1)!}\) как в предыдущей лекции
и получаем \(F(z)-a_0=2z\cdot F(z)+\frac{1}{1-z}-1\)
Далее выражаем \(F(z)\)
\[F(z)=\frac{z}{(1-z)(1-2z)}=\sum_{n=0}^{\infty}2^{n+1}z^{n+1}-\sum_{n=0}^{\infty}z^{n+1}=\sum_{n=1}^{\infty}(2^n-1)z^n\]Преобразуем до экспоненциальной производящей функции (умножаем на \(n!\) и делим на \(n!\))
\[F(z)=\sum_{n=1}^{\infty}(2^n-1)n!\frac{z^n}{n!}\]В итоге получаем что коэффициент при \(\frac{z^n}{n!}$ равен $(2^n-1)n!\)
Ответ
n!*(2^n-1)