%\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-26}
%\title{Дискретка}
%\author{Зайцев Вадим}
%
%  Пережогин Алесей Ловович
%
%\begin{document}

\subsubsection{Торема 10}
$\displaystyle \forall n \in \mathbb{N}: \quad  [x]_{\overline{n}} = \sum_{k=1}^n s(n, k)x^k$
\begin{proof}
	Индукция по $n$\\
	$ [x]_{\overline{n+1}} = [x]_{\overline{n}} (x+n)$\\
	Аналогично Теореме 9 (1.5.4).
\end{proof}

%$[x]_4 = x^4 - 6x^3 + 11x^2 - 6x$
\subsubsection{Следствие}
	$ \displaystyle  [x]_n = \sum_{k=1}^n (-1)^{n-k} s(n,k) x^k$
	
	
\subsubsection{Теорема 11: Связь между числам Стирлинга}
	$ \displaystyle \forall n,m \in N\quad \sum_{k=1}^n S(n,k)s(k,m)(-1)^{k-m} = \begin{cases}1, \quad n=m \\ 0, \quad n
	\ne m \end{cases}$.
\begin{proof}
	$ \displaystyle x^n = \sum_{k=1}^n S(n,k) [x]_k = \sum_{k=1}^n S(n,k) \sum_{m=1}^k s(k,m)(-1)^{k-m}x^m= \sum_{m=1}^n
	x^m \sum_{k=1}^n S(n,k) s(k,m) (-1)^{k-m}x^m $
\end{proof}

\section{Разбиение чисел}
	Разбиение числа $n$ на натуральные слагаемые - это представление $n$ в виде суммы $x_1 + x_2 +\ldots + x_k,\quad x_i
	\in \mathbb{Z_+}$

\subsection{Упорядоченные разбиния}
	Если фиксировать $k: \displaystyle \quad \binom{n-1}{k-1}$\\
	Если не фиксировать $k: \quad 2^{n-1}$
	
\subsection{Нупорядоченные разбиения}
	$P(n)$ - число неупорядоченных разбиений $n$ на натуральные слагаемые, $P(n,k)$ - на $k$ натуральных слагаемых.\\
	Стандартные формы:\\
	$ \begin{cases} n = x_1+\ldots +x_k\\ x_1 \ge x_2 \ge \ldots \ge x_k \ge 1 \end{cases}$\\
	$P(5) = 7 \quad (4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1+1 = 1+1+1+1+1)$
	
\subsubsection{Теорема 12:}
	$ \displaystyle \forall n,k \mid 0<k<n\\ P(n,k) = \sum_{i=1}^k P(n-k, i)$
\begin{proof}
	$ (*)\quad (n-k) = (x_1 - 1) + (x_2 - 1) + \ldots  + (x_k - 1)\\
	y_i = x_i - 1\\
	n-k = y_1 + y_2 + \ldots + y_k,\quad y_1 \ge y_2 \ge \ldots \ge y_k \ge 0$\\
	Если $s: y_s>0, y_{s+1}=y_{s+2}=\ldots=y_n = 0$, тогда (*) - это разбиение $n-k$ на $k$ слагаемых, которых у нас
	$ P(n-k, s)$.\\
	$ \displaystyle P(n,k) = \sum_{s=1}^k P(n-k, s)$
\end{proof}

$ \displaystyle  P(n) = \sum_{k=1}^n P(n,k)$

\subsubsection{Теорема 13}
	Кол-во разбиений $n$ на различные слагаемые равно кол-ву разбиений $n$ на нечётные слагаемые.
\begin{proof}
	$Q_n$ - мно-во разбиений $n$ на различные слагаемые, $T_n$ - мно-во разбиений на нечётные слагаемые. Докажем, что
	$|Q_n| = |T_n|$, построим для этого биекцию.\\
	$ f: Q_n \rightarrow T_n\\
	n = x_1 + x_2 + \ldots + x_k, \quad x_1 > x_2 > \ldots > x_k\\
	\forall i \quad x_i = x^{t_i} \cdot y_i,\quad y_i \text{ - нечётно}\\
	n = \underbrace{y_1 + \ldots + y_1}_{2^{t_1}} + \underbrace{y_2 + \ldots + y_2}_{2^{t_2}} + \ldots + \underbrace{y_k
	+ \ldots + y_k}_{2^{t_k}}.\\ \\
