割り切れること - ryamadaの遺伝学・遺伝統計学メモ

n個をk個とn-k個とに分ける場合の数は $\frac{n!}{k!(n-k)!}$ と表せる。この割り算が、どうして、割り切れるのかという、ごくごく単純なことを考える。
今、 $\frac{n!}{k!(n-k)!}=\frac{n(n-1)...(n-k+1)}{k(k-1)...1}$ と変形できる。分子と分母はそれぞれ、k個の連続する自然数の積である。
ここで、分子はk個の連続する自然数からなるから、この数はkで除したときその余りが、0,1,2,...k-1のいずれかであって、余りが等しいものはない。言い換えれば、分子の唯一つの数がkで割り切れる。
今、kで割り切れる数を除いた、k-1個の数を考える。これらは、kで除したとき、余りが、1,2,...k-1となるような数であるから、 $k\times m +i$ ( $i=1,2,...,k-1$ )、ただし $m \in N$ (自然数)と表せる。変形して、 $(k-1)\times m +m+i$ 。ここでmの値によらず、 $m+i$ ( $i=1,2,...,k-1$ )は、k-1で除したとき、割り切れる数をただ１個含む。これをk-2,k-3と繰り返すことで、 $\frac{n(n-1)...(n-k+1)}{k(k-1)...1}$ の分子は、kで割り切れるただ１個の数、それを除いたあとは、k-1で割り切れるただ１個の数、それを除いた後は、k-2で割り切れるただ１個の数、が順次決まり、結局、分母で割り切れることがわかる。
これから、 $\frac{n!}{k!(n-k)!}$ が割り切れることが示された。
さらに $\frac{n!}{\prod_{i=1}^{k} n_i!}$ 、ただし $\sum_{i=1}^{k} n_i = n$ が割り切れることもわかる。それは、今、 $k=2$ のときにはすでに示してあるから、 $k=\kappa$ のときに成り立てば、 $k=\kappa+1$ のときに成り立つことを示せばよい。
$\frac{n!}{\prod_{i=1}^{\kappa} n_i!$ が、任意の自然数 $n,n_i$ について割り切れるとする。
$\frac{(n+x)!}{\prod_{i=1}^{\kappa} n_i! \times x!}$ は、 $\frac{n'!}{\prod_{i=1}^{\kappa+1}n_i'!}$ と表せるから、これが割り切れることを示せばよい。
式変形して
$\frac{(n+x)!}{x!n!}\frac{x!n!}{\prod_{i=1}^{\kappa} n_i! \times x!}$
$\frac{(n+x)!}{x!n!}\frac{n!}{\prod_{i=1}^{\kappa} n_i!}$
この左側の分数は、 $k=2$ のときの組合せの数で割り切れる。右側の分数は $k=\kappa$ のときのそれであるから、示せたことになる。