
\documentclass[12pt,fleqn,a4paper]{article}

\usepackage[russian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{enumitem}
\usepackage{ntheorem}
\usepackage{tikz}
\usepackage{verbatim}

\usetikzlibrary{arrows,shapes}

\tikzstyle{vertex}=[circle,fill=black,minimum size=3pt,inner sep=0pt]
\tikzstyle{edge} = [draw,thick,-]

\newtheorem{definition}{Определение}
\newtheorem*{solution}{Решение}

\newenvironment{task}[2] {
	\noindent\fbox{\bf {#1} {#2}.}
}{
}

\newcommand{\mytitle}[2] {
  \begin{center}
      \bf {#1} {#2}.
  \end{center}
}

\let\origenumerate\enumerate
\let\origendenumerate\endenumerate
\renewenvironment{enumerate}{\origenumerate[topsep = 0pt, noitemsep]}{\origendenumerate}

\begin{document}
	\mytitle{Домашняя работа 5.}{Остовные деревья}
	\begin{task}{COMB}{56}
		Посчитайте число остовных деревьев графа $K_{3, n}$ не используя рекуррентное соотношение и матричную теорему о деревьях.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{57}
		Используя матричную теорему о деревьях, подсчитать количество всех остовных деревьев
		полного двудольного графа $K_{m,n}$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{58}
		Доказать, что количество корневых лесов, построенных на $n$ вершинах, описывается формулой $(n + 1)^{(n - 1)}$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{59}
		Пусть у нас имеется улица с односторонним движением, на которой расположено $n$ парковочных мест.
		На эту улицу последовательно заезжают машины с порядковыми номерами от $1$ до $n$. 
		Каждая $i$-я машина по прибытии едет вначале к своему любимому парковочному месту $f(i)$.
		Если это место оказывается свободным, то она занимает его. В противном случае она 
		пытается занять первое следующее за ним свободное место. В случае, если такового не оказывается,
		процесс парковки считается завершившимся неудачей.
		
		Функция $f : [n] \to [n]$ называется парковочной функцией, если задаваемая ею парковка всех $n$ машин прошла успешно.
		Доказать, что количество всех различных парковочных функций равно $(n + 1)^(n - 1)$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{60}
		Какова максимальная степень вершины в дереве, последовательность Прюфера которой имеет вид $(1, 7, 2, 2, 2, 2)$?
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{61}
		Используя матричную теорему о деревьях, подсчитать количество всех помеченых деревьев на $n$
		вершинах.
	\end{task}
	\begin{solution}
	\end{solution}

\end{document}