%\documentclass{article}
%
%\usepackage[utf8]{inputenc}
%\usepackage[TS1,T2A]{fontenc}
%\usepackage[russian]{babel}
%\usepackage{amsmath}
%\usepackage{amsfonts}
%\usepackage{amssymb}
%\usepackage{amsthm}
%
%\hoffset=-3cm
%\textwidth=18cm
%\voffset=-3cm
%\textheight=26cm
%
%\date{2010-02-19}
%\title{Лекции по дискретке}
%\author{Зайцев Вадим}
%
%\begin{document}
%\maketitle

\section{Рекуррентное соотношение}

\subsubsection{Примерчик 1}
	8 дисков разного диаметра, есть 3 колышка.  Они выложены на первом в порядке возрастания.  Надо переложить с первого
	колышка на другой. Какого минимальное кол-во перекладываний?\\
	Пусть у нас есть $n$ дисков, $T_n$ - минимальное кол-во перкладываний.\\
	$ T_0 = 0\qquad T_1 = 1 \qquad T_2 = 3\\
	T_n \le 2T_{n-1}+1 \quad \Rightarrow T_n = 2T_{n-1}+1 $, т.к. чтобы переложить пирамиду высотой $n$, надо переложить
	пирамиду высотой $n{-}1$ и потом ещё переложить $n$-ый диск.\\
	А может, $T_n = 2^n-1$? $T_{n+1} = 2T_n +1 = 2(2^n-1) + 1 = 2^{n+1}-1$. Действительно, так.

\subsubsection{Небольшое обощение}
	$a_0, a_1, \ldots ,a_{n-1}, \quad a_n = f(a_{n-1}, \ldots ,a_{n-k}) \quad \forall n\ge k$
	Но считать каждое $n$ по порядку долго и требует $O(n)$ времени, поэтому лучше было бы найти волшебную ф-ию  $ a_n =
	h(n)$ со временем $O(1)$.

\subsubsection{Примерчик 2}
	$n$ пар скобок. Сколько существует правильных скобочных последовательностей определённой длины?\\
	$C_1 = 1  \quad ()\\
	C_2 = 2 \quad (()), ()()\\
	C_3 = 5 \quad ()()(), (()), ()(()), (()()), ((()))\\$
	Рассмотрим самую левую скобку: для неё существует пара. И тут должна быть красивая картинка.\\
	$C_n = C_0\cdot C_{n-1} + C_1\cdot C_{n-2}+ \ldots +C_{n-1}\cdot C_0$.\\

\subsection{последовательность чисел Каталана}
	$ \{C_n\}_{n=0}^{\infty}$ - последовательность чисел Каталана.

	Пусть $ \quad '(' = +1,  \quad  ')'=-1 \quad b_1,b_2, \ldots ,b_{2n}, b_i \in \{-1, 1\}$. Получаем сво-ва:
	\begin{enumerate}
		\item $ \displaystyle \sum_{i=1}^{2n} b_i = 0$
		\item $ \displaystyle \sum_{i=1}^j b_i \ge 0 \quad  \forall j$
	\end{enumerate}

\subsubsection{Лемма 11}
	Пусть $b_1, \ldots ,b_{2n}$  удоволетворяет 1 и 2. Тогда $ \exists!$ правильная скобочная структура с этим кодом.
	\begin{proof} Индукцией по $n$.\\
		$C_n$ - число послед. $b_1, \ldots ,b_{2n}$ из ``+1`` и ``-1``, удовл. 1 и 2.\\
		Удовлетворяют условию 1: $\binom{2n}{n}$\\
		Пусть $W_n$ - мно-во послед., удовлет. 1 и не удовлет. 2. Пусть $\alpha \in W_n, \, \alpha = \alpha_1 - \alpha_{2n} $. \\
		Рассмотрим min $j: \quad \displaystyle \sum_{i=1}^j \alpha_i = -1$\\
		$ \varphi (\alpha) \rightarrow -\alpha_1, -\alpha_2, \ldots, -\alpha_j, \alpha_{j+1}, \ldots, \alpha_{2n}$. $\in
		V_n$ - мно-во послед. из -1 и 1 длины $2n$, в которых $n+1$ единиц.\\
		$ \displaystyle \beta \in V_n,\, \beta=\beta_1, \ldots ,\beta_{2n}. \quad \exists \min j \mid \sum_{i=1}^j \beta_i=1. \quad \xi(\beta) \rightarrow \beta_1, \beta_2, \ldots \beta_{2n} \in W_n$.\\
		$ \xi(\varphi(\alpha)) = \alpha\\
		\varphi(\xi(\beta)) = \beta\\
		| W_n| = |V_n| = \binom{2n}{n+1}$
	\end{proof}

