Лесенкой называется последовательность клеток на к...

Введём координаты клеток так, чтобы клетка $O$ имела координаты $(0,0)$, а сосед справа увеличивал $x$ на $1$, сосед сверху — $y$ на $1$.

Для клетки $A=(x,y)$ положим

$$h(A)=x+y.$$

При каждом шаге лесенки вправо или вверх величина $h$ увеличивается ровно на $1$.

Рассмотрим диагональные слои

$$D_k=\{A:\ h(A)=k\}.$$

Для каждого целого $k$ построим двудольный граф $G_k$: в одной его доле находятся отмеченные клетки из $D_k$, в другой — отмеченные клетки из $D_{k+1}$, а две клетки соединены ребром, если они соседние по стороне. Обозначим через $m_k$ число всех паросочетаний в $G_k$, включая пустое.

1. Разбиения на лесенки считаются произведением $\prod m_k$

Пусть дано разбиение отмеченных клеток на лесенки. В каждой лесенке отметим пары последовательных клеток. Между слоями $D_k$ и $D_{k+1}$ эти отмеченные пары образуют паросочетание: у клетки не может быть двух следующих или двух предыдущих клеток в одной лесенке.

Обратно, независимо для каждого $k$ выберем любое паросочетание в $G_k$. Соединим клетки выбранными рёбрами.

У каждой клетки тогда не более одного выбранного ребра, ведущего из предыдущего слоя, и не более одного — в следующий слой. Поэтому каждая компонента получившегося графа является цепочкой

$$A_1\to A_2\to\cdots\to A_r,$$

причём каждый шаг идёт вправо или вверх. То есть каждая компонента — лесенка. Циклов быть не может, поскольку $h$ вдоль каждого ребра увеличивается.

Таким образом, имеем биекцию

$$\{\text{разбиения на лесенки}\} \longleftrightarrow \prod_k\{\text{паросочетания в }G_k\}.$$

Следовательно, число разбиений равно

$$N=\prod_{k\in\mathbb Z}m_k.$$

Фактически почти все множители равны $1$, так как отмеченных клеток конечное число.

2. Центральная симметрия попарно уравнивает множители

Поворот на $180^\circ$ относительно клетки $O$ переводит

$$(x,y)\longmapsto(-x,-y),$$

поэтому слой $D_k$ переходит в $D_{-k}$.

Если две соседние клетки образуют ребро между $D_k$ и $D_{k+1}$, то после центральной симметрии они образуют ребро между

$$D_{-k-1}\quad\text{и}\quad D_{-k}.$$

Значит, симметрия задаёт изоморфизм

$$G_k\cong G_{-k-1}.$$

В частности,

$$m_k=m_{-k-1}.$$

Но преобразование индексов

$$k\longmapsto -k-1$$

разбивает все целые числа на пары и не имеет неподвижных точек, поскольку равенство $k=-k-1$ дало бы $k=-\tfrac12$.

Поэтому

$$N=\prod_{k\in\mathbb Z}m_k =\prod_{k\ge 0}m_k\,m_{-k-1} =\prod_{k\ge0}m_k^2 =\left(\prod_{k\ge0}m_k\right)^2.$$

Итак, число способов разбить отмеченное множество клеток на лесенки является квадратом натурального числа. $\square$