二項係数

${}_n{\mathrm{C}}_r={}_n{\mathrm{C}}_{n-r}$

${}_n{\mathrm{C}}_r={}_{n-1}{\mathrm{C}}_{r-1}+{}_{n-1}{\mathrm{C}}_r$

証明

${}_{n-1}{\mathrm{C}}_{r-1}=\frac{(n-1)!}{(r-1)!(n-1-r+1)!}=\frac{(n-1)!}{(r-1)!(n-r)!}$

$=\frac{(n-1)(n-2)\mathrm{・}\mathrm{・}\mathrm{・}\{n-(r-1)\}(n-r)!}{(r-1)!(n-r)!}=\frac{(n-1)(n-2)\mathrm{・}\mathrm{・}\mathrm{・}\{n-(r-1)\}}{(r-1)!}$

${}_{n-1}{\mathrm{C}}_r=\frac{(n-1)!}{r!(n-r-1)!}=\frac{(n-1)(n-2)\mathrm{・}\mathrm{・}\mathrm{・}(n-r)\{n-(r+1)\}!}{r!\{n-(r+1)\}!}$

$=\frac{(n-1)(n-2)\mathrm{・}\mathrm{・}\mathrm{・}(n-r)}{r!}$

よって、

${}_{n-1}{\mathrm{C}}_{r-1}+{}_{n-1}{\mathrm{C}}_r$

$=\frac{(n-1)(n-2)\mathrm{・}\mathrm{・}\mathrm{・}\{n-(r-1)\}}{(r-1)!}+\frac{(n-1)(n-2)\mathrm{・}\mathrm{・}\mathrm{・}(n-r)}{r!}$

$=\frac{r!(n-1)(n-2)\mathrm{・}\mathrm{・}\mathrm{・}\{n-(r-1)\}+(r-1)!(n-1)\mathrm{・}\mathrm{・}\mathrm{・}\{n-(r-1)\}(n-r)!}{r!(r-1)!}$

$=\frac{(r-1)!(n-1)(n-2)\mathrm{・}\mathrm{・}\mathrm{・}\{n-(r-1)\}\{r+(n-r)\}}{r!(r-1)!}$

$=\frac{n(n-1)(n-2)\mathrm{・}\mathrm{・}\mathrm{・}\{n-(r-1)\}}{r!}$

$=\frac{n(n-1)(n-2)\mathrm{・}\mathrm{・}\mathrm{・}\{n-(r-1)\}(n-r)!}{r!(n-r)!}$

$=\frac{n!}{r!(n-r)!}$

$={}_n{\mathrm{C}}_r$