52-я Международная Математическая OлимпиадаНидерланды, Амстердам, 2011 год

Дано целое число $n > 0$. Имеются чашечные весы и $n$ гирь, веса которых равны ${{2}^{0}}$, ${{2}^{1}}$, $\ldots$, ${{2}^{n-1}}$. Все $n$ гирь выкладываются одна за другой на чаши весов, то есть на каждом из $n$ шагов выбирается гиря, которая еще не выложена на весы, и добавляется либо на левую, либо на правую чашу весов; при этом гири выкладываются так, чтобы ни в какой момент правая чаша не была тяжелее левой. Найдите количество способов выполнить такую последовательность шагов.

Комментарий/решение

Пусть $A_{n}$ количество таких последовательностей. Выразим $A_{n}$ через $A_{n-1}$.

Заметим, что гиря с весом $2^{n-1}$ лежит на левой чаше весов. Пусть ее положили на $k$ой. Тогда количество способов положить первые $k-1$ гирь это $C^{k-1}_{n-1}A_{k-1}$. Количество способов положить оставшиеся гири, это $2^{n-k}(n-k)!$. Тогда $A_{n}=\sum_{i=0}^n C^{i-1}_{n-1}A_{i-1}2^{n-i}(n-i)! = (2n-1)A_{n-1}$. Так как $A_{1}=1$, то $A_{n}=(2n-1)!!$.