\input comb-head.tex

\pagestyle{empty}

\begin{center}
{\Large Ответы к задачам от 31.10.00}\\[2mm]
{\large\tt http://www.botik.ru/\~{}duzhin/NMU/2000a/}
\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)$.
\smallskip

{\sl Ответ.}
\begin{enumerate}
\item
Тривиальный вид $F=\sum_{k\ge0}f_kE_k$ (здесь $E_k$ --- вид множеств
мощности $k$, а слово ``тривиальный'' означает тривиальное действие
группы перестановок $S_k$ на множестве $F[k]$).
$F(x)=(e^{\f x}-e^{x/\f})/\sqrt{5}$, где $\f=(1+\sqrt{5})/2$ --- золотое
сечение;
$\tilde{F}(x)=x/(1-x-x^2)$.
\item
Есть два разумных ответа: $F=L(X+X^2)$ и $F=L(X+E_2)$.
Производящая функция, перечисляющая типы, в обоих случаях одна и та же
и совпадает с $\tilde{F}$ из предыдущего пункта. Функции $F(x)$ разные:
для первого варианта $1/(1-x-x^2)$, для второго $1/(1-x-x^2/2)$.
\end{enumerate}

\item
Дайте явное описание комбинаторных видов $Y$, $B$ и $P$,
удовлетворяющих соотношениям
\begin{eqnarray*}
  (a)\quad Y &=& 1+X\cdot Y,\\
  (b)\quad B &=& 1+X\cdot B^2,\\
  (c)\quad 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)$.

\smallskip

{\sl Ответ.}
\begin{enumerate}
\item
$Y=L$ --- вид линейных порядков.
$L(x)=\tilde{L}(x)=1/(1-x)$.
\item
$B[U]$ --- плоские бинарные корневые деревья с множеством
вершин $U$. Производящие функции
$B(x)=\tilde{B}(x)=(1+\sqrt{1-4x})/(2x)$.
\item
$P[U]$ --- бинарные корневые деревья с множеством  
листьев $U$, они же --- коммутативные неассоциативные скобочные 
структуры на множестве $U$.
$P(x)=1-\sqrt{1-2x}$.
Для $\tilde{P}(x)$ имеется уравнение
$\tilde{P}(x)=x+(\tilde{P}(x)^2+\tilde{P}(x^2))/2$,
откуда находим: $\tilde{P}(x)=x+x^2+x^3+2x^4
+3x^5+6x^6+11x^7+23x^8+46x^9+...$.
Общую формулу никому найти не удалось.
\end{enumerate}

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

{\sl Решение.}
Если голова позвоночного совпадает с хвостом, то это не что иное, как
корневое дерево. В противном случае нужно отрубить голову,
и позвоночное развалится на дерево и меньшее позвоночное.

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

\smallskip

{\sl Решение.}
\begin{enumerate}
\item
$\C(2X)$ --- это цикл, состоящий из точек двух цветов.
Если все точки черные, то это структура типа $\C(X)$.
В противном случае из цикла можно сделать осьминога,
поместив белые точки на центральную окружность, а черные выпустив в виде
щупалец в стороны.
\item
Можно доказать подобным же комбинаторным рассуждением.
А можно при помощи тождественных преобразований в кольце виртуальных 
видов. С одной стороны,
\begin{eqnarray*}
  \Oct(X)&=&\C(2X)-\C(X),\\
  \Oct^{\bdot}&=&\C(2X)^{\bdot}-\C(X)^{\bdot}
              =L(2X)\cdot2X-X\cdot L\\
              &=&\frac{2X}{1-2X} - \frac{X}{1-X}
              =\frac{X}{(1-X)(1-2X)}.
\end{eqnarray*}
С другой стороны:
\begin{eqnarray*}
  L(X)L(2X)-L(2X)&=&\frac{1}{1-X}\cdot\frac{1}{1-2X} - \frac{1}{1-2X}\\
                 &=&\frac{X}{(1-X)(1-2X)}.
\end{eqnarray*}
\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}

\smallskip

{\sl Ответ.}
\begin{enumerate}
\item
$(X\cdot E_2)\times(X\cdot E_2)=X\cdot E_2+X^3$.
\item
$\Oct+\,\C=\C(2X)=\C\times\Sub$,
где $\Sub=E\cdot E$ --- вид подмножеств.
\end{enumerate}

\end{enumerate}

\end{document}