Двойной подсчёт

Двойной подсчёт (или подсчёт двумя способами) — тип доказательства равенства двух выражений, представляя их как два способа подсчета элементов одного множетва.

Примеры

• Лемма о рукопожатиях: каждый неориентированный граф содержит чётное число вершин нечётной степени.

• Тождество Вандермонда — тождество для сумм биномиальных коэффициентов, которое может быть доказано двойным подсчетом.

• Квадратное пирамидальное число. Равенство между суммой первых $n$ квадратвов и кубическим многочленом может быть показано путем двойного подсчета троек чисел $x$, $y$, и $z$, где $z$ больше любого из двух других чисел.