%\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

\subsection{Функция Эйлера}
$ \varphi(m)$ - ф-ия Эйлера, $m \in N$. Кол-во натуральных чисел, не превосходящих $m$ и взаимно простых с $m$.

\subsubsection{Теорема 2}
	$\displaystyle \forall m \ge 2\quad m=p_1^{l_1}\cdot \ldots \cdot p_n^{l_n}$ - разложение на простые множители,тогда
	$\displaystyle \varphi(m)=m \prod_{i=1}^n\left(1-\frac{1}{p_i}\right)$
	\begin{proof}
		$A=\{1\ldots m\}\\
		A_1$ - числа $A$, которые дляется на $p_i$, $\forall i=1\ldots m$\\
		$|A\setminus (A_1 \cup \ldots \cup A_n|$\\
		$\displaystyle |A| = m \quad \Rightarrow \quad S_0 = m\\
		|A_i| = \frac{m}{p_i} (p_i, 2p_i, 3p_i, \ldots, \frac{m}{p_i}\cdot p_i)\\
		S_1 = \sum_{i=1}^m \frac{m}{p_i} = \sum_{i=1}^n |A_i|\\
		|A_{i_1} \cap \ldots \cap A_{i_k}| = \frac{m}{p_{i_1} \ldots p_{i_k}}\\
		S_k = \sum_{i\le i_1 < \ldots < i_k \le n}\frac{m}{p_{i_1} \ldots p_{i_k}}\\		
		|A \setminus (A_1 \cup \ldots \cup A_n)| = m + \sum_{k=1}^n(-1)^k S_k = 
		m + \sum_{k=1}^n (-1)^k S_k =
		m + \sum_{k=1}^n (-1)^k \sum_{1\le i_1< \ldots <i_k\le n} \frac{m}{p_{i_1} \ldots p_{i_k}} =
		- (some letters) ... + (-1)^n \frac{m}{p_1 ... p_n}
		= m - \sum_{i=1}^n \frac{m}{p_i} + \sum_{1\le i<j \le n} \frac{m}{p_i p_j} =\\
		= m\cdot(1-\frac{1}{p_1})\cdot(1-\frac{1}{p_2})\cdot...\cdot(1-\frac{1}{p_n})$
	\end{proof}
 
\subsubsection{Теорема 3}
	Число сюрьективных отображение $ \displaystyle f : X \rightarrow Y, \quad |X| = n,  \, |Y|=k$, равно $ \displaystyle
	(-1)^k \sum_{i=1}^k (-1)^i\binom{k}{i}\cdot i^n$
	\begin{proof}
		$A$ - все отображения $X \rightarrow Y, \quad Y=\{y_1,  \ldots ,y_k\}$ \\
		$ A_i $ - все отображения $X \rightarrow Y \mid y_i$ - нет проообраза.\\
		$ A \setminus (A_1 \cup ... \cup A_k)$ - мно-во всех отображений, у которых 1-й элемент покрыт, ..., k-й элемент
		покрыт.\\
		$ \displaystyle |A| = k^n\\
		|A_i| = (k-1)^n\\
		|A_{i_1} \cap  \ldots  \cap A_{i_t}| = (k-t)^n\\
		S_t = \sum_{1\le i_1 <  \ldots  < i_t \le k} (k-t)^n = \binom{k}{t}(k-t)^n\\
		|A \ (A_1 \cup \ldots \cup A_k)| = \sum_{t=0}^k (-1)^t \binom{k}{t}(k-t)^n \, \overset{k-t=i}{=} \, \sum_{i=0}^k (-1)^
		{k-i}\binom{k}{i}i^n$
	\end{proof}

\subsection{Числа Стирлинга}
	Число Стирлинга II рода $S(n,k)$ - кол-во неупорядоченных разбиений n-элементного мно-ва на k непустых подмно-в.\\
	$\{1,2,3,4\}\quad S(4,2) = \{1\}\{2,3,4\}, \{2\}\{1,2,3\}, \{3\}\{1,2,3\}, \{4\}\{1,2,3\}, \{1,2\}\{3,4\}, \{1,3\}\{2,4\}, \{1,4\}\{2,3\} = 7$.\\
	Очевидно что $\forall n \in N,\quad S(n,1)=1,  \quad S(n,n) = 1,  \quad S(n,k)=0 \text{ при } k>n$.\\
	Полагаем, что $S(0,0) = 1,  \quad  S(n,0)=0, \, n>0$.

\subsubsection{Теорема 4}
	$\forall k,n \in N,  \quad 0 < k < n\quad S(n,k) = S(n{-}1, k{-}1)+k\cdot S(n{-}1,k)$, что очень напоминает ф-лу для
	биномиальнго коэффициента $  \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.
	\begin{proof}
		Все разбиения разделим на 2 неперсекающихся мно-ва:
		\begin{enumerate}
			\item $n$ - одноэлементное подмно-во. Количество $\{n\}, S(n{-}1,k{-}1)$
			\item все остальные. Количество? Разобьём все оставшиеся на k подмно-в: $S(n{-}1,k) \cdot k$ - надо засунуть
			n-й элемент. (где k - кол-во множеств, откуда мы можем взять этот самый элемент).
		\end{enumerate}
		По правилу суммы: $S(n,k) = S(n-1, k-1) + kS(n-1,k)$.
	\end{proof}

\subsubsection{Теорема 5}
	$ \displaystyle \forall k \ge 2, n\ge k,\quad S(n,k)=\sum_{i=k-1}^{n-1} S(i,k-1)\binom{n-1}{i}$.
	\begin{proof}
		Разобъем все разбиения на подмно-ва по параметру $S$. $S$ - мощность подмно-ва, куда попал элемент $n$. $1 \le S
		\le n-k+1$, т.к. к-1 эл-н надо будет ещё куда-нить засунуть.\\
		Способов выбрать подмно-во, куда засунем $n$: $\binom{n-1}{s-1}$. $S(n-s,k-1)$ - разбить остальные.\\
		Способов разбить $n$ на $k$ непустых подмножеств, таких  что  $n$  попал в $s$-элементое подмножество получилось
		$\binom{n-1}{s-1} \cdot S(n-s,k-1)$.
		Получаем $ \displaystyle S(n,k) = \sum_{s=1}^{n-k+1} \binom{n-1}{s-1}  \cdot S(n-s,k-1) \, \overset{n-s=i}{=} \,
		\sum_{i=k-1}^{n-1} \binom{n-1}{n-i-1 (=i)}S(i, k-1)$.
	\end{proof}

\subsubsection{Теорема 6}
	$ \displaystyle S(n,k) = \frac{(-1)^k}{k!} \sum_{i=1}^{k}(-1)^i \binom{k}{i}i^n $
	\begin{proof}
		Число сюрьективных отображений $ X \rightarrow Y, |X| = n, |Y| = k $. Каждое такое отображение отображает: \\ $x
		=\begin{cases} \{ \} \rightarrow y_1 \\ \{ \} \rightarrow y_2 \\ \ldots \\ \{ \} \rightarrow y_k \end{cases}$.\\
		Это число - есть количество упорядоченных разбиений $n$-элементного множества на $k$ непустых подмножеств. А нам
		нужно найти число неупорядоченных разбиений. В общем, хрень какая-то, но по теореме 3 всё доказано
	\end{proof}

\subsection{Числа Белла}
	Обозначим $B_n$ - кол-во неупорядоченных разбиений $n$-элементного мно-ва на непустые подмно-ва. $$ B_n =\sum_{k=1}^
	{n} S(n,k) $$
	
\subsubsection{Теорема 7}
	$ \displaystyle  B_n = \sum_{0}^{n-1} \binom{n-1}{i} B_i$
	\begin{proof}
		$ \displaystyle B_n  =  \sum_{k=1}^{n}  S(n,k) \stackrel{\text{теорема 5}}{=}  \sum_{k=1}^{n} \sum_{i=k-1}^{n-1}
		S(i,k-1)\binom{n-1}{i} = \\ = 
		\sum_{i=0}^{n-1} \sum_{k=1}^{i+1} S(i,k-1) \binom{n-1}{i} \overset{k-1=t}{=}
		\sum_{i=0}^{n-1} \sum_{t=0}^i S(i,t) \binom{n-1}{i} = 
		\sum_{i=0}^{n-1} \binom{n-1}{i}B_i$
	\end{proof}
	

\subsection{Число Стирлинга первого рода}
	$s(n,k)$ - число перестановок мно-ва {1,...,n}, в циклическом представлении которых ровно к циклов.\\
	$ \displaystyle \binom{1, 2, 3, \ldots, n}{\pi_1, \pi_2,\pi_3, \ldots, \pi_n}. \quad 1 \rightarrow \pi_1 \rightarrow
	\ldots$\\
	$ s(4,2) = 11 ([1][2,3,4], [1][2,4,3], [2][1,3,4], [2][1,3,4], [3][1,2,4], [3][1,4,2], [4][1,2,3], [4][1,3,2], [1,2]
	[3,4], [1,3][2,4], [1,4][2,3])$.
	Положим $s(0,0) = 1, \quad s(n,0) = 0,  \, n>0\quad s(n,k)=0, k>n$.
	
\subsubsection{Лемма 10:}
	\begin{enumerate}
		\item $s(n,1) = (n-1)!$
		\item $s(n,k) \ge S(n,k)$
		\item $s(n,n) = S(n,n) = 1$
		\item $s(n,n-1) = S(n,n-1) = \binom{n}{2}$
		\item $ \displaystyle \sum_{k=1}^{n} s(n,k) = n!$
	\end{enumerate}
	\begin{proof}
		Домашнее задание :'(
	\end{proof}

\subsubsection{Теорема 8}
	$ \forall n,k, \,  0<k<n\quad s(n,k) = s(n-1, k-1) + (n-1)s(n-1,k)$
	\begin{proof}
		аналогично :'(. (Говорят, похоже на числа Стирлинга второго рода)
	\end{proof}

\subsubsection{Некоторые факты (вступление к 9-й теореме)}
$[x]_k = x\cdot(x-1)\cdot\ldots\cdot(x-k+1)$ - как мы знаем, это ``укороченный'' факториал длины $k$.\\
$x^1 = [x]_1\\
x^2 = [x]_2 + [x]_1\\
x^3 = [x]_3 + 3[x]_2  = [x]_1\\
x^4 = [x]_4 + 6[x]_3 + 7[x]_2 + [x]_1\\
x^4 = S(4,4)[x]_4 + S(4,3)[x]_3 + S(4,2)[x]_2 + S(4,1)[x]_1$

\subsubsection{Теорема 9}
	$ \displaystyle  \forall n \in N:\quad x^n = \sum_{k=1}^n S(n,k)[x]_k$.
	\begin{proof}
		$[x]_{k+1} = [x]_k\cdot (x-k) \\
		(*) \quad x\cdot[x]_k = [x]_{k+1} + k\cdot[x]_k$\\
		Индукция по $n$: $x^1 = [x]_1$ - очев.\\
		$ \displaystyle x^n = x\cdot x^{n-1} \overset{ \text{ по индукции } }{=} x \cdot \sum_{k=1}^{n-1}S(n-1,k)[x]_k =
		\sum_{k=1}^{n-1} S(n-1, k)\cdot [x]_{k+1} + \sum_{k=1}^{n-1} S(n-1, k)\cdot k \cdot [x]_k \overset{ t=k+1 \text{
		в первой сумме}}{=}\\= \sum_{t=2}^n S(n-1,t-1) [x]_t + \sum_{k=1}^{n-1} S(n-1, k)\cdot k \cdot [x]_k$
		Первая сумма равно 0 при t=1, вторая сумма равно 0 при k=n. Получается:\\
		$ \displaystyle \sum_{k=1}^n (S(n-1,k-1) + kS(n-1,k)) [x]_k = \sum_{k=1}^n S(n,k) [x]_k$
	\end{proof}
	
\subsubsection{Ещё факты (вступление к 10-й теореме)}
$[x]_{\overline{k}} = x(x+1)\ldots(x+k-1)\\ 
~[x]_{\overline{1}} = x \\
~[x]_{\overline{2}} = x(x+1) = x^2 + x \\
~[x]_{\overline{3}} = x^3 + 3x^2 + 2x \\
~[x]_{\overline{4}} = x^4 + 6x^3 + 11x^2 + 6x \\
~[x]_{\overline{4}} = s(4,4) \cdot x^4 + s(4,3) \cdot x^3 + s(4,2) \cdot x^2 + s(4,1) \cdot x$


%\end{document}