コンビネーションの関係式の証明とパスカルの三角形について

1. コンビネーションの関係式1

はるか

${}_{n}\mathrm{C}_{k}$は組み合わせでも使った記号。

1.1. 数式による証明

${}_{n+1}\mathrm C_{k+1}={}_{n}\mathrm{C}_{k}+ {}_{n}\mathrm{C}_{k+1}$の左辺を計算する。

$$\begin{align*} {}_{n}\mathrm{C}_{k}+ {}_{n}\mathrm{C}_{k+1}&=\dfrac{n!}{k!\cdot(n-k)!}+\dfrac{n!}{(k+1)!(n-k-1)!} \\ &=\dfrac{n!}{k!(n-k)!}+\dfrac{n!}{(k+1)!(n-k-1)!} \\ &=\dfrac{n!(k+1)}{(k+1)!(n-k)!}+\dfrac{n!(n-k)}{(k+1)!(n-k)!} \\ &=\dfrac{n!(k+1+n-k)}{(k+1)!(n-k)!} \\ &=\dfrac{(n+1)!}{(k+1)!(n-k)!} \\ &=\dfrac{(n+1)!}{(k+1)!\lbrace n+1-(k+1)\rbrace!} \\ &= {}_{n+1}\mathrm C_{k+1} \end{align*}$$

1.2. ポイント

今回のコンビネーションの関係式のポイントは

パスカルの三角形で確認できるということです。

このように、パスカルの三角形は隣り合う項を足し合わせると、その間にある下の項になるという関係が成り立ちます。実際に、パスカルの三角形では、${}_{2}\mathrm C _{0} +{}_{2}\mathrm C _{1} = {}_{3}\mathrm C _{1}$となるように、先ほど証明した式が成り立つことを確認することができます。

2. コンビネーションの関係式2

$k=-1$にはならないことと定義上$_{n}\mathrm C _{k}$は0にはならないことを考慮して、与えら式を式変形すると、

$$\dfrac{{}_{n+1}\mathrm C_{k+1}}{{}_{n}\mathrm{C}_{k}}=\dfrac{n+1}{k+1}$$

となるため、この式を示せばよい。

$$\begin{align*} \dfrac{{}_{n+1}\mathrm C_{k+1}}{ {}_{n}\mathrm{C}_{k}} &=\dfrac{\dfrac{(n+1)!}{(k+1)!(n-k)!}}{\dfrac{n!}{k!(n-k)!}} \\ &=\dfrac{k!}{n!}\cdot\dfrac{(n+1)!}{(k+1)!} \\ &=\dfrac{n+1}{k+1} \end{align*}$$

となる。そのため、$\dfrac{_{n+1}\mathrm C_{k+1}}{_{n}\mathrm{C}_{k}}=\dfrac{n+1}{k+1}$この両辺に$(k+1)_{n} \mathrm C _{k}$をかけると与えられ式になる。

$$(k+1){}_{n+1}\mathrm C_{k+1}=(n+1){}_{n}\mathrm{C}_{k}$$