二項恒等式の二重数え上げによる証明

$n$ 人の男子と $n$ 人の女子からなる $2n$ 人の集合を考える。この $2n$ 人からちょうど $n$ 人の委員会を選ぶ方法の数を二通りに数える。

直接には、定義よりこの数は $\binom{2n}{n}$ である。単に $2n$ 個から $n$ 個を選んでいるだけだからである。

別の方法として、すべての有効な委員会を含まれる男子の人数で分類する。委員会がちょうど $k$ 人の男子を含む場合、すなわちある $k$ が $0 \le k \le n$ を満たすとき、その $k$ 人の男子は $\binom{n}{k}$ 通りで選べ、残りの $n-k$ 人は女子でなければならず、$n$ 人の女子から $\binom{n}{n-k}$ 通りで選ばれる。対称性の恒等式 $\binom{n}{n-k} = \binom{n}{k}$ より、ちょうど $k$ 人の男子を含む委員会の数は $\binom{n}{k} \cdot \binom{n}{k} = \binom{n}{k}^2$ である。

$n$ 人のすべての有効な委員会は $0$ から $n$ の間のある確定した男子の人数 $k$ を持ち、異なる $k$ の値で二重に数えられる委員会はないため、すべての $k$ について和を取ると委員会の総数は $\sum_{k=0}^{n} \binom{n}{k}^2$ となる。

両方の式が全く同じ委員会の集合を数えているため、それらは等しくなければならない:$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$。