%\documentclass{article}

%\usepackage[utf8]{in%putenc}
%\usepackage[TS1,T2A]{fontenc}
%\usepackage[russian]{babel}
%\usepackage{amsmath}
%\usepackage{amsfonts}
%\usepackage{amssymb}
%\usepackage{amsthm}
%\usepackage{graphicx}
%\DeclareGraphicsExtensions{.png,.jpg,.pdf}


%\hoffset=-3cm
%\textwidth=18cm
%\voffset=-3cm
%\textheight=26cm

%\date{2010-02-12}
%\title{Дискретка}
%\author{Зайцев Вадим}

%  Пережогин Алесей Ловович

%\begin{document}
%\maketitle

\section{Комбинаторика}

\subsubsection{Правило произведенеия}
	Если элемент $a \in A$ мы можем выбрать $n$ способами и после каждого такого выбора элемент из
	$b \in B$ можем выбрать $m$ способами, то пары $ab$ мы можем выбрать $n\cdot m$ способами.
	$| X_1 \times \ldots \times X_n| = |X_1| \times \ldots \times |X_n|$.\\
	В $n$-мерном векторном про-ве над $GF(p)$ есть $p^n$ элементов. (Двоичных векторов длины $n$
	будет $2^n$ штук).
	
\subsubsection{Опр} Выборка семействава элементовв $a_{i_1},\ldots, a_{j_k}$ из $A=\{a_1,,... a_n\}$
	назовем выборкой объема $K$ из $n$ элементов.
	
\begin{enumerate}
	\item \textbf{Упорядоченная выборка объема $K$ из $n$ элементов без повторений}.\\
	$(n,k)$ - перестановка, $A(n,k)$ - число таких выборок.
	\paragraph{Лемма 1:}
		$A(n,k) = n \cdot (n-1) \cdot (n-2) \ldots (n-k+1) = [n]_k$.
	\paragraph{Док-во:} очевидно :).\\ \\
		$ \forall x \in \mathbb{R}:\quad [x]_k = x\cdot(x-1)\cdot\ldots\cdot(x-k).\quad
		k \in \mathbb{Z}, k\ge 0$ т.к. мы должны иметь целое кол-во скобок, равное $k$.\\
		$ [x]_0 = 1,\quad [n]_n=n!$.
	\paragraph{Пример:}
		$(3,2)$-перестановки: $ab, ac, ba, bc, ca, cb$.
		
	\item \textbf{Упорядоченная выборка объема $K$ из $n$ элементов с повторениями}.
		$\widehat{A}(n,k)$\\
	\paragraph{Лемма 2:}
		$\widehat{A}(n,k)=n^k$. Док-во очевидно.
	\paragraph{Пример:}
		$\widehat{A}(3,2)=9$. В отличие от предыдущего, могут быть повторения: $aa, bb, cc$.
		
	\item \textbf{Неупорядоченные выборки объема $K$ из $n$ элементов без повторений}. $(n,k)$ -
		сочетания. Обозн. $С(n,k)$.\\
		$(3,2)$-сочетания: $ab, ac, bc. \, C(3,2)=3.$\\
		$\displaystyle C(n,k) = \frac{[n]_k}{k!} = \binom{n}{k}=C_n^k = \frac{n!}{k!(n-k)!},\quad
		x \text{ может быть из } \mathbb{R}$.
	\paragraph{Док-во:} $\displaystyle С(n,k) = \frac{A(n,k)}{k!} = \frac{[n]_k}{k!}$. ч.т.д.\\ \\
	$\displaystyle \binom{n}{k} = 0, \text{ при } k>n$
	
	\paragraph{Пример: }Число двоичных векторов длины $n$ с $k$ единицами равно числу $k$-элементных
		подмножеств $n$-элементного мно-ва и равно $\binom{n}{k}$. $((x_1,\ldots,x_n) \in \{0,1\}^n$
		, $\{0,1\}^n$ - число двоичных картежей/наборов - как больше нравится).
	
	\item \textbf{Неупорядоченные выборки объема $k$ из $n$ элементов с повторениями}.
		Обозначим $\widehat{C}(n,k)$\\
		$\widehat{C}(3,2)=6$ (предыдущие $ab, ac, bc$ плюс повторения $aa, bb, cc$).
		\paragraph{Лемма 4:} $\displaystyle \widehat{C}(n,k) = \binom{n+k-1}{n-1}$
		\paragraph{Док-во:}\hangindent=2.73cm
			Давайте построим биекцию с множеством, кол-во элементов которого мы можем посчитаь.\\
			$ r_1,\ldots, r_n$ - где $r_i$ - число вхождений $a_i$ в выборку.\\
			$ \sum r_i = k, \quad r_i \ge 0$ \\
			Рассмотрим двоичный картеж, у которого: $ \underbrace{0\ldots0}_{r_1} 1
			\underbrace{0\ldots0}_{r_2} 1 \ldots 1 \underbrace{0\ldots0}_{r_n}$ - длина $n+k-1$,
			единиц $n-1$.\\
			Получаем биекцию между неупорядоченными выборками по $k$ из $n$ элементов без повторений
			и двоичных картежей для $(n+k-1)$ c $(n-1)$ единицами.\\
			Получаем $\displaystyle \binom{n+k-1}{n-1}$ ч.т.д.
