Изменения
Нет описания правки
# Можно заметить, что производящая функция последовательности $a_n = n^m$ будет иметь вид $\frac {P_m(s)}{(1-s)^{m+1}}$. Выведите рекуррентное соотношение для коэффициентов многочленов $P_{m, k}$.
# Оказывается, что коэффициенты $P_{m,k}$ также являются количеством некоторых комбинаторных объектов. Вскройте архивы домашних заданий по комбинаторике за первый семестр и вспомните, каких.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-1}-8a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-2}-a_{n-1}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-1}-9a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 2a_{n-1}-2a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Пусть рациональная производящая функция имеет вид $A(s) = \frac {P(s)}{Q(s)}$, где единственный минимальный по модулю корень $Q(s)$ равен $1 / \beta$ и имеет кратность $k$. Тогда $a_n \approx C \beta^k n^{k-1}$. Покажите, что $C = k \frac {(-\beta)^n P(1 / \beta)} {Q^{(k)}(1 / \beta)}$
# Докажите, что если последовательность $a_n$ допускает представление в виде $a_n = \sum_i p_i(n)q_i^n$, где $p_i(n)$ - полиномы, и все $q_i$ различны, то такое представление единственно с точностью до порядка слагаемых.
# Из производящей функции чисел Каталана $C(t) = \frac {1 - \sqrt{1-4t}} {2t}$ покажите, что $C_n = \frac {1}{n+1} {2n \choose n}$.
# Путь Моцкина - путь, начинающийся в точке $(0, 0)$, составленный из векторов $(1, 1)$, $(1, 0)$, $(1, -1)$, не опускающийся ниже оси $OX$ и заканчивающийся в точке $(n, 0)$. Напишите рекуррентное соотношение для числа путей Моцкина, найдите производящую функцию для числа таких путей. Указание: в этом и нескольких следующих заданиях напишите рекуррентное соотношение, похожее на соотношение для чисел Каталана.
# Рассмотрим множество путей на прямой, начинающихся в 0, состоящих из шагов длины 1 вправо или влево. Будем называть такой путь блужданием. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0.
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$.
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$ и не заходящих в отрицательную полупрямую.
# Произведением Адамара двух производящих функций $A(t)$ и $B(t)$ называется производящая функция для ряда $C(t) = a_0b_0+a_1b_1t+a_2b_2t^2+\ldots+a_nb_nt^n+\ldots$. Докажите, что если $A(t)$ и $B(t)$ являются рациональными, то и $C(t)$ рациональна.
# Найдите произведение Адамара $\frac{1}{1-t}$ и $\frac{1}{1-2t}$.
# Найдите произведение Адамара $\frac{1}{1-2t}$ и $\frac{1}{1-3t}$.
# Найдите произведение Адамара $\frac{1}{1+3t-t^2}$ и $\frac{1}{1-2t}$.
# Найдите произведение Адамара $\frac{1}{(1-3t)^2}$ и $\frac{1}{(1-2t)^2}$.
# Найдите произведение Адамара $\frac{t}{1-3t+2t^2}$ и $\frac{2-4t}{1-4t+3t^2}$.
