На листе клетчатой бумаги нарисован прямоугольник 1 Х8. Сколькими различными способами его можно нарезать на части, содержащие одну, две или четыре клетки? В одном разрезании не обязательно встречается все три возможных типа. (Например, для прямоугольника 1 Х3 таких возможностей три: 1+2, 2+1 и 1+1+1).

8 частей по 1 клетке:

1+1+1+1+1+1+1+1

2 части по 4 клетки:

4+4

4 части по 2 клетки:

2+2+2+2

1 часть по 4 клетки и 2 части по 2 клетки:

4+2+2, 2+4+2, 2+2+4

1 часть по 4 клетки и 4 части по 1 клетке:

4+1+1+1+1, 1+1+4+1+1, 1+4+1+1+1, 1+1+1+4+1, 1+1+1+1+4

1 часть по 4 клетки, 1 часть по 2 клетки и 2 части по 1 клетке:

4+2+1+1, 4+1+2+1, 4+1+1+2, 2+4+1+1, 2+1+4+1, 2+1+1+4, 1+4+2+1,

1+2+4+1, 1+1+2+4, 1+1+4+2

3 части по 2 клетки и 2 части по 1 клетке:

2+2+2+1+1, 2+2+1+1+2, 2+2+1+2+1, 2+1+2+1+2, 2+1+1+2+2, 2+1+2+2+1, 1+1+2+2+2, 1+2+1+2+2, 1+2+2+1+2, 1+2+2+2+1

2 части по 2 клетки и 4 части по 1 клетке:

2+2+1+1+1+1, 2+1+2+1+1+1, 2+1+1+2+1+1, 2+1+1+1+2+1, 2+1+1+1+1+2,

1+2+2+1+1+1, 1+2+1+2+1+1, 1+2+1+1+2+1, 1+2+1+1+1+2, 1+1+2+2+1+1,

1+1+2+1+2+1, 1+1+2+1+1+2, 1+1+1+2+2+1, 1+1+1+2+1+2, 1+1+1+1+2+2

1 часть по 2 клетки и 6 частей по 1 клетке:

2+1+1+1+1+1+1, 1+2+1+1+1+1+1, 1+1+2+1+1+1+1, 1+1+1+2+1+1+1, 1+1+1+1+2+1+1, 1+1+1+1+1+2+1, 1+1+1+1+1+1+2

Много способов