\end{enumerate}

\subsection{Бином Ньютона}
	$ \displaystyle \forall n \in \mathbb{N} \quad (a+b)^n = \sum_{k=0}^n \binom{n}{k}a^kb^{n-k}$.\\
	Следущие вещи верны $ \forall n,k \in N, \quad k\le n$\\
	\begin{enumerate}
		\item $ \displaystyle \binom{n}{k} = \binom{n}{n-k} $
		\item $ \displaystyle \text{тождество Паскаля:}\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$
		\item $ \displaystyle \sum_{k=0}^n \binom{n}{k} = 2^n $
		\item $ \displaystyle \sum_{k=0}^n (-1)^k\binom{n}{k} = 0 $
		\item \textbf{Лемма 6: (тождества Вандермонда):}
			$\displaystyle\forall n,m\mid k\le n, \, k\le m\quad
			\binom{n+m}{k}=\sum_{s=0}^n \binom{m}{s}\cdot\binom{n}{k-s}$ \\
			\paragraph{Док-во}: \hangindent=2cm \\
%				\includegraphics[width=100px, height=50px]{2010-02-12_1}
		\item\textbf{Лемма 7: }$\displaystyle\forall n\in N\binom{2n}{n}=\sum_{k=0}^n\binom{n}{k}^2$
		\paragraph{Док-во:} $ \displaystyle \binom{2n}{n} = \binom{n+n}{n} = \sum_{k=0}^n 
			\binom{n}{k} \binom{n}{n-k} = \sum_{k=0}^n \binom{n}{k}^2$ ч.т.д.
	\end{enumerate}
	
\paragraph{Пример} 5 ручек, 7 карандашей. Можем выбрать 1 предмет. 12 вариантов :)
\subsubsection{Правило суммы} Если из $A$ можно выбрать $n$ способами, из $B$ можно выбрать $m$
	способами. Из $A$ или $B$ можно выбрать $n+m$ способами.\\
	$\forall$ разбиения мно-ва $S$ на $S_1 \cup S_2 \cup S_2 \ldots \cup S_n,\quad\forall i\neq j \,
	S_i \cap S_j = \varnothing:\quad |S| = |S_1| + \ldots + |S_n| $.
\paragraph{Пример:} тождество Паскаля (1.1.2).
\paragraph{Док-во:}\hangindent=1.73cm
	разобъем мно-во всех $(n,k)$-сочетаний на 2 мно-ва:
	\begin{enumerate}
		\item Елемент $a$ попал в наше сочетание $\Rightarrow$ один уже есть, из осташвихся $n-1$
			выбираем нужные $k-1$.
		\item Елемент $a$ не попал в сочетание.
	\end{enumerate}
	$(1)+(2)$ = всем сочетаниям = $\displaystyle \binom{n-1}{k-1} + \binom{n-1}{k} =\binom{n}{k}$.\\
	
	
	$ |S_1 \cup ... \cup S_2|,\quad S_i <= S \leftarrow $ это интересная строчка, которую я так и не
	понял, к какому пункту лучше отнести \ldots \footnote{ наверное, всё-таки к нижнему \ldots }. \\
\subsubsection{Лемма 8:}
	$ |A \cup B| = |A| + |B| - |A \cap B|$.
	\paragraph{Док-во}: \hangindent=5cm \\
