IMO олимпиада по математике 2011 года | Казахстанские олимпиады

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