discrete_structures.tex

\documentclass[a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[english, russian]{babel}
\usepackage[fleqn]{amsmath}
\usepackage{amsfonts, amssymb, amsthm, mathtools}

\usepackage{mathtools}
\usepackage{fullpage}
\usepackage[colorinlistoftodos]{todonotes}


\title{Дискретные структуры}
\author{MIPT DIHT}

\theoremstyle{plain}
\newtheorem*{theorem-star}{Theorem}
\newtheorem{theorem}{Theorem}
\newtheorem*{lem-star}{Lemma}
\newtheorem{lem}{Lemma}
\newtheorem*{proposition-star}{Proposition}
\newtheorem{proposition}{Proposition}
\newtheorem{statement}{Statement}
\newtheorem*{statement-star}{Statement}
\newtheorem{corollary}{Corollary}
\newtheorem*{corollary-star}{Corollary}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\theoremstyle{definition}
\newtheorem*{definition-star}{Definition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem*{example-star}{Example}

\renewenvironment{proof}{{\bfseries Proof}}{$\bullet$}

\newcommand{\combus}[2]{\left(\begin{smallmatrix}#1 \\ #2 \end{smallmatrix} \right)} % american style for C_n^k
\newcommand{\combru}[2]{C_{#1}^{#2}} % russian C_n^k
\newcommand{\comb}[2]{\combru{#1}{#2}}

\newcommand{\myequat}[1]{\begin{equation} #1 \nonumber \end{equation}}
\newcommand{\pars}[1]{\left( #1 \right)} 
\newcommand{\class}[1]{\left[ #1 \right]} 
\newcommand{\myN}{\mathbb{N}} 
\newcommand{\myZ}{\mathbb{Z}}
\newcommand{\myR}{\mathbb{R}}
\newcommand{\myC}{\mathbb{C}}
\newcommand{\myQ}{\mathbb{Q}}
\newcommand{\myE}{\mathcal{E}} 
\newcommand{\myM}{\mathcal{M}}
\newcommand{\myO}{(1+o(1))}

\newcommand{\mysetP}{\mathcal{P}}
\newcommand{\mysetR}{\mathcal{R}}
\newcommand{\mysetM}{\mathcal{M}}
\newcommand{\mysetN}{\mathcal{N}}
\newcommand{\mysetX}{\mathcal{X}}

\newcommand{\mysum}{\sum\limits}
\newcommand{\myprod}{\prod\limits}
\newcommand{\mylim}{\lim\limits}

\newcommand{\myset}[1]{\left\{ #1 \right\}}

\newcommand{\walls}[1]{\left | #1 \right |} % |smth_vertically_large|
\newcommand{\bra}[1]{\langle #1 \rangle} % brackets for span of vectors, eg. <e_1, ..., e_k>

\begin{document}
\maketitle

\section{Билет №1}
\subsection{Правила комбинаторики: правила сложения, умножения, принцип Дирихле. Формула включения и исключения}

\begin{definition}{Правило сложения}
	\newline
	Если есть два набора объектов, причем в первом $N$ объектов $a_1, \ldots, a_n$, во втором $M$ объектов $b_1, \ldots, b_m$. 
Тогда есть $N+M$ способов выбрать объект либо из первого множества, либо из второго.
\end{definition}

\begin{definition}{Правило умножения}
	\newline
	Если есть два набора объектов, причем в первом $N$ объектов $a_1, \ldots, a_n$, во втором $M$ объектов $b_1, \ldots, b_m$. 
Тогда есть $NM$ способов выбрать объект сначала из первого множества, затем из второго.
\end{definition}

\begin{definition}{Принцип Дирихле}
	\newline
	Если есть $N$ ящиков и $N+1$ кролик, то для любой рассадки кроликов по ящикам найдется ящик, в котором находится не менее двух кроликов.
\end{definition}
\subsubsection{Формула включения-исключения}

Рассмотрим произвольное $N$ объектов $a_1, a_2, \ldots, a_N$. Выделим некоторые свойства $\alpha_1, \alpha_2, \ldots, \alpha_N$, которые могут быть присущи некоторым объектам.

	Пусть $N(\alpha_i)$ "--- количество объектов, обладающих свойством $\alpha_i$, $N(\alpha_i, \alpha_j)$ "--- количество объектов, обладающих свойствами $\alpha_i$ и $\alpha_j$ одновременно.

	$\alpha_i'$ "--- отрицание свойства $\alpha_i$

\begin{theorem}
	$N(\alpha_1', \alpha_2', \ldots, \alpha_3') = N - N(\alpha_1) - N(\alpha_2) - \ldots - N(\alpha_n) + N(\alpha_1, \alpha_2) + N(\alpha_1,\alpha_3) + \ldots + N(\alpha_{N-1}\alpha_N) - N(\alpha_1, \alpha_2,\alpha_3) + \ldots \ldots + (-1)^n N(\alpha_1, \alpha_2, \ldots, \alpha_n)$
\end{theorem}

\begin{proof}
	Докажем индукцией по $n$ \\
	\underline{База индукции:} $\forall N\ \forall\ a_1, \ldots, a_N\ \forall\ \alpha_i N(\alpha_i') = N - N(\alpha_i)$ \\
	\underline{Предположение:} $\forall N\ \forall\ a_1, \ldots, a_N\ \forall\ \alpha_1, \ldots, \alpha_n$ выполняется утверждение теоремы. \\
	\underline{Шаг индукции:} $\forall N\ \forall\ a_1, \ldots, a_N\ \forall\ \alpha_1, \ldots, \alpha_{n+1}$ выполнено утверждение теоремы. \\
	Зафиксируем произвольные $N$, $a_1, \ldots, a_N$, $\alpha_1, \ldots, \alpha_n$. Рассмотрим все из наших объектов, которые обладают свойством $\alpha_{n + 1}$. Обозначим их $\myset{b_1, b_2, \ldots, b_M} \subset \myset{a_1, \ldots, a_N}$, где $M = N(\alpha_{n + 1})$. Применим предположение индукции к объектам $\myset{b_1, \ldots, b_M}$ и свойствам $\myset{\alpha_1, \ldots, \alpha_n}$. $M(\alpha_1', \ldots, \alpha_n') = M - M(\alpha_1) - \ldots - M(\alpha_n) + M(\alpha_1\alpha_2) + \ldots + (-1)^nM(\alpha_1, \ldots, \alpha_n)$. \\
	$N(\alpha_1', \alpha_2', \ldots, \alpha_n', \alpha_{n+1}) = N(\alpha_{n + 1}) - \ldots - N(\alpha_1, \alpha_{n+1}) - \ldots - N(\alpha_n, \alpha_{n + 1}) + \ldots + (-1)^nN(\alpha_1, \ldots, \alpha_n,\alpha_{n+1})$. Применим предположение индукции к множеству $\myset{a_1, \ldots, a_N}$ и свойствам $\myset{\alpha_1, \ldots, \alpha_n}$ $N(\alpha_1',\ldots, \alpha_n') = N - N(\alpha_i) - \ldots + (-1)^nN(\alpha_1, \ldots, \alpha_n)$. \\
	Вычтем полученные утверждения: $N(\alpha_1', \ldots, \alpha_n') - N(\alpha_1', \ldots, \alpha_n', \alpha_{n + 1}) = N(\alpha_1', \ldots, \alpha_n', \alpha{n + 1}') = N - N(\alpha_1) - \ldots - N(\alpha_n) - N(\alpha_{n + 1}) + \ldots + (-1)^{n + 1}N(\alpha_1, \alpha_2, \ldots, \alpha_n, \alpha_{n + 1})$
\end{proof}

Еще один вариант формулы включения-исключения. Рассмотрим множества $S_1, \ldots, S_n$. Тогда $\walls{S_1 \cup \ldots \cup S_n} = |S_1| + |S_2| + \ldots + (-1)^{n + 1} |S_1 \cap S_2 \cap \ldots \cap S_n|$

\subsection{Размещения, сочетания и перестановки. Формула Стирлинга (б/д)}

Пусть $A = \myset{a_1, \ldots, a_n}$. Можно составлять упорядоченные последовательности элементов $A$. А можно извлекать объекты "кучами", то есть без учета порядка. 
Если мы рассматриваем $A$ как упорядоченную последовательность, то говорят о \emph{размещении} объектов. 
Если же мы извлекаем объекты без учета порядка, то говорят о \emph{сочетании} объектов. Бывают размещения с повторениями и без повторений. 
Аналогично, сочетания бывают с повторениями и без повторений.

Будем говорить о $k$-сочетании и $k$-размещении, если в сочетании(размещении) ровно $k$ объектов.

Пусть дано множество объектов $\myset{a_1, \ldots, a_n}$. 
Обозначим через $\overline{A_n^k}$ число всех $k$-размезещений с повторениями и $A_n^k$ число всех $k$-размещений без повторения.
Аналогично обозначим $\overline{C_n^k}$ и $C_n^k$ число $k$-размещений с повторениями и без повторений соответственно.


\section{Билет №2}
\subsection{Размещения, сочетания, перестановки}
Пусть $A = \myset{a_1, \ldots, a_n}$. Можно составлять упорядоченные последовательности элементов $A$. А можно извлекать объекты "кучами", то есть без учета порядка. 
Если мы рассматриваем $A$ как упорядоченную последовательность, то говорят о \emph{размещении} объектов. 
Если же мы извлекаем объекты без учета порядка, то говорят о \emph{сочетании} объектов. Бывают размещения с повторениями и без повторений. 
Аналогично, сочетания бывают с повторениями и без повторений.

Будем говорить о $k$-сочетании и $k$-размещении, если в сочетании(размещении) ровно $k$ объектов.

Пусть дано множество объектов $\myset{a_1, \ldots, a_n}$. 
Обозначим через $\overline{A_n^k}$ число всех $k$-размезещений с повторениями и $A_n^k$ число всех $k$-размещений без повторения.
Аналогично обозначим $\overline{C_n^k}$ и $C_n^k$ число $k$-размещений с повторениями и без повторений соответственно.

\subsection{Формулы для чисел размещения и сочетания с повторениями и без}
\begin{theorem}
	$\overline{A_n^k} = n^k$
\end{theorem}

\begin{proof}
	На первую позицию нашего размещения можно поставить любой и $n$ объектов. Как, впрочем, и на все остальные. Тогда по правилу умножения получаем $n^k$
\end{proof}

\begin{theorem}
	$A_n^k = \frac{n!}{(n-k)!}$
\end{theorem}

\begin{proof}
	На первую позицию нашего размещения можно поставить любой и $n$ объектов. На вторую "--- все, кроме того, который мы поставили на первую позицию, то есть любой из $n-1$ объектов. Иначе говоря, на $i$-тую позицию можно поставить объект $n-i$ способами. То есть $A_n^k = n(n-1)(n-2) \ldots (n-k+1) = \myprod_{i=0}^{k-1} n-i = \frac{n!}{(n-k)!}$
\end{proof}

\begin{theorem}
	$C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}$
\end{theorem}

\begin{proof}
	Каждому $k$-сочетанию без повторений соответствует $k!$ различных размещений без повторения. 
То есть $k! C_n^k = A_n^k$, откуда следует, что $C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}$
\end{proof}

\begin{theorem}
	$\overline{C_n^k} = C^k_{n+k-1}$
\end{theorem}

\begin{proof}
	Рассмотрим исходное множество объектов ${a_1, \ldots, a_n}$. 
Каждому $k$-сочетанию с повторениями поставим в соответствие некоторую последовательность из нулей и единиц.
Ставить в соответствие последовательность из нулей и единиц мы будем по следующему алгоритму: пусть дано $k$-сочетание с повторениями.
Рисуем в нашу последовательность столько единиц, сколько раз нам встретился элемент $a_i$, после этого рисуем ноль, если это не была последний, $n$-ный объект, и так делаем последовательно $n$ раз для каждого $i$ от $1$ до $n$.
Всего у нас в нашей последовательности $k$ единиц, так как каждому элементу, входящему в наше сочетание с повторениями соответствует ровно одна единица и $n-1$ единиц. 
Утвержается, что между такими $0,1$ векторами длины $n-k+1$ с $k$ единицами и сочетаниями с повторениями установилась биекция. 
Но количество таких последовательностей и нулей и единиц это число способов зафиксировать ровно $k$ позиций среди $n-k+1$, а как известно, это количество равно $C_n^k$
\end{proof}

\subsection{Бином Ньютона, полиномиальная формула}
\begin{theorem}{Бином Ньютона}
	$(x+y)^n = \mysum_{k=0}^n = C_n^k x^k y^{n-k}$ 
\end{theorem}

\begin{proof}
	$(x+y)^n = (x+y)(x+y) \ldots (x+y)$. Из каждой скобки надо взять либо $x$, либо $y$. Пусть из $k$ скобок мы взяли $x$, то есть из остальных $n-k$ скобок мы взяли $y$. Но мы выбрать $k$ скобок можем выбрать $C_n^k$ способами, то есть $x^k y^{n_k}$ встречается $C_n^k$ раз, то есть $(x+y)^n = \mysum_k C_n^k x^k y^{n-k}$
\end{proof}

\begin{remark}
	$C_n^k$ также называются биномиальными коэффициентами и в западной традиции пишут $\combus{n}{k}$
\end{remark}

\begin{theorem}{Полиномиальная формула}
	\newline
	$(x_1 + x_2 + \ldots + x_k)^n = \mysum_{(n_1, n_2, \ldots, n_k): n_i \in \myN, \mysum n_i = n}P(n_1,n_2, \ldots, n_k)x_1^{n_1}x_2^{n_2}\ldots x_k^{n_k}$
\end{theorem}

\begin{proof}
	Возьмем $n_1$ скобок из которых извлекается $x_1$, $n_2$ из которых извлекается $x_2$, $\ldots$, $n_k$ скобок, из которых извлекается $x_k$. Очевидно, что $x_i \in \myN, \mysum n_i = n$. Тогда в произведении получится $x_1^{n_1} x_2^{n_2} \ldots x_k^{n_k}$. Этот моном встретится в $P(n_1, n_2, \ldots, n_k)$ раз в качестве слагаемого, т.к. число способов выбрать скобки для $x_1$ равно $\combru{n}{n_1}$, для $x_2$ остается $n-n_1$ свободных скобок, то есть количество способов выбрать $x_2$ равно $\combru{n-n_1}{n_2}$, и так далее. А как известно, произведение таких биномимиальных коэффициэнтов равно $P(n_1, n_2, \ldots, n_k)$.
\end{proof}

\begin{remark} 
	Числа $P(n_1, n_2, \ldots, n_k)$ называются \emph{полиномиальными} коэффициентами
\end{remark}

\subsection{Простейшие тождества. Оценки биномиальных коэффициентов}
\begin{itemize}
	\item $\combru{n}{k} = \combru{n}{n-k}$
	\item $\combru{n}{k} = \combru{n-1}{k} + \combru{n-1}{k-1}$
	\item $\mysum_{i=0}^{n} \combru{n}{i} = 2^n$
		\begin{proof}
			$\mysum_{i=0}^n \combru{n}{i} = (1 + 1) ^ n = 2 ^ n$
		\end{proof}
	\item $\mysum_{(n_1, n_2, \ldots, n_k): n_i \in \myN, \mysum n_i = n}P(n_1,n_2, \ldots, n_k) = k^n$
	\item $\mysum_{i=0}^{n}(\combru{n}{i})^2 = \combru{2n}{n}$	
		\begin{proof}
			$A = \myset{a_1, \ldots, a_{2n}}$. $V$ "--- множество всех $n$ - сочетаний из $A$. $|V| = \combru{2n}{n}$. $V = \bigsqcup\limits_{i=0}^n V_i$, где $V_k$- множество тех $n$-сочетаний, которые содержат ровно $k$ из первых $n$ элементов, то есть $\combru{n}{k}$ спобосов выбрать $k$ элементов из первых $n$ элементов и $\combru{n}{n-k}$ способов выбрать оставшиеся $n-k$ элементов из последних $n$ элементов. То есть $|V_k| = \combru{n}{k}\combru{n}{n-k} = (\combru{n}{k})^2$. 
			$|V| = \sum |V_i| \Leftrightarrow \combru{2n}{n} = \mysum_{i=0}^{n}(\combru{n}{i})^2$
		\end{proof}
	\item $\forall n,m:\ \combru{n+m}{n} = \mysum_{i=n-1}^{n+m-1} \combru{i}{n-1}$
		\begin{proof}
			Рассмотрим $A = \myset{a_1, \ldots, a_n, a_{n+1}}$. $V$ "--- множество всех $m$-сочетаний с повторениями из $A$. $|V| = \combru{n+1+m-1}{m} = \combru{n+m}{m}$. Пусть $V_k$ это те сочетания из $V$, в которые объект $a_1$ входит ровно $k$ раз. Осталось оценить $|V_k|$. В любое сочетание из $V_k$ $k$ раз встречается элемент $a_1$ и в этом сочетании еще есть $m-k+1$ "свободных" мест, на котором стоят остальные $n$ элементов. То есть количество элементов в $V_k$ равно количеству с$m-k+1$-ccочетаний с повторениями их $n$ элементов. То есть $|V_k| = \combru{}{}$ %TODO
		\end{proof} 
		\begin{corollary}
			Если мы возьмем $n = 1$ и подставим в тождество, то мы получим $\combru{m+1}{1} = \combru{m}{0} + \combru{m-1}{0} + \ldots + \combru{0}{0}$
		\end{corollary}
		\begin{corollary}
			Если $n = 2$, то $\combru{m+2}{2} = \combru{m+1}{1} + \combru{m}{1} + \ldots + \combru{1}{1} \Leftrightarrow \frac{(m + 2)(m + 1)}{2} = (m + 1) + m + (m - 1) \ldots 1$
		\end{corollary}
		\begin{corollary}
			Если $n = 3$, то $\combru{m+3}{3} = \combru{m+2}{2} + \combru{m+1}{2} + \ldots + \combru{2}{2} \Leftrightarrow \frac{(m + 1)(m + 2)(m + 3)}{6} = \frac{9(m + 1)(m + 2)}{2} + \frac{m(m + 1)}{2} + \ldots + \frac{1 \cdot 2}{2} = \frac{1}{2} (1^2 + 2^2 + \ldots + (m + 1) ^ 2) + \frac{1}{2}(1 + 2 + \ldots + (m + 1)) \Rightarrow \frac{1}{2} (1^2 + 2^2 + \ldots + (m + 1)^2) = \frac{(m + 1)(m + 2)(m + 3)}{6} - \frac{1}{4} (m + 1)(m + 2) = \frac{1}{12} (m + 1)(m + 2)(2m + 3)$
		\end{corollary}
\end{itemize}

\section{Билет №3}
\subsection{Формальные степенные ряды. Производящие функции и тождества}
\subsubsection{Формальные степенные ряды}

\begin{definition}
	Назовем $A = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5 + \ldots$ формальным степенным рядом с коэффициентами $\myset{a_i} \in \myR$. 
\end{definition}

\begin{definition}
	Пусть $A$ и $B$ два формальных степенных ряда. Назовем их суммой формальный степенной ряд $C$ с коэффициентами $c_i = a_i + b_i$.
\end{definition}

\begin{definition}
	Пусть $A$ и $B$ два формальных степенных ряда. Назовем их произведением формальный степенной ряд $C$ с коэффициентами $c_i = \mysum_{j=0}^{i} a_j \cdot b_{i - j}$.
\end{definition}

\begin{definition}
	Пусть $A$ и $B$ два формальных степенных ряда. Назовем их отношением формальный степенной ряд $C$, если $A = BC$. 	
\end{definition}

$b_0 c_0 = a_0 \Rightarrow c_0 = \frac{a_0}{b_0}$ \newline
$b_1 c_0 + b_0 c_1 = a_1 \Rightarrow c_1 = \frac{a_1 - b_1c_0}{b_0}$ \newline
$\ldots$ \newline

\subsubsection{Производящая функция}
\begin{definition}
	Пусть есть последовательность чисел $a_0, a_1, a_2, \ldots$. Её производящая функция "--- ряд $a_0 + a_1x + a_2x^2 + \ldots$. Хочется научиться понимать какой смысл принимает это выражение 
\end{definition}

Обозначим 
	$A(x) = \mysum_{i= 0}^{\infty} a_n x^n$

\begin{definition}
	Ряд $A(x)$ имеет значение $A$ в точке $x \in \myR$, если $\mylim_{k \to \infty} \mysum_{n=0}^k a_n x^n = A$.
\end{definition}

Вопрос "--- при каких условиях на $x \in \myR$ такой предел существует.

\begin{theorem} % Без доказательства
	Положим $\rho = \frac{1}{\limsup\limits_{n \to \infty} \sqrt[n]{a_n}}$. Тогда ряд $\mysum_{n=0}^{\infty}a_nx^n$ сходится при всех $x:\ |x| < \rho$.
\end{theorem}

\begin{theorem}
	Пусть $A(x) = \frac{b_0 + b_1x + b_2x^2 + \ldots}{c_0 + c_1x + c_2x + \ldots}$, $c_0 \neq 0, b_0 \neq 0$, и выполнены два следующих условия: все корни знаменателя лежат в $\myR$ (то есть нет комплесных корней) и множество корней числителя и корней знаменателя не пересекается. Тогда ряд $A(x)$ сходится для всеx $x$, таких что $|x|$ меньше наименьшего значения модуля корня знаменателя.
\end{theorem}

\begin{theorem}
	Если $|x| < \rho$. $A'(x) = \mysum_{n=1}^{\infty} a_n n x^{n-1}$
\end{theorem}

\begin{example}
	Найти $\mysum_{k=0}^n k^2 \combru{n}{k} (\frac{1}{3}) ^ k$ \newline
	Возьмем $\myset{\combru{n}{k} (\frac{1}{3})^k}$ и составим её производящую функцию. \newline
	$f(x) = \mysum_{k=0}^n \combru{n}{k}(\frac{1}{3})^k = (1 + \frac{x}{3})^n$ \newline
	$f'(x) = \mysum_{k=1}^n k \combru{n}{k} (\frac{1}{3})^k x^{k-1}$ \newline
	$x f'(x) = \mysum_{k=1}^n k \combru{n}{k} (\frac{1}{3})^k x^k$ \newline
	$(x f'(x))' = \mysum_{k=1}^n k^2 \combru{n}{k} (\frac{1}{3})^k x^{k-1}$ \newline
	$x (x f'(x))' = \mysum_{k=1}^n k^2 \combru{n}{k} (\frac{1}{3})^k x^k$ \newline
	$x (x f'(x))' = x(x \frac{n}{3}(1 + \frac{n}{3})^{n-1})'$ \newline
\end{example}

\begin{example}
	$F_0 = 1, F_1 = 1, F_n = F_{n-1} + F_{n-2}$
	Найдем $\mysum_{n=0}^{\infty} F_n (\frac{1}{2})^n$. \newline
	$xf(x) = F_0x + F_1x^2 + F_2x^3 + \ldots$ \newline
	$x^2f(x) = F_0x^2 + F_1x^3 + F_2x^4 + \ldots$ \newline
	$xf(x) + x^2f(x) = F_1x + (F_0+F_1)x^2 + \ldots + (F_{n-2} + F_{n-1})x^n + \ldots = F_1x + F_2x^2 + \ldots = f(x) - F_0$ \newline
	$xf(x) + x^2f(x) = f(x) - 1 \Rightarrow f(x) = \frac{1}{1-x-x^2}$ Корни знаменателя: $\frac{\sqrt{5}+1}{2}, \frac{\sqrt{5} - 1}{2}$. По теореме о сходимости $|x| < \frac{\sqrt{5} - 1}{2}$
\end{example}


\section{Билет №4}
\subsection{Линейные рекуррентные соотношения с постоянными коэффициентами}

Линейная зависимость порядка $k$: $x_n = a_{n-1} x_{n-1} + \ldots + a_{n-k} x_{n-k}$.

\paragraph{Для$k=2$} 
$a_2 y_{n+2} + a_1 y_{n+1} + a_0 y_n = 0$
\begin{definition}
	Характеристическое уравнение для линейной зависимости порядка $2$ есть $a_2\lambda^2 + a_1\lambda + a_0 = 0$
\end{definition}

\begin{theorem}	
	Пусть у характеристического уравнения есть решение $\lambda_1 \neq \lambda_2$. Тогда
	\begin{itemize}
		\item любая последовательность $y_n = c_1 \lambda_1^n + c_2 \lambda_2^n$, $c_1, c_2 \in \myC$ являются решениями зависимости.
		\item если $y_n$ "--- решение. Тогда $\exists c_1,c_2 \in \myC:\ y_n = c_1 \lambda_1^n + c_2 \lambda_2^n$
	\end{itemize}
\end{theorem}

\begin{proof}\\
	\begin{itemize}
		\item Подставим и получим равносильность утверждения и характеристического уравнения. 
		\item Пусть $y_0, y_1, \ldots, y_n,  \ldots$. Рассмотрим уравнения $c_1 + c_2 = y_0$, $c_1\lambda_1 + c_2\lambda_2 = y_1$ c неизвестными $c_1, c_2$. Так как $\lambda_1 \neq \lambda_2$, то у этой системы есть решения. Пусть $c_1^*, c_2^*$ "--- решения этой системы. Рассмотрим последовательность $y_n^* = c_1^* \lambda_1^n + c_2^*\lambda_2^n$.
	\end{itemize}
\end{proof}

\begin{theorem}
	Пусть у характеристического уравнения $\lambda_1 = \lambda_2 = \lambda$. Тогда для любое решение представимо в виде $y_n = (c_1n + c_2) \lambda^n$, и для любых $c_1,c_2$ $y_n = (c_1n + c_2) \lambda^n$ есть решение
\end{theorem}

\begin{proof}
	Доказательство аналогично.
\end{proof}

\paragraph{Общий случай}
$a_k\lambda^k + a_{k-1}\lambda^{k-1} + \ldots + a_0 = 0$ "--- характеристическое уравнение \newline

$\lambda_1, \ldots, \lambda_k \in \myC$ (основная теорема алгебры). 

Обозначим все различные корни через $\mu_1, \ldots, \mu_l$. Пусть 

\begin{theorem}
	Пусть $P_1(n), \ldots P_l(n)$, таких что $P_i(n)$ "--- многочлен с произвольными коэффициентами из $\myC$, имеющий степень $n_i - 1$. Тогда любое $y_n = P_1(n) \mu_1^n + \ldots + P_l(n)\mu_l^n$ "--- решение и любое решение представимо в таком виде.
\end{theorem}
\begin{theorem}[Шевалле]
	Рассмотрим многочлен от $n$ переменных c целочисленными коэффициентами $F(x_1, \ldots, x_n) \equiv 0(p)$. Пусть $V_p$ "--- число различных решений этого сравнения. Если $\deg F < n$, то $V_p \equiv 0(p)$
\end{theorem}


\begin{proof}
	Запишем число решений в виде $\mysum_{x_1 = 1}^p \ldots \mysum_{x_n = 1}^p (1 - F^{p-1}(x_1, \ldots, x_n))$. Действительно, $F(x_1, \ldots, x_n) \equiv 0$ равносильно тому, что $F^{p-1}(x_1, \ldots, x_n) \equiv 0$. Если $F(x_1, \ldots, x_n) \not\equiv 0$, то $F^{p-1}(x_1, \ldots, x_n) \equiv 1$.  

	$\mysum_{x_1 = 1}^p \ldots \mysum_{x_n = 1}^p 1 = p^n \equiv 0$. Осталось доказать, что $\mysum_{x_1 = 1}^p \ldots \mysum_{x_n = 1}^p F^{p-1}(x_1, \ldots, x_n) \equiv 0$.
	
	$F^{p-1}$ ~--- это сумма каких-то одночленов. Каждый из этих многочленов имеет вид $x_1^{a_1}x_2^{a_2}\ldots x_n^{a_n}$, $\mysum a_i \leq (n-1)(p-1)$. 
	Если докажем, что $\mysum_{x_1 = 1}^p \ldots \mysum_{x_n = 1}^p x_1^{a_1}x_2^{a_2}\ldots x_n^{a_n} \equiv 0$, то мы получим, что сумма по всем $F$ сравнима с нулем по модулю $p$. 
	$\mysum_{x_1 = 1}^p \ldots \mysum_{x_n = 1}^p x_1^{a_1}x_2^{a_2}\ldots x_n^{a_n} = (\mysum_{x_1 = 1}^p x_1^{p_1}) (\mysum_{x_2 = 1}^p x_2^{p_2}) \ldots (\mysum_{x_n = 1}^p x_n^{p_n})$.

	Рассмотрим $p = 2$. $a_1 + \ldots + a_n \leq n - 1 \Rightarrow$ по признаку Дирихле есть $a_i = 0$, откуда $\mysum_{x_i = 1}^p x_i^{a_i} = p \equiv 0$.
	
	Рассмотрим $p \leq 3$. Тогда либо есть $a_i = 0$ и все тривиально, либо все $a_i \leq 1$. Но тогда есть $2 \leq a_i \leq p-2$
	Рассмотрим $S = \mysum_{x_i = 1}^p x_i^{a_i}$. $x^{a_i}S = \mysum_{x_i = 1}^p (xx_i)^{a_i}$. $xx_i$ пробегает полуную систему вычетов, то есть $\mysum_{x_i = 1}^p (xx_i)^{a_i} = \mysum_{x_i = 1}^p x_i^{a_i}$. Получается, что $x^{a_i}S = S \Rightarrow S = 0$
\end{proof}

\begin{corollary}
	Пусть степень многочлена $F(x_1, \ldots, x_n)$ от $N$ переменных меньше $n$ и $F(0,0,\ldots, 0) \leq 0$. Тогда существует $x_1, \ldots, x_n$ в котором не все $x_i$ равны $0$, но $F(x_1, \ldots, x_n) = 0$.
\end{corollary}

\begin{statement}
	Пусть $F_1(x_1, \ldots, x_n), \ldots, F_k(x_1, \ldots, x_n)$ ~--- полиномы, $\deg F_1 + \ldots + \deg F_2 < n$. Тогда если система сравнений $F_i(x_1, \ldots, x_n) \equiv 0$ имеет $\pars{0,0,\ldots, 0}$ в качестве решения, то у неё есть ненулевое решение
\end{statement}

\section{Билет №5}
\subsection{Граф, орграф, псевдограф, мультиграф, гиперграф}
\begin{definition-star} Граф ~--- множество вершин и неориентированных рёбер.
\end{definition-star}
\begin{definition-star} Псевдограф ~--- граф с петлями.
\end{definition-star}
\begin{definition-star} Мультиграф ~--- граф с кратными рёбрами.
\end{definition-star}
\begin{definition-star} Дерево ~--- связный ациклический граф. Оно же ~--- граф, в котором любые две вершины соединены ровно одним путём; связный граф, в котором вершин на единицу больше, чем рёбер; ациклический граф,  в котором вершин на единицу больше, чем рёбер.
\end{definition-star}ф, в котором вершин на единицу больше, чем рёбер; ациклический граф,  в котором вершин на единицу больше, чем рёбер.
\begin{definition-star} Гиперграф ~--- множество вершин и рёбер,  каждое ребро ~--- произвольное подмножество вершин.
\end{definition-star}
\begin{definition-star} $k$-однородный гиперграф ~--- каждое ребро содержат ровно $k$ вершин.
\end{definition-star}
\begin{definition-star} $t$-пересекающийся гиперграф ~--- любые 2 ребра гиперграфа имеют хотя бы $t$ общих вершин.
\end{definition-star}

\subsection{Маршруты в графах. Степени вершин}

\subsection{Изоморфизм и планарность графов}
\subsection{Эйлеровы и гамильтоновы циклы в графах}
\begin{definition-star} Эйлеров цикл (цепь) ~--- цикл (цепь), содержащий все рёбра графа.
\end{definition-star}
\begin{definition-star} Эйлеров граф ~--- граф, обладающий эйлеровым циклом.
\end{definition-star}
\begin{definition-star} Гамильтонов цикл (цепь) ~--- цикл (цепь), содержащая все вершины по одному разу.
\end{definition-star}

\subsection{Критерий Эйлеровости. Достаточное условие гамильтоновости.}
\begin{theorem} Связный (мульти)граф является эйлеровым (1) тогда и только тогда, когда степень каждой вершины чётна (2), или тогда и только тогда, когда множество рёбер графа можно покрыть без пересечений простыми циклами (3).
\end{theorem}
\begin{proof} $(1)\Rightarrow(2)$: если степень какой-либо вершины нечётна, то мы, двигаясь в порядке рёбер эйлерова цикла, не сможем в какой-то момент войти в эту вершину по одному ребру и выйти по другому ребру, поскольку её степень нечётна. Это означает, что наш обход не является циклом. Противоречие.\\
$(3)\Rightarrow(1)$: объединение всех этих простых циклов является эйлеровым циклом.\\
Что мы подразумеваем под словом "объединение"? Давайте рассмотрим это как последовательный процесс: на нулевом шаге мы рассмотрим любой простой цикл, и будем добавлять к нему простые циклы из числа ещё не задействованных по одному. Таким образом, на каждом шаге мы имеем некоторый цикл и множество (возможно, пустое) тех простых циклов, которые мы ещё не рассмотрели.\\
Пусть это множество непусто. Тогда, так как граф связен, в построенном на данный момент цикле обязательно найдётся вершина, лежащая в одном из незадействованных простых циклов. Обозначим эту вершину $v$, уже построенный нами цикл ~--- $a_1\dots a_i v a_{i+1}\dots a_1$, незадействованный простой цикл ~--- $vb_1b_2\dots b_kv$. Тогда новый цикл мы определим как $a_1\dots a_i v b_1\dots b_k v a_{i+1}\dots a_1$, и мы уменьшили на 1 количество не рассмотренных простых циклов.\\
Пусть это множество оставшихся циклов пусто. По предположению, тогда пусто и множество ребёр, которые лежат вне построенного нами цикла ~--- следовательно, этот цикл эйлеров.\\
$(2)\Rightarrow(3)$: индукция по количеству рёбер.\\
База индукции: если рёбер $0$, то множество рёбер тривиально состоит из нуля простых непересекающихся друг с другом циклов.\\
Переход: выберем произвольную вершину ненулевой степени и пойдём в обход по графу, не проходя дважды одного и того же ребра, пока не вернёмся в какую-либо вершину ~--- таким образом, мы выделили простой цикл. Рёбра этого цикла мы удалим из графа, и чётность степеней всех вершин сохранится, а число рёбер уменьшится.
\end{proof}
\begin{theorem} Слабо связный орграф является эйлеровым тогда и только тогда, когда входящие степени (каждой вершины) равны исходящим.
\end{theorem}
\begin{proof} Аналогично предыдущей теореме.
\end{proof}
\begin{theorem}[Критерий Дирака] Если в графе на $n$ вершинах степень каждой вершины не менее $\lceil \frac{n}{2} \rceil$, то граф содержит гамильтонов цикл.
\end{theorem}
\begin{proof} Начнём со вспомогательного утверждения:
\begin{lem-star} Пусть в графе максимальный простой путь состоит из $m$ вершин, и суммарная степень двух концов этого пути не меньше $m$. Тогда в графе существует простой цикл длины $m$.
\end{lem-star}
\begin{proof} Обозначим вершины этого пути $a_1,a_2,a_3,\dots,a_m$. Так как путь максимален, то рёбра вида $(a_1,\:v)$ и $(a_m,\:v)$, где $v \notin \{a_i\}_{i=1}^m$, в графе отсутствуют. 
Если вершины $a_1$ и $a_m$ соединены ребром, то искомый цикл найден.\\
Если одновременно есть рёбра $(a_{i+1},\:a_1)$ и $(a_i,a_m)$ (для произвольного $ i \in \overline{2,\, m-2} $ ), то искомый цикл выглядит так: $a_1a_2\dots a_ia_ma_{m-1}\dots a_{i+1} a_1$.
Предположим, что цикла всё же нет. Тогда в силу предыдущего утверждения каждое ребро, проведённое из $a_m$, "запрещает"\ одно ребро из $a_1$, и наоборот (кроме заведомо существующих рёбер $(a_1,\,a_2)$ и $(a_m,\,a_{m-1})$, которые мы сейчас не учитываем). При этом из вершины $a_1$ могут быть рёбра к вершинам $a_3,a_4,\dots,a_{m-1}$ ~--- всего $m-3$ возможности, столько же для $a_m$. Однако эти возможности взаимоисключающие, а нам необходимо (согласно посылке леммы) провести из $a_1$ и $a_m$ суммарно $m-2$ ребра. Противоречие.
\end{proof}
Заметим, что граф связен, поскольку суммарная степень любых двух вершин не менее $n$ ~--- это означает, что они либо соединены ребром, либо (по принципу Дирихле) имеют общего соседа.\\
Рассмотрим в нашем графе максимальный простой путь. Согласно лемме, существует простой цикл, проходящий по всем вершинам этого пути (и только по ним). Обозначим его вершины в порядке следования цикла $a_1,a_2,a_3,\dots ,a_m$.\\
Если $m<n$, то рассмотрим любую вершину $v$, не лежащую в цикле. Так как граф связен, для некоторого $i$ существует ребро $(a_i,\:v)$. Тогда путь $va_ia_{i+1}\dots a_ma_1a_2\dots a_{i-1}$ содержит на одну вершину больше, чем рассмотренный нами максимальный. Противоречие.\\
Если же $m=n$, то цикл $a_1a_2a_3\dots a_{m-1}a_ma_1$ ~--- гамильтонов.
\end{proof}


\begin{theorem} Пусть в графе $G$ хотя бы 3 вершины и $k(G)\geq\alpha(G)$. Тогда $G$ содержит гамильтонов цикл.
\end{theorem}
\begin{proof} Если в $G$ нет циклов, то $k(G)\geq\alpha(G)\geq 1 \Rightarrow G$ связен $\Rightarrow k=1, \alpha\geq 2$. Противоречие. Иначе рассмотрим максимальный простой цикл $C = \{v_1,v_2,\dots,v_m\}$ и предположим, что он не гамильтонов, то есть $G\setminus C$ непусто. Пусть $W$ ~--- любая связная компонента $G\setminus C$, $N(W) = \{x\notin W\: |\:\exists y \in W: \: (x,y)\in E(G)\}$. Имеют место следующие утверждения:
\begin{enumerate}
\item $N(W)\subset C$ (сосед компоненты связности, не лежащий в $C$, должен лежать в самом $W$). 
\item Никакие две соседние вершины цикла не лежат в $N(W)$ одновременно. В противном случае для некоторого $i$ в графе есть рёбра $(v_i,x)$, $(y,v_{i+1})$, где $x,y \in W$, а также путь (возможно, нулевой длины) между $x$ и $y$, так как $W$ связно. Тогда, удаляя ребро $(v_i,v_{i+1})$ из $C$ и заменяя его на путь $v_ix\dots yv_{i+1}$, мы получаем цикл большей длины, чем $C$ ~--- значит, $C$ не был максимален.
\item $|N(W)|\geq k(G)$. Действительно, если мы удалим множество $N(W)$ из графа, то $C\setminus N(W)$ и $W$ окажутся в различных компонентах связности.
\item Определим $M = \{v_{i+1}\:|\: v_i\in N(W)\}$ и заметим, что $|M|=|N(W)|$ (по построению).
\item $M \cap N(W) = \emptyset$, что вытекает из пункта 2.
\item $M$ ~--- независимое множество. Иначе рассмотрим индексы $i,j$, для которых $v_{i+1},v_{j+1}\in M$, $v_i,v_j\in N(W)$, $(v_{i+1},v_{j+1})\in E$. Пусть $x$ и $y$ ~--- те вершины в $W$ (возможно, совпадающие), которые соединены с $v_i$ и $v_j$ соответственно. Рассмотрим цикл $v_1v_2\dots v_i x\dots y v_j \dots v_{i+1}v_{j+1}\dots v_1$ ~--- по существу, мы удалили из $C$ два ребра $(v_i,v_{i+1})$ и $(v_j,v_{j+1})$, добавили три ребра $(v_i,x)$, $(v_j,y)$, $(v_{i+1},v_{j+1})$ и прошли путь от $v_j$ до $v_{i+1}$ в обратной последовательности. Значит, $C$ ~--- не максимальный цикл.
\item Пусть $w\in W$ ~--- произвольная вершина, тогда $M\cup w$ ~--- также независимое множество. Действительно, если $v\in M$, $(v,w)\in E$, то по определению $v\in N(W)$, поскольку по построению $M\subset C$. Но тогда $v\in M\cap N(W)$, что противоречит пункту 5.
\end{enumerate}
Пункт 7 означает, что $|M|<\alpha(G)$. хотя из пунктов 3 и 4 следует $|M|\geq k(G)$. Противоречие.

\end{proof}

$\bullet$ \\ 

\section{Билет №6}
\subsection{Хроматическое число, число независимости, кликовое число и соотношения между ними}

\begin{definition-star} $k(G)$ (вершинная связность) ~--- минимальное к-во вершин, от удаления которых граф $G$ теряет связность.
\end{definition-star}
\begin{definition-star} $\alpha(G)$ (число независимости) ~--- максимальная мощность независимого множества.
\end{definition-star}
\begin{definition-star} $w(G)$ (кликовое число) ~--- максимальный размер клики в графе.
\end{definition-star}

\begin{definition-star} Хроматическое число графа $\chi(G)$ ~--- минимальное число цветов, в которое можно раскрасить вершины графа так, что все рёбра соединяют вершины разного цвета.
\end{definition-star}
\begin{proposition-star} $\chi(G)\geq \omega(G),\:\: \chi(G)\geq \frac{n}{\alpha(G)}$.
\end{proposition-star}
\begin{theorem} В последовательности случайных графов при $p(n)=1/2$ АПН $\alpha(G)\leq 2\: \log_2 n$.
\end{theorem}
\begin{proof} Пусть $X_k(G)$ ~--- число независимых множеств на $k$ вершинах, $k = [2\log_2 n]$. 
\myequat{MX_k=C_n^k\,2^{-C_k^2}\leq \frac{n^k}{k!}2^{-\frac{k^2}{2}+\frac{k}{2}}\leq \frac{2^{2 \log_2^2 n}}{k!}2^{-\frac{(2\log_2 n - 1)^2}{2}+\log_2 n}\leq\frac{1}{k!}2^{3\log_2 n}=\frac{n^3}{k!}}
\myequat{k!>(k/e)^k=\pars{\frac{2\log_2 n}{e}}^{2\log_2 n}>8^{2\log_2 n}=n^6}
\myequat{MX_k\to 0}
\end{proof}
Таким образом, вторая оценка для $\chi(G)$, как правило, лучше.
\begin{theorem}[Боллобаш, б/д] При $p(n)=1/2$ существует функция $\phi(n)=o\pars{\frac{n}{\ln n}}$ такая, что АПН $\chi(G)= \frac{n}{2\log_2 n}+\phi(n)$.
\end{theorem}
\begin{definition-star} Жадный алгоритм нахождения хроматического числа: раскрасим последовательно вершины в минимально возможный на данный момент цвет. Обозначим полученный результат $\chi'(G)$.
\end{definition-star}
\begin{definition-star} Жадный алгоритм нахождения числа независимости (кликового числа ~--- аналогично): в найденной ранее раскраске графа рассмотрим наибольшую компоненту. Обозначим полученный результат $\alpha'(G)$.
\end{definition-star}
\begin{theorem} При $p(n)=1/2$ АПН $\alpha'(G)\geq (1-\varepsilon)\log_2 n$.
\end{theorem}
\begin{proof} Пусть событие $A$ означает обратное, т.е. $\alpha'(G)<(1-\varepsilon)\log_2 n$. Отсюда следует, что алгоритм отыскал хотя бы $x=\class{\frac{n}{2(1-\varepsilon)\log_2 n}}$ различных цветов. Так как алгоритм жадный, то каждая вершина из $V(G)/\bigcup_{i=1}^xC_i$ соединена с каждым из первых $x$ цветов.\\
Пусть $a_1,a_2,\dots,a_x$ ~--- размеры первых $x$ цветов, $a_i<(1-\varepsilon)\log_2 n$. В дальнейших выкладках внешнее суммирование ведётся по всем возможным числам $a_i$ от $1$ до $(1-\varepsilon)\log_2 n$ и непересекающимся подмножествам $C_1,C_2,\dots,C_x\subset V$ таким, что $|C_i|=a_i$.
\myequat{P(A)\leq \sum P(\forall\,x\in V/\bigcup_{i=1}^xC_i\;\forall\,i\,\exists\, y\in C_i\: | \: (x,y)\in E)\leq}
\myequat{\leq\sum \class{\prod_{i=1}^x(1-2^{-a_i})}^{n-\sum_{j=1}^xa_j}\leq\sum\class{1-2^{(\varepsilon-1)\log_2 n}}^{x(n-\sum_{j=1}^xa_j)}\leq}
\myequat{\leq\sum [1-n^{\varepsilon-1}]^{\frac{nx}{2}}\leq\sum e^{-\frac{nx}{2n^{1-\varepsilon}}}}
То, что осталось под суммой, оценим окончательно как $e^{\frac{n^{\varepsilon}x}{2}}<e^{-n^{1+\delta}},\:\:\delta>0$.\\
Вернёмся к количеству слагаемых: их не больше, чем
\myequat{(\log_2 n)^x (C_n^{\log_2 n})^x<(\log_2 n)^x n^{x\log_2 n}}
\myequat{(\log_2 n)^x<n^x<n^{x\log_2 n}}
\myequat{n^{2x\log_2 n}=e^{2x\log_2 n\ln n}=e^{C\myO n\log_2 n}}
Итого,
\myequat{P(A)<n^{2x\log_2 n}e^{-n^{1+\delta }}<e^{-n^{1+\delta}+C\myO n\log_2 n}\to 0,}
что и требовалось.
\end{proof}

\section{Билет №7}
\subsection{Системы общих представителей. Тривиальная верхняя и нижняя оценки}
\begin{definition-star} Пусть имеется $s$ $k$-элементных подмножеств $\{1,2,\dots,n\}$. Обозначим систему этих множеств $\myM(n,k,s)$. Система общих представителей для $\myM$ ~--- любое подмножество $\{1,2,\dots,n\}$, пересечение которого с каждым множеством системы непусто. Минимально возможный размер с.о.п. обозначим $\tau(\myM)$.
\end{definition-star}
\begin{proposition-star} Для любой совокупности $\myM$ выполнено $\tau(\myM)\leq min\{s,n-k+1\}$.
\end{proposition-star}
\begin{proof} Можно взять по элементу из каждого множества совокупности $\myM$, а можно взять любое множество размера $n-k+1$ ~--- оно неизбежно пересекается с любым множеством размера $k$.
\end{proof}
\begin{proposition-star} Всегда имеется совокупность $\myM$, для которой $\tau(\myM)\geq min\{[n/k],s\}$.
\end{proposition-star}
\begin{proof} Если $[n/k]\geq s$, то построим совокупность из непересекающихся множеств. Если $[n/k]<s$, то сделаем первые $[n/k]$ множеств не пересекающимися, а остальные возьмём произвольно.
\end{proof}
\subsection{Верхняя оценка с помощью жадного алгоритма. Ее точность (б/д)}
\begin{theorem} Для любой совокупности: $\tau(\myM)\leq max\{\frac{n}{k},\frac{n}{k}\ln \frac{sk}{n}\}+\frac{n}{k}+1$.
\end{theorem}
\begin{proof} Если $s\leq \frac{n}{k}$, то (предложение 13) $\tau(\myM)\leq s\leq \frac{n}{k}$.\\
Если $\frac{n}{k}\,ln\:\frac{sk}{n}\geq n$, то $\tau(\myM)\leq n \leq \frac{n}{k}\ln \frac{sk}{n}$.\\
Иначе воспользуемся жадным алгоритмом: на каждом шаге берём элемент, лежащий в наибольшем числе множеств совокупности, и удаляем из совокупности эти множества. На каждом шаге мы удаляем $sk/n$ множеств. Сделаем $N = \class{\frac{n}{k}\ln \frac{sk}{n}}+1$ шагов, тогда в совокупности останется не более $\frac{n}{k}$ множеств. Значит, $\tau(\myM)\leq N+\frac{n}{k}$.
\end{proof}

\section{Билет №8}
\subsection{Гиперграфы с запрещенными пересечениями ребер}
\subsection{Основы линейно-алгебраического метода}

\end{document}