\subsubsection{Теорема 16}
	Для последовательности чисел Катална, заданных рекуррентным соотношением \\$c_n=c_0\cdot c_{n-1} + c_1\cdot c_{n-2}+
	\ldots + c_{n-1}\cdot c_0$\\$n$-ое число Каталана: $ \displaystyle C_n = \frac{1}{n+1} \binom{2n}{n}$.
	\begin{proof}\hfil\\
		1 января: 1 пара кроликов. Сколько кроликов через год? $f_n$ - число пар кроликов 1 числа $n{+}1$-ого месяца.\\
		$ f_0 = 1, \quad f_1 = 1, \quad f_2=2, \quad  \ldots  \quad f_{12} = ? $\\
		$ f_n = f_{n-1} + f_{n-2}. \quad \{ f_n \}_{n=0}^\infty\\
		\begin{cases} 
			f_0=1,f_1=1 \\
			f_n = f_{n-1} + f_{n-2},  \quad  \forall n \ge 2
		\end{cases}
		$
	\end{proof}

\subsection{Производящие функции}

$ \{ a_n \}_{n=0}^\infty $\\
$ \displaystyle \sum_{n=0}^\infty a_n t^n = A(t)$ - производящая ф-ия последовательноси $ \{ a_n \}_{n=0}^\infty$. $A(t)$ - это как бэ не ф-ия от $t$, мы знаем только что $A(0) = a_0$.\\

\subsubsection{Элементарная производящая ф-ия}
\begin{enumerate}
	\item $ \displaystyle  (1+T)^\alpha = \sum_{n=0}^\infty \binom{\alpha}{n} t^n$
	\item $ \displaystyle  e^t = \sum_{n=0}^\infty \frac{t^n}{n!} $
	\item $ \displaystyle \ln\left(\frac{1}{1-t}\right) = \sum_{n=1}^\infty \frac{t^n}{n} $
	\item $ \displaystyle  \sin(t) \sum_{n=0}^\infty (-1)^n \frac{f^{2n+1}}{(2n+1)!} $
	\item $ \displaystyle  \cos(t) \sum_{n=0}^\infty (-1)^n \frac{f^{2n}}{(2n)!} $
\end{enumerate}
\subsubsection{Сво-ва производящих ф-ий}
Пусть $A(t)$ и $B(t)$ - производящие ф-ии послед. $\{ a_n \}_{n=0}^\infty$ и $\{ b_n \}_{n=0}^\infty$ соотвтественно. Тогда:
\begin{enumerate}
	\item $ \alpha A(t) = \beta B(t)$ -  производящая ф-ия. $ \{ \alpha a_n + \beta b_n \}_{n=0}^\infty $.
	\item $ A(t)\cdot B(t)$ - производ. ф-ия послед. $ \{ d_n \}_{n=0}^\infty, d_n = a_0b_n + a_1b_{n-1} +  \ldots  + a_nb_0$
	\item $ t^m A(t)$ - производящ. ф-ия. $ \underset{m}{\underbrace{0, \ldots ,0}} a_0, a_1, \ldots $
	\item $ A(ct)$ - про-щая ф-ия послед. $\{ c^n a_n \}_{n=0}^\infty $
	\item $ tA'(t)$ - $\{ n\cdot a_n \}_{n=0}^\infty $
	\item $ \displaystyle \int_{0}^t \frac{A(t)-a_0}{t}dt$ - производящая ф-ия послед. $ \displaystyle \left\{ \frac{a_n}{n} \right\}_{n=1}^\infty $
	\item $ \displaystyle \frac{A(t)}{1-t}$ - производящая ф-ия послед. $ \displaystyle \left\{ \sum_{i=0}^n a_i \right\}_{n=0}^\infty $
\end{enumerate}