%
	h: T_n \rightarrow Q_n\\
	n = \underbrace{y_1 + \ldots + y_1}_{d_1} + \ldots + \underbrace{y_s + \ldots + y_s}_{d_s},\quad y_i \ne y_j, i\ne j
	.\\ \forall i\quad d_i \text{ - однозначно раскладывается в степени двойки}.\\
	d_i = 2^{\sigma_{i,1}} + 2^{\sigma_{i,2}} + \ldots + 2^{\sigma_{i,m_i}}, \sigma_{i,1} > \sigma{i,2} > \ldots
	> \sigma_{i, m_i}\\
	n = 2^{\sigma_{1,1}}y_1 + 2^{\sigma_{1,2}}y_1 + \ldots + 2^{\sigma_{i,m_i}} + \ldots + 2^{\sigma_{s,1}} y_s + \ldots
	+ 2^{\sigma_{s,m_s}}y_s.$\\ \\
	$h = f^{-1}$ - биекция.
\end{proof}

\subsubsection{Пример}
	$ 30 = 10 + 7 + 6 + 4 + 3 = 2^1\cdot5 + 2^0\cdot7 + 2^1\cdot3 + 2^2\cdot1 + 2^0\cdot1 = 5 +5+7+3+3+1+1+1+1+3$.
	
\subsubsection{Диаграмма Ферре}
%$n = x_1 + \ldots + x_k,\quad x_1 \ge \ldots \ge x_k \ge 1$\\
Диаграмма Ферре $k$ строчек точек. В $i$-й строке $x_i$ точек, расположенных в первых $x_j$ столбцах.

\subsubsection{Теорема 14}
	$ \forall k,n,\quad 0<k\le n:$
	\begin{enumerate}
		\item $P(n,k)$ равно числу разбиений $n$ на натуральные слагаемые, наибольшее из которых равно $k$.
		\item $P(n+k,k)$ равно числу разбиений $n$ на натуральные слагаемые, не превосходящие $k$.
		\item Число разбиений $n-k$ ровно на $m-1$ слагаемое, не превосходящих $k$ равно числу разбиений $n-m$
			на $k-1$ слагаемое, не превосходящих $m$.
	\end{enumerate}
\begin{proof}
	\begin{enumerate}
		\item упражнение
		\item упражнение
		\item Рассмотрим диаграмму Ферре:
	\end{enumerate}
\end{proof}

\subsubsection{Теорема 15}
	$P_o(n)$ - число разбиений $n$ на чётное число различных слагаемых. (\textit{Прим. Odd - англ. чётный})\\
	$P_e(n)$ - число разбиений $n$ на нечётное число различных слагаемых. (\textit{Прим. Even - англ. нечётный})\\
	Теорема: $P_o(n) - P_e(n) = \begin{cases} (-1)^n, \quad n=\frac{m}{2}(3m\pm1)\\0,\quad\text{в остальных}\end{cases}$
\begin{proof}
	$n = x_1 + x_2 + \ldots + x_k \quad, x_1 > x_2 > \ldots > x_k, \\ x=(x_1,\ldots,x_k)\,
	\alpha(x) = x_k, \quad  \beta(x)$ - наибольшее $j, x_j = x_1 -j + 1$
	\textit{Exmaple: }\\
	
	Преобразуем $x$ следующим образом:
	\begin{enumerate}
		\item $\alpha(x) \le \beta(x)$, тогда отбрасываем $x_k$ и в первых $x_k$ строчках добавляем по дной точке.
			Получим разбиение на различные слагаемые и чётность числа слагаемых измениться.
		\item $\alpha(x) > \beta(x)$, тогда отнимаем в первых $\beta(x)$ строчках по одной точке и строим новую строку длины
			$\beta(x)$.
			\begin{enumerate}
				\item $ n = m+(m+1)+...+(2m-1) = \frac{1}{2}m(3m-1) $
				\item $ n = (m+1)+(m+2)+...+2m = \frac{1}{2}m(3m-1) $
			\end{enumerate}
			$ n \ne \frac{1}{2}m(3m\pm1)\\
			\widehat{P_o} = \widehat{P_e}(n)$.
	\end{enumerate}
\end{proof}

%\end{document}
