\input comb-head.tex

\pagestyle{empty}

\begin{center}
{\Large Задачи по комбинаторным видам}\\[2mm]
{\large\sl С.\,В.\,Дужин}
\end{center}

\begin{enumerate}

\item
Придумайте комбинаторный вид $F$ такой, что
\begin{enumerate}
\item
Число $f_n$ структур вида $F$ на $n$-элементном множестве
есть $n$-е число Фибоначчи.
\item
Число $\tilde{f}_n$ классов эквивалентности структур вида $F$ 
на $n$-элементном множестве есть $n$-е число Фибоначчи.
\end{enumerate}
В каждом случае найдите производящие функции $F(x)$ и $\tilde{F}(x)$.

\item
Дайте явное описание комбинаторных видов $Y$, $B$ и $P$,
удовлетворяющих соотношениям
\begin{eqnarray*}
   Y &=& 1+X\cdot Y,\\
   B &=& 1+X\cdot B^2,\\
   P &=& X+E_2\circ P,
\end{eqnarray*}
где 1, $X$ и $E_2$ --- виды пустых, одноточечных и двухточечных
множеств соответственно.
Найдите производящие функции $Y(x)$, $\tilde{Y}(x)$,
$B(x)$, $\tilde{B}(x)$, $P(x)$, $\tilde{P}(x)$.

\item
Пусть $T$ --- вид деревьев, $R=T^{\bdot}$ --- вид корневыых
деревьев, $V=R^{\bdot}$ --- вид позвоночных.
Докажите изоморфизм $V=R+V\cdot R$.

\item
Пусть $L$ --- вид линейных порядков, $L_+$ --- вид линейных порядков
на непустых множествах, $\C$ --- вид циклических перестановок,
$\Oct=\C(L_+)$ --- вид осьминогов.
Докажите, что
\begin{enumerate}
\item
$\Oct(X)+\C(X)=\C(2X)$, где $X$ --- вид одноточечных множеств.
\item
$\Oct^{\bdot}+L(2X)=L(X)\cdot L(2X)$, где точка обозначает операцию 
пунктирования (выделения точки).
\end{enumerate}

\item
\begin{enumerate}
\item
Представьте вид $(X\cdot E_2)\times(X\cdot E_2)$
в виде многочлена от $X$ и $E_2$. (Многочлен понимается относительно 
сложения и `обычного' умножения видов.)
\item
Разложите вид $\Oct+\,\C$, где $\Oct$ --- вид осьминогов, а $\C$
--- вид циклических перестановок, нетривиальным способом в декартово 
произведение двух видов.
\end{enumerate}

\end{enumerate}

\vfill
\hrulefill
\vfill

{\small
Задание выдано 31 октября 2000.
Решения в рукописном виде сдавать 14.11.2000 либо в электронном виде
до того же срока по адресу \verb#duzhin@botik.ru#.

Лекционные заметки см. по адресу \verb#http://www.botik.ru/~duzhin/NMU#.
}
\end{document}