244
правки
Изменения
Нет описания правки
# Обозначим за $a_n$ количество способов разменять $n$ рублей монетами по $1$, $2$ и $5$ рублей (порядок монет важен). Постройте производящую функцию для $a_n$.
# То же самое, что в предыдущем задании, но порядок монет не важен.
# Последовательность задана рекуррентным соотношением $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(t) = \frac {P(t)}{Q(t)}$, где единственный минимальный по модулю корень $Q(t)$ равен $1 / \beta$ и имеет кратность $k$. Тогда $a_n \approx C \beta^n n^{k-1}$. Покажите, что $C = k \frac {(-\beta)^k P(1 / \beta)} {Q^{(k)}(1 / \beta)}$
# Найдите ПФ последовательности $a_n$, где $a_n = n + 1$ для четных $n$, $a_n = 2^n$ для $n = 1, 5, \ldots, 4k+1, \ldots$, $a_n = 3^n$ для $n = 3, 7, \ldots, 4k+3, \ldots$; проанализируйте асимптотическое поведение.
# Докажите, что если последовательность $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}$.
