Один из способов вычисления количества способов вырезания прямоугольников из клетчатых фигур — подсчёт количества способов провести вертикальные и горизонтальные прямые. 1
Например, если нужно найти, сколькими способами можно вырезать прямоугольник из клетчатого листа, состоящего из n клеток по горизонтали и m клеток по вертикали. 1 Чтобы выделить прямоугольник, нужно провести 4 прямые: 2 вертикальные и 2 горизонтальные. 1
Количество способов провести пару вертикальных прямых можно вычислить по формуле: N = n(n + 1) / 2. 1 При этом каждую пару прямых нужно посчитать дважды: можно провести сначала первую прямую, потом вторую, а можно — сначала вторую, потом первую. 1
Количество способов провести пару горизонтальных прямых можно найти по формуле: M = m(m + 1) / 2. 1
Общее количество способов вырезать прямоугольник равно произведению количества способов провести вертикальные и горизонтальные прямые: N × M. 1
Ещё один способ — учёт возможных ориентаций прямоугольника. 2 Например, если нужно найти, сколькими способами из клетчатого прямоугольника 5 × 8 можно вырезать прямоугольник 1 × 2, нужно учесть, что прямоугольник 1 × 2 может быть вырезан в разных ориентациях (горизонтально и вертикально). 2 В этом случае количество способов для горизонтальной ориентации (5 × 7) нужно сложить с количеством способов для вертикальной ориентации (4 × 8). 2