割り切れること

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で除したとき、割り切れる数をただ1個含む。これをk-2,k-3と繰り返すことで、\frac{n(n-1)...(n-k+1)}{k(k-1)...1}の分子は、kで割り切れるただ1個の数、それを除いたあとは、k-1で割り切れるただ1個の数、それを除いた後は、k-2で割り切れるただ1個の数、が順次決まり、結局、分母で割り切れることがわかる。
これから、\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のときのそれであるから、示せたことになる。