二項係数

${}_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)・・・\lbrace n-(r-1) \rbrace(n-r)!}{ (r-1)!(n-r)! }= \frac{ (n-1)(n-2)・・・\lbrace n-(r-1) \rbrace}{ (r-1)! }$

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

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

よって、

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

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

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

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

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

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

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

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