\subsubsection{Лемма 12}
	$ A(t)$ - про-щая ф-ия послед. $ \{ a_n \}_{n=0}^\infty, a_0\ne 0$. Тогда $\exists!$ производящ. ф-ия $B(t)$ послед. $\{ b_n \}_{n=0}^\infty$. $A(t)\cdot B(t) = 1$.
	\begin{proof}\hfil\\
		Опред. коэффициент $B(t)$ послед. $b_n = \frac{1}{a_0}$ если определены $b_0, b_1, b_2,  \ldots, b_{n-1}$.\\
		$a_0b_n + a_1b_{n-1} +  \ldots  + a_nb_0$ - неизвестен только $b_n$, который мы можем найти.
	\end{proof}

\subsubsection{Применение производящих ф-ий}
\paragraph{Пример}
	$ \displaystyle (1+t)^n = \sum_{s=0}^\infty \binom{n}{s} t^s \\
	(1+t)^m = \sum_{s=0}^\infty \binom{m}{s} t^s \\
	(1+t)^{n+m} = (1+t)^n(1+t)^m $\\
	Приравнием коэффициенты при $t^k$:\\
	$ \displaystyle \binom{n+m}{k} = \sum_{s=0}^k \binom{n}{s} \cdot \binom{m}{k-s}$
\paragraph{Упражнение}
	$ \displaystyle \sum_{k=0}^{n} \binom{m}{k} \cdot \binom{m}{n-k}(-1)^k = 
		\begin{cases} 
			0 \text{, если $n$ - нечётно} \\
			(-1)^{^n/_2} \binom{m}{^n/_2} \text{, если $n$ - чётно}
		\end{cases}$
		
\subsubsection{Лемма 13}
	Производящая ф-ия для $ \displaystyle  \{ P(n) \}_{n=0}^\infty, \quad A(t) = \prod_{i=1}^\infty (1-t^i)^{-1}$.
	\begin{proof}\hfil\\
		$ \displaystyle  (1-t^i)^{-1} = 1 + t^i + t^{2i} +  \ldots \\
		A(t) = \prod_{i=1}^\infty (1-t^i)^{-1} = \prod_{i=1}^\infty (1 + t^i + t^{2i} +  \ldots )$\\
		При $t^n$: $ \displaystyle \sum_{ j_1, \ldots ,j_n \ge 0 \setminus n 1j_1+2j_2+ \ldots +nj_n=n} 1 = P(n)$.
	\end{proof}

\subsubsection{Лемма 14}
	Производящая ф-ия для $ \displaystyle  \{ c_n \}_{n=0}^\infty$ есть $ \displaystyle C(t) = \frac{1-\sqrt{1-4t}}{2t}$
	\begin{proof}\hfil\\
		$ \displaystyle C(t) = \sum_{n=0}^\infty C_n t^n = 1 + \sum_{n=1}^\infty (C_0C_{n-1} +  \ldots  + C_{n-1}C_0)t^n =
		1 = t(C(t))^2$\\
		$ t\cdot (C(t))^2 - C(t) + 1 = 0\\
		C(t) = \frac{1 \pm \sqrt{1-4t}}{2t}\\
		C(0) = 1.$
		
		$ \displaystyle (1-4t)^{^1/_2} = \sum_{n=0}^\infty \binom{^1/_2}{n} (-4t)^n = \\
		= 1 + \sum_{n=1}^\infty \frac{ (^1/_2)(-^1/_2)(-^3/_2) \ldots (-^{2n-3}/_2)}{n!}(-4t)^n =\\
		= 1 - \sum_{n=1}^\infty \frac{3\cdot5\cdot7\cdot \ldots \cdot(2n-3)}{n!} 2^nt^n =\\
		= 1 - \sum_{n=1}^\infty \frac{(2n-2)!}{n!(n-1)!}2t^n\\
		C(t) \frac{1}{2t} \sum_{n=1}^\infty \frac{(2n-2)!}{n!(n-1)!}2t^n =
		\sum_{n=1}^\infty \frac{(2n-2)!}{n!(n-1)!}t^{n-1} =
		\sum_{n=0}^\infty \frac{(2n)!}{(n+1)!n!} t^n\\
		c_n = \frac{(2n)!}{(n+1)!n!}
		$
	\end{proof}

%\end{document}