Монгол Бодлогын Сан

Заавар: ММО-37, хуу.22

Бодолт: $n$ хүнийг "өндөр - нам - өндөр - нам - $\ldots$" дарааллаар байрлуулах боломжийн тоог $c_n$ гэе. Хамгийн хүн өндөр хүн сондгой дугаартай байранд зогсох ёстой. Хамгийн өндөр хүн хаана зогсож байгаагаар нь тооцож рекурент харьцаа зохиовол $$c_n=c_{0}c_{n-1}+C_{n-1}^2c_{2}c_{n-3}+C_{n-1}^4c_{4}c_{n-5}+\dots$$ байна. Түүнчлэн $c_0=1$ тул \begin{align*} c_1&=c_0c_0=1\cdot 1=1\\ c_2&=c_0c_1=1\cdot 1=1\\ c_3&=c_0c_2+C_{2}^2c_2c_0=1\cdot 1+1\cdot 1\cdot 1=2\\ c_4&=c_0c_3+C_3^2c_2c_1=1\cdot 2+3\cdot 1\cdot 1=5\\ c_5&=c_0c_4+C_4^2c_2c_2+C_4^4c_4c_0=1\cdot 5+6\cdot 1\cdot 1+1\cdot 5\cdot 1=16\\ c_6&=c_0c_5+C_5^2c_2c_3+C_5^4c_4c_1=1\cdot 16+10\cdot 1\cdot 2+5\cdot 5\cdot 1=61\\ c_7&=c_0c_6+C_6^2c_2c_4+C_6^4c_4c_2+C_6^6c_6c_0=1\cdot 61+15\cdot 1\cdot 5+15\cdot 5\cdot 1+1\cdot 61\cdot 1=272\\ \end{align*}