二項係数の有名公式一覧と2つの証明方針

$n$ 個のものから $r$ 個のものを選ぶ組み合わせの数は，$n-r$ 個の「選ばないものを選ぶ」組み合わせの数に等しい。

${}_n\mathrm{C}_r=\dfrac{n!}{r!(n-r)!}\\ =\dfrac{n!}{(n-r)!\{n-(n-r)\}!}\\ ={}_n\mathrm{C}_{n-r}$

（特定のものAを含む）$n$ 個のものから $r$ 個のものを選ぶ組み合わせの数は

「Aを選ばず残り $n-1$ 個の中から $r$ 個のものを選ぶ組み合わせの数」
＋「Aを選び残り $n-1$ 個の中から $r-1$ 個のものを選ぶ組み合わせの数」

に等しい。

右辺を変形していく。

${}_{n-1}\mathrm{C}_r+{}_{n-1}\mathrm{C}_{r-1}\\ =\dfrac{(n-1)!}{r!(n-1-r)!}+\dfrac{(n-1)!}{(r-1)!(n-r)!}\\ =\dfrac{(n-1)!}{(r-1)!(n-1-r)!}\left(\dfrac{1}{r}+\dfrac{1}{n-r}\right)\\ =\dfrac{n!}{r!(n-r)!}\\ ={}_n\mathrm{C}_r$

$n$ 人から $r$ 人採り，1人をリーダーにする組み合わせの数を2通りの方法で考える。

「$n$ 人の中から $r$ 人選んでそのグループのリーダーを選ぶ組み合わせの数」
＝「$n$ 人の中から1人リーダーを選んで残り $n-1$ 人から $r-1$ 人選ぶ組み合わせの数」

$r{}_{n}\mathrm{C}_r\\ =r\dfrac{n!}{r!(n-r)!}\\ =n\dfrac{(n-1)!}{(r-1)!(n-r)!}\\ =n{}_{n-1}\mathrm{C}_{r-1}$

3通りの証明方法を紹介する。

1. $(1+x)^n=\displaystyle\sum_{k=0}^n{}_n\mathrm{C}_kx^k$
   に対して「両辺微分して $x$ をかける」ことを $n$ 回繰り返す。その結果に $x=-1$ を代入すると，右辺は $\displaystyle\sum_{k=1}^nk^n(-1)^k{}_n\mathrm{C}_k$ になる。左辺は $n!(-1)^n$ になる。
   （左辺について微分をきちんと計算するのはしんどいが，$(1+x)$ を含む項は $x=-1$ を代入して消えることに注意すると $x=-1$ を代入した結果ならわりと簡単に計算できる）

2. 包除原理を使って「$1$ から $n$ が全て現れる長さ $n$ の数列の個数」を数えることでも $\displaystyle\sum_{k=1}^nk^n(-1)^{n-k}{}_n\mathrm{C}_k=n!$ が導出できる。

3. 2と全く同じことだが，全射の個数の公式で $k=n$ とすることでも同じ式を得る。