\begin{equation}
{}_n C_r = +{}_{n -1} C_r +{}_{n -1} C_{r -1}
\end{equation}
個から
個を取り出す組合せと
個から
個を取り出す組合せの和は、
個から
個を取り出す組合せに等しい、というものです。
組合せの定義から導くことができます。
\begin{eqnarray}
{}_n C_r &=& \frac{n!}{(n -r)! \ r!} \\
&=& \frac{n}{n -r} \cdot \frac{(n -1)!}{(n -1 -r)! \ r!} \\
&=& \left( 1 +\frac{r}{n -r} \right) \frac{(n -1)!}{(n -1 -r)! \ r!} \\
&=& \frac{(n -1)!}{(n -1 -r)! \ r!} +\frac{r}{n -r} \cdot \frac{(n -1)!}{(n -1 -r)! \ r!} \\
&=& \frac{(n -1)!}{(n -1 -r)! \ r!} +\frac{(n -1)!}{(n -r)! \ (r -1)!} \\
&=& \frac{(n -1)!}{(n -1 -r)! \ r!} +\frac{(n -1)!}{(n -1 -r +1)! \ (r -1)!} \\
&=& {}_{n -1} C_r +{}_{n -1} C_{r -1}
\end{eqnarray}
