комбинаторика - Про прямоугольник

Если дана полоска $%1\times n$%, то количество способов её заполнения равно $%2^{n-1}$%. Доказывается по индукции. При $%n=1$% это очевидно. При $%n > 1$% рассмотрим числа 1 и 2, стоящие в соседних клетках. Соединим эти две клетки в одну, помещая туда число 2. Тогда полоска размером $%1\times(n-1)$% окажется заполнена символами от 2 до $%n$% по тем же правилам. Это число способов такое же, как и для заполнения символами от 1 до $%n-1$%. По предположению индукции, оно равно $%2^{n-2}$%. Теперь вернём всё назад: вместо клетки с символом 2 рассмотрим две соседние клетки, которые можно заполнить двумя способами: 12 или 21. При этом число способов удваивается и становится равно $%2^{n-1}$%.