この記事では$k$乗和の以下の公式を組合せ的に証明する方法を解説します。
$$ \sum_{i=1}^n i^k = \sum_{i=1}^k f(k,i) \binom{n+1}{i+1}$$
ここで$f(n,m)$は、区別できる$n$個のボールを区別できる$m$個の箱に入れる方法のうち、どの箱にも$1$個以上のボールが入っているようなものの総数とします。
\begin{eqnarray} \sum_{i=1}^n i&=& \binom{n+1}{2} \\ \sum_{i=1}^n i^2&=&\binom{n+1}{2} + 2\binom{n+1}{3} \\ \sum_{i=1}^n i^3&=&\binom{n+1}{2} + 6\binom{n+1}{3} + 6\binom{n+1}{4} \\ \sum_{i=1}^n i^4&=&\binom{n+1}{2} + 14\binom{n+1}{3} + 36\binom{n+1}{4} + 24\binom{n+1}{5} \end{eqnarray}
まず次の問題を解いてみます。
区別できる$n$個のボールと区別できる$k$個のタグがある。タグをボールに付ける方法は何通りあるか。ただし同じボールに複数のタグを付けてもよい。
この問題の答えは$n^k$になります。$1$番目のタグを付ける方法が$n$通り、$2$番目のタグを付ける方法が$n$通り、のように考えていくと$n$を$k$回掛け合わせれば答えがでることが分かります。
この問題を修正すると答えが$k$乗和になる問題を作ることができます。
区別できる$n+1$個のボールと区別できる$k+1$個のタグがあり、ボールは横一列に並んでいる。ボールにタグを付ける方法のうち、タグが付けられているボールの中で最も右に位置するボールに$k+1$番目のタグのみが付けられているようなものは何通りあるか。
この問題はタグが付けられている最も右のボールの位置で場合分けすることで解くことができます。
タグが付けられている最も右のボールの位置が$i+1$番目のとき、タグの付け方は$i^k$通りあります。よって$i=1,...,n$の場合を足し合わせることで答えが$1^k+\dots+n^k$であることが分かります。
この問題は別の方法でも解くことができて、タグが$1$個以上付けられているボールの個数で場合分けします。
タグが$1$個以上付けられているボールの個数が$i+1$個の場合、まず$n+1$個のボールから$i+1$個を選んだ後に、$i+1$番目に選ばれたボールに$k+1$番目のタグを付け、それから選ばれた$i+1$個のボールから$i+1$番目のボールを取り除いた$i$個のボールに$k$個のタグを付けていきます。ただしこのとき$i$個のボールのどれにも$1$個以上のタグが付けられているようにします。このような付け方は、区別できる$i$個のボールに区別できる$k$個のタグを付ける方法のうち、どのボールにも$1$個以上のタグが付いているようなものの総数を$f(k,i)$としたとき、$\binom{n+1}{i+1}f(k,i)$通りあります。よって$i=1,\dots,k$のすべての場合を足し合わせることで、答えが$\sum_{i=1}^k \binom{n+1}{i+1}f(k,i)$であることが分かります。
これら二つの解法で得られた答えは一致するので、$1^k+\dots+n^k=\sum_{i=1}^k \binom{n+1}{i+1}f(k,i)$が成り立ちます。
$f(n,m)$は$n$元集合から$m$元集合への全射の総数と一致します。全射の総数は包除原理やスターリング数の漸化式を使って効率的に計算できます。詳細は以下の記事を参考にしてください。