%	\includegraphics[width=100px, height=50px]{2010-02-12_2}
	
\subsubsection{Лемма 9:}
	$|A\cup B\cup C| = |A| + |B| + |C| - |A\cup C| - |A \cup B| - |B \cup C| + |A \cup B \cup C|$.\\
	Док-во картинкой:\\
%	\includegraphics[width=100px, height=50px]{2010-02-12_3}
	
\subsubsection{Теорема 1: формула включений-исключений}
	Пусть $A$ - конечное конечное мно-во, $A_1 \ldots A_n \subseteq A$.
	Тогда $ \displaystyle |A \setminus (A_1 \cup \ldots \cup A_n)| = \sum_{k=0}^n S_k,\\
	S_k = \sum_{\{ i_1 \ldots i_k\} \subseteq \{1\ldots n\}} |A_i \cap\ldots\cap A_k| $\\
	$ |S\setminus (A \cup B \cup C) | = S_0(|S|) - S_1(|A|+|B|+|C|) + S_2(|A \cap B| + |B \cap C| + 
	|A \cap C|) - S_3(|A \cap B \cap C|) $.
\begin{proof}
	\textit{Первый способ:} инудкция по $n$ - д.з.
\end{proof}
\begin{proof}
	\textit{Второй способ:} $ x \in A$ - рассмотрим вклад $x$ в левую и правую часть неравенства.
	\begin{enumerate}
		\item $x \in A\setminus (A_1 \cup \ldots \cup A_n) $\\
			слева дает 1. справа только в $S_0$, т.е. 1 раз.
		\item $x \in (A_1 \cup \ldots \cup A_n) $\\
			слева дает 0. Пусть $x$ встречается ровно в $t$ множествах $A_{i_1} \ldots A_{i_t}$,
			в $S_0$ он встретися 1 раз\\
			в $S_1$ он встретится $t$ раз\\
			в $\displaystyle S_2:\sum_{1\le j_1< j_2 \le n}|A_{j_1}\cap A_{j_2}|=\binom{t}{2}$ раз\\
			в $\displaystyle S_3:\binom{t}{3}\\\vdots \\$ в $\displaystyle S_t:\binom{t}{t}=1$ раз\\
			Всего справа он встречатеся $ \displaystyle 1 - t + \binom{t}{2} - \binom{t}{3} \ldots +
			(-1)^t \binom{t}{t} = \sum_{j=0}^t (-1)^i\binom{t}{i} \overset{\text{по тождеству 4}}{=}
			0 $. ч.т.д.
	\end{enumerate}
\end{proof}

\subsubsection{Задача о беспорядках}
	$ \pi = (\pi_1, \ldots ,\pi_n) $ - перестановка $(1,\ldots,n)$.\\
	Нужно найти число перестановок из $n$ эл-ов мно-ва, в котороых никакой эл-т не остался на мсте.
	\begin{proof}
	($\forall i \quad \pi_i \not= i$).\\
	$A$ - все перестановки. $\forall i \quad A_i \leftrightarrow \pi_i = i $.\\
	$ A \setminus (A_1 \cup \ldots \cup A_n)$ - искомое мно-во.\\
	$ |A| = n! \Rightarrow S_0 = n!$\\
	$ |A_i| = (n-1)! $\\
	$ \displaystyle S_i = \sum_{i=1}^n |A_i| = n\cdot(n-1)!$\\
	$ |A_i \cap A_j| = (n-2)!$\\
	$ \displaystyle S_2 = \sum_{1 \le i < j \le n}  |A_i \cap A_j| = \sum_{1\le i < j\le n} (n-2)! =
	\binom{n}{2} (n-2)! $ \\
	$ | A_{i_1} \cap \ldots A_{i_k} | = (n-k)! $\\
	$ \displaystyle S_k = \sum_{1 \le i_1 < \ldots < i_k \le n} (n-k)! = \binom{n}{k} (n-k)! $\\
	$ \displaystyle | A\setminus(A_i \cup \ldots \cup A_n)| = \sum_{k=0}^n (-1)^k S_k = \sum_{k=0}^n
	(-1)^k \binom{n}{k}(n-k)! = \sum_{k=0}^n(-1)^k\frac{n!}{(n-k)!k!} (n-k)! = n!\sum_{k=0}^n \frac{
	(-1)^k}{k!} $
	\end{proof}

%\end{document}