二項係数nCmが整数になることの証明

二項係数(組み合わせの数)が整数になることの証明をメモしておきます。


これについて、2通りの証明法が知られています。

${}_{n}\mathrm{C}_{m}$ が整数であることの証明

 

 ① 素因数の個数に着目した証明

 

 ② 数学的帰納法による証明

 

$${}_{n}\mathrm{C}_{m}=\dfrac{n!}{m!(n-m)!} \quad \cdots (*)$$が整数になることを示すには、$n!$

もしくは、連続する$m$個の整数の積$$\small n(n-1)\cdots(n-m+1)=\dfrac{n!}{(n-m)!}$$が$m!$で割り切れることを示せばOKです。

証明①では「ルジャンドルの定理」を利用し、分子と分母の素因数の個数を評価して示します。証明②ではいわゆる「強化帰納法」を用います。


証明①

 

$(*)$の分子 $n!$ に含まれる素因数 $p$ の個数は$$\small \displaystyle\sum_{i=1}^{\infty}\left[ \dfrac{n}{p^i} \right]$$であり、$(*)$の分母 $m!(n-m)!$ に含まれる素因数 $p$ の個数は$$\small \displaystyle\sum_{i=1}^{\infty}\left(\left[ \dfrac{m}{p^i} \right]+\left[ \dfrac{n-m}{p^i} \right]\right)$$となる(ルジャンドルの定理による)。
ガウス記号について一般に$$[x+y] \geqq [x]+[y]$$が成り立つから、$$\small \displaystyle \sum_{i=1}^{\infty}\left[ \dfrac{n}{p^i} \right] \geqq \sum_{i=1}^{\infty}\left(\left[ \dfrac{m}{p^i} \right]+\left[ \dfrac{n-m}{p^i} \right]\right)$$となる。これがすべての素因数 $p$ について成り立つから、 $(*)$の分子に含まれる素因数 $p$ の個数は$(*)$の分母よりも多い。故に、連続する $m$ 個の整数の積は $m!$ で割り切れる。

 

したがって、$${}_{n}\mathrm{C}_{m}=\dfrac{n!}{m!(n-m)!}$$は整数であることが示された。

この方針による証明は非常に簡明です。証明中で用いた不等式$$\small [x+y] \geqq [x]+[y] \quad \cdots (★)$$は以下のように証明可能です。

不等式$(★)$の証明

 

$[x]=m$、$[y]=n$ $(m, n \in Z)$ と置くと、ガウス記号の定義より$$\begin{cases}
m \leqq x<m+1 \\
n \leqq y<n+1
\end{cases}$$が成り立つ。これより辺々を加えると$$m+n \leqq x+y<m+n+2$$となるから$$[x+y]=m+n \text{ または } m+n+1$$を得る。一方で $[x]+[y]=m+n$ であるから、$$[x+y] \geqq [x]+[y]$$が成立する。


証明②

 

連続する$m$個の整数の積$$\small \mathrm{P}(n,m)=n(n+1)\cdots(n+m-1)$$が $m!$ で割り切れることを数学的帰納法で証明する。

 

$n=1$ のとき、および $m=1$ のときは明らかに $\mathrm{P}(n,m)$ が $m!$ で割り切れる。

 

以下、$n+m$ に関する数学的帰納法で証明する。$n+m \leqq N$ のとき $\mathrm{P}(n,m)$ が $m!$ で割り切れると仮定して、$n+m=N+1$ の場合を考える。

 

$n=1$ や $m=1$ のときは成り立つから、$n>1$、$m>1$ としてよい。$\mathrm{P}(n,m)$は$$\small \begin{align} & \quad \ \mathrm{P}(n,m) \\ &=n(n+1)\cdots(n+m-1) \\ &=n(n+1)\cdots(n+m-2)(n-1) \\ & \quad \quad +n(n+1)\cdots(n+m-2)m \\ &=(n-1)n(n+1)\cdots(n-1+m-1) \\ & \quad \quad +n(n+1)\cdots(n+m-1-1)m \\ &=\mathrm{P}(n-1,m)+\mathrm{P}(n,m-1)\cdot m\end{align}$$と変形できる。いま、$(n-1)+m=n+(m-1)=N$ であるから、帰納法の仮定より $\mathrm{P}(n-1,m)$ は $m!$ で割り切れ、$a(n,m-1)$ は $(m-1)!$ で割り切れる。

 

よって $\mathrm{P}(n,m-1)m$は、$m!$で割り切れるから、$\mathrm{P}(n,m)$は$m!$で割り切れる。これより、$n+m=N+1$ の場合でも仮定が成立するから、数学的帰納法によりすべての $n$、$m$ について $\mathrm{P}(n,m)=n(n+1)\cdots(n+m-1)$ は $m!$ で割り切れる。

 

したがって、$${}_{n}\mathrm{C}_{m}=\dfrac{n!}{m!(n-m)!}$$は整数であることが示された。


上の証明では積 $\mathrm{P}(n,m)$ を考えましたが、二項係数のまま議論を進めると以下のようになります。


証明②(改)

$${}_{n}\mathrm{C}_{m}=\dfrac{n!}{m!(n-m)!} \quad \cdots (*)$$が整数になることを$n$についての帰納法で示す。以下、$0!=1$ と定める。

 

$n=1$ のとき、明らかに ${}_{n}\mathrm{C}_{m}$ は $n!$ で割り切れる。

 

$n=k$ のとき、$1 \leqq m \leqq k$ を満たすすべての $m$ について ${}_{n}\mathrm{C}_{m}$ が整数だと仮定する。二項係数について成り立つ以下の関係式$${}_{k+1}\mathrm{C}_{m}={}_{k}\mathrm{C}_{m}+{}_{k}\mathrm{C}_{m-1}$$および仮定より、$1 \leqq m \leqq k$ を満たすすべての $m$ について ${}_{k+1}\mathrm{C}_{m}$ も整数となる。また、$${}_{k+1}\mathrm{C}_{0}={}_{k+1}\mathrm{C}_{k+1}=1$$であり整数となる。よって、$n=k+1$ のときも$(*)$は整数になる。

 

したがって、数学的帰納法により$(*)$が整数であることが示された。


(コメント)

これらの他に「二項係数${}_{n}\mathrm{C}_{m}$は組み合わせを取ったときの総数を表すから整数」という証明もあり得ますが、これが自明だと感じられない人も多いかと思い、証明法をまとめてみました。帰納法だとやや答案風に書くのが手間でしょうか。入試ではこの証明はまともに出題されませんが、やり方を知っておくといざという時に役立ちます。

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です