Список заданий по ДМ 2к 2017 весна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 24: Строка 24:
 
# Последовательность $a_0, a_1, a_2, \ldots, a_k$ имеет производящую функцию $A(s)=a_0+a_1t+a_2t^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_2, a_4, a_6\ldots$.
 
# Последовательность $a_0, a_1, a_2, \ldots, a_k$ имеет производящую функцию $A(s)=a_0+a_1t+a_2t^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_2, a_4, a_6\ldots$.
 
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
 
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_2n=f_{2n+1}$.
+
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.
 
# Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
 
# Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
 
# Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками.
 
# Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками.
 
# Найдите производящую функцию для чисел Каталана.
 
# Найдите производящую функцию для чисел Каталана.
 
</wikitex>
 
</wikitex>

Версия 01:45, 26 февраля 2017

<wikitex>

  1. Формальный степенной ряд $\exp(s) = e^s$ определен как $e^s=1+\frac{1}{1!}s+\frac{1}{2!}s^2+\frac{1}{3!}s^3+\ldots+\frac{1}{n!}s^n+\ldots$. Логично, что $e^{-s}=1-\frac{1}{1!}s+\frac{1}{2!}s^2-\frac{1}{3!}s^3+\ldots+(-1)^n\frac{1}{n!}s^n+\ldots$. Докажите, используя определение умножения для степенных рядов, что $e^se^{-s}=1$.
  2. Формальный степенной ряд $(1+s)^\alpha$ определен как $(1+s)^\alpha=1+\frac{\alpha}{1}s+\frac{\alpha(\alpha-1)}{1 \cdot 2}s^2+\ldots+\frac{\alpha(\alpha-1)\ldots(\alpha-n+1)}{1 \cdot 2 \cdot\ldots\cdot n}s^n+\ldots$. Докажите, что $(1+s)^\alpha(1+s)^\beta=(1+s)^{\alpha+\beta}$.
  3. Формальный степенной ряд $\ln\left(\frac{1}{1-s}\right)$ определен как $\ln\left(\frac{1}{1-s}\right)=s+\frac{1}{2}s^2+\frac{1}{3}s^3+\ldots+\frac{1}{n}s^n+\ldots$. Докажите, что $\exp\left(\ln\left(\frac{1}{1-s}\right)\right)=(1-s)^{-1}$.
  4. Пусть $B(s) = b_1s+b_2s^2+b_3s^3+\ldots+b_ns^n+\ldots$, причем $b_1\ne 0$. Пусть формальные степенные ряды $A(s)$ и $C(s)$ таковы, что $A(B(s)) = s$, $B(C(s))=s$. Докажите, что $A(s)=C(s)$ Этот ряд называется обратным к $B(s)$, обозначается как $B^{-1}(s)$.
  5. Докажите, что не существует формального степенного ряда $A(s)$, такого что $sA(s)=1$.
  6. Будем называть нулем степенной ряд $0(s) = 0 + 0s + 0s^2 + \ldots$. Докажите, что $A(s) \ne 0(s)$, $B(s) \ne 0(s)$, то $A(s)B(s) \ne 0(s)$.
  7. Пусть формальный степенной ряд $A(s)$ имеет целые коэффициенты. При каких условиях ряд $\frac{1}{A(s)}$ имеет целые коэффициенты?
  8. Пусть формальный степенной ряд $A(s)$ имеет целые коэффициенты. При каких условиях ряд $A^{-1}(s)$ имеет целые коэффициенты?
  9. Докажите, что $(A(s) + B(s))' = A'(s) + B'(s)$.
  10. Докажите, что $(A(s)B(s))' = A'(s)B(s) + A(s)B'(s)$.
  11. Докажите, что $\int(A'(s)B(s) + A(s)B'(s)) = A(s)B(s) - A(0)B(0)$.
  12. Найдите производящую функцию для последовательности $1, 2, 3, \ldots, n, \ldots$.
  13. Найдите производящую функцию для последовательности $0 \cdot 1, 1 \cdot 2, 2 \cdot 3, 3 \cdot 4, \ldots, (n - 1) \cdot n, \ldots$.
  14. Найдите производящую функцию для последовательности $1^2, 2^2, 3^2, \ldots, n^2, \ldots$.
  15. Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Последовательность $1, -2, 3, -4, 5, \ldots$.
  16. Последовательность $2, -6, 12, \ldots, (-1)^k(k+1)(k+2),\ldots$.
  17. Последовательность $1, -4, 9, -16, \ldots, (-1)^k(k+1)^2,\ldots$.
  18. Последовательность $1, 1, 4, 9, 25, \ldots, F_k^2,\ldots$.
  19. Последовательность $a_0, a_1, a_2, \ldots, a_k$ имеет производящую функцию $A(s)=a_0+a_1t+a_2t^2+\ldots$. Найдите производящую функцию последовательности $a_0 + a_1, a_1 + a_2, \ldots, a_k+a_{k+1}$.
  20. Последовательность $a_0, a_1, a_2, \ldots, a_k$ имеет производящую функцию $A(s)=a_0+a_1t+a_2t^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{i=0}^ka_i,\ldots$.
  21. Последовательность $a_0, a_1, a_2, \ldots, a_k$ имеет производящую функцию $A(s)=a_0+a_1t+a_2t^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_1b, a_2b^2, \ldots, a_kb^k$.
  22. Последовательность $a_0, a_1, a_2, \ldots, a_k$ имеет производящую функцию $A(s)=a_0+a_1t+a_2t^2+\ldots$. Найдите производящую функцию последовательности $a_0, 0, a_1, 0, a_2, 0, a_3\ldots$.
  23. Последовательность $a_0, a_1, a_2, \ldots, a_k$ имеет производящую функцию $A(s)=a_0+a_1t+a_2t^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_2, a_4, a_6\ldots$.
  24. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
  25. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.
  26. Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
  27. Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками.
  28. Найдите производящую функцию для чисел Каталана.

</wikitex>