Mongolian Mathematical Olympiad

It is equivalent to find number of spanning trees in the figure below.



Thus it is sufficient to find number of spanning trees of $G$. Denote $a_n$ number of spanning trees of $G$.



Let $e$ be edge $A_n{A}_{n-1}$ of the graph $G$. Now if we remove the edge $e$ then vertices $A_n$ and $A_{n-1}$ will coincide. Denote $G\cdot e$ remaining graph. Spanning trees of $G$ are divided into two subsets that either contain $e$ or not.



Trees that do not contain $e$ are those trees of the graph remained after deleting $e$ from $G$. Since spanning tree of such graph contains edge $A_{n}C$, number of spanning trees that do not contain $e$ equals to $a_{n-1}$.

On the other hand, for those trees that contain $e$, either $A_{n-1}C$ or $A_{n}C$ will be removed. Therefore number of spanning trees of $G\cdot e$ equals to number of spanning trees of $G$ that do not contain $e$. Number of spanning trees of $G\cdot e$ equals to $a_{n-1}$ in case that removed $A_{n-1}C$ and equals to $a_{n-1}$ in case that removed $A_{n}C$. However, we need to note that in case that both edges $A_{n-1}C$ and $A_{n}C$ are removed the number of the spanning trees may be counted 2 times. Therefore we get recurrence relation $a_n=3a_{n-1}-a_{n-2}$. It is easy to see $a_1=1$ and $a_2=3$. Solving the recurrence relation we get $$a_n=\frac{1}{\sqrt{5}}\left({\left(\frac{3+\sqrt{5}}{2}\right)}^n-{\left(\frac{3-\sqrt{5}}{2}\right)}^n\right)$$ and conclude that desired number equals to $$\frac{1}{5}\left({\left(\frac{3+\sqrt{5}}{2}\right)}^n-{\left(\frac{3-\sqrt{5}}{2}\right)}^n\right)\left({\left(\frac{3+\sqrt{5}}{2}\right)}^m-{\left(\frac{3-\sqrt{5}}{2}\right)}^m\right).$$

---

Alternative solution.

II solution. (Due to MMO's 5 times winner B. Bayarjargal.)



Denote $u_n$ number of the possibilities of removing $n$ edges from $2n-1$ edges. Let's divide stations $A_1,A_2,...,A_n$ into $l$ parts with length $d_1,d_2,...,d_l$ (where $d_l$ is number of stations in a part).



Since remaining graph must be connected, there is one edge from every part to $C$ and number of such possibilities equals to $d_1\cdot d_2\cdots d_l$.

Therefore $u_n$ equals to the sum of all possible summands $\prod d_i$, where $n=\sum d_i,d_i\in \mathbb{N}$.

Let's consider generating function of the sequence $u_n$: $F(x)=x+2x^2+3x^3+...+n{x}^n+...$ $$S(x)=\sum _k(F(x){)}^k=\sum _k{u}_k{x}^k.$$ $$\begin{array}{rl}\frac{F(x)}{x}& ={\left(\frac{1}{1-x}\right)}^{\prime }=\frac{1}{(1-x{)}^2}\Rightarrow \\ \Rightarrow F(x)& =\frac{x}{(1-x{)}^2}\Rightarrow F^k(x)=\frac{x^k}{(1-x{)}^{2k}}=a_{k1}x+a_{k2}x+\dots \end{array}$$ Since $\frac{1}{(1-x{)}^{2k}}=\sum c_i{x}^i$ we get $$\begin{array}{rl}{c}_i=(-1{)}^i(\genfrac{}{}{0ex}{}{-2k}{i})& =\frac{-2k\cdot (-2k-1)\cdots (-2k-i+1)}{i!}\cdot (-1{)}^i=\\ & =\left(\genfrac{}{}{0ex}{}{2k+i-1}{i}\right)\Rightarrow a_{k1}=\left(\genfrac{}{}{0ex}{}{2k+i-1}{i}\right)\Rightarrow u_n=\sum _{k=1}^n{a}_{k1}=\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{k+n-1}{n-k}\right).\end{array}$$ Finally, the desired number equals to $u_n\cdot u_m=\left({\sum }_{k=1}^n\left(\genfrac{}{}{0ex}{}{k+n-1}{n-k}\right)\right)\left({\sum }_{i=1}^m\left(\genfrac{}{}{0ex}{}{i+m-1}{m-i}\right)\right)$.