Зачем делить в комбинаторике

Чтобы задать прямоугольник, достаточно выбрать его границы, то есть четыре линии сетки, которые будут его ограничивать. Из этих четырех линий сетки две вертикальные и две горизонтальные. Сначала посчитаем, сколькими способами можно выбрать пару вертикальных линий. Всего линий сетки штук: столбцов , промежутков между ними , а также есть две линии сетки, ограничивающие сам квадрат . Поэтому упорядоченную пару вертикальных линий сетки можно выбрать способами, так как выбор последовательный и независимый. При этом нам не важно, в каком порядке выбираются эти линии сетки: в любом случае более левая линия сетки будет левой границей, а более правая — правой. Поэтому посчитанное количество нужно поделить пополам, так как каждый интересующий нас способ учтен дважды: .

Итак, пару вертикальных границ можно выбрать способами. Аналогично пару горизонтальных границ также можно выбрать способами. Учитывая, что любой паре вертикальных границ может соответствовать любая пара горизонтальных границ, и все такие комбинации дадут нам различные прямоугольники, эти два количества нужно перемножить: .