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

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

Примеры

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

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

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

Примечания

1. Joshi, 2015.

Литература

• Joshi, Mark (2015), "Double Counting", Proof Patterns, Springer International Publishing, pp. 11–17, doi:10.1007/978-3-319-16250-8_2, ISBN 978-3-319-16249-2