第二種スターリング数による累乗和の公式

階乗冪,スターリング数,累乗和

1407

今回紹介するのは $1$ から $n$ までの自然数の累乗の和
$\sum_{k = 1}^{n} k^{s}$
の一般項についてです．
一番有名な表示は，ベルヌーイ数を使った次の公式ですね

Faulhaberの公式

$\sum_{k = 1}^{n} k^{s} = \frac{1}{s + 1} \sum_{i = 0}^{s}_{s + 1} C_{i} B_{i} n^{k + 1 - i}$

この公式については他の方がたくさん解説しているので特にここでは扱いません．

下降階乗冪の総和

今回扱うのは，以下に示す，下降階乗冪 $n^{\underset{―}{i}} = n (n - 1) (n - 2) \dots (n - i + 1)$
の総和公式を用いた方法です．連続する整数の積の総和が連続する整数の積として表現できることは有名なので知っている方も多いと思います．それを定式化したのが以下の公式です．

下降階乗冪の総和

$n^{\underset{―}{s}} = n (n - 1) (n - 2) \dots (n - s + 1)$ とする．
$n \in N$ に対して，次の等式が成立する．
$\sum_{k = 1}^{n} k^{\underset{―}{s}} = \frac{1}{s + 1} (n + 1)^{\underset{―}{s + 1}}$

この公式は数列における階差や総和を，関数の微積分に関連づけて扱うという「和差分法」の考え方が背景にあるのですが，和差分については本記事では割愛します．気になる方は調べてみてください.

$k^{\underset{―}{s}} = \frac{1}{s + 1} (s + 1) k^{\underset{―}{s}} = \frac{1}{s + 1} {(k + 1) k^{\underset{―}{s}} - (k - s) k^{\underset{―}{s}}} = \frac{1}{s + 1} {(k + 1)^{\underset{―}{s + 1}} - k^{\underset{―}{s + 1}}}$
であるから，
$\sum_{k = 1}^{n} k^{\underset{―}{s}} = \frac{1}{s + 1} \sum_{k = 1}^{s} {(k + 1)^{\underset{―}{s + 1}} - k^{\underset{―}{s + 1}}} = \frac{1}{s + 1} {(n + 1)^{\underset{―}{s + 1}} - 1^{\underset{―}{s + 1}}} = \frac{1}{s + 1} (n + 1)^{\underset{―}{s + 1}}$

実はこれを使えば，その場で特定の次数の累乗和の公式を作ることは簡単にできます．
$k^{s}$ を $k^{\underset{―}{1}}, k^{\underset{―}{2}}, \dots, k^{\underset{―}{s}}$ の一次結合で表してしまえばいいのです！
例を見ていきましょう．

$\sum_{k = 1}^{n} k^{1} = \sum_{k = 1}^{n} k^{\underset{―}{1}} = \frac{1}{2} (n + 1)^{\underset{―}{2}} = \frac{1}{2} n (n + 1)$
$k^{2} = k + k (k - 1)$ だから
$\sum_{k = 1}^{n} k^{2} = \sum_{k = 1}^{n} (k^{\underset{―}{1}} + k^{\underset{―}{2}}) = \frac{1}{2} (n + 1)^{\underset{―}{2}} + \frac{1}{3} (n + 1)^{\underset{―}{3}} = \frac{1}{6} n (n + 1) (2 n + 1)$
$k^{3} = k + 3 k (k - 1) + k (k - 1) (k - 2)$ だから
$\sum_{k = 1}^{n} k^{3} = \sum_{k = 1}^{n} (k^{\underset{―}{1}} + 3 k^{\underset{―}{2}} + k^{\underset{―}{3}}) = \frac{1}{2} (n + 1)^{\underset{―}{2}} + \frac{3}{3} (n + 1)^{\underset{―}{3}} + \frac{1}{4} (n + 1)^{\underset{―}{4}} = \frac{1}{4} n^{2} (n + 1)^{2}$

$k^{4} = k + 7 k (k - 1) + 6 k (k - 1) (k - 2) + k (k - 1) (k - 2) (k - 3)$ だから
$\sum_{k = 1}^{n} k^{4} = \sum_{k = 1}^{n} (k^{\underset{―}{1}} + 7 k^{\underset{―}{2}} + 6 k^{\underset{―}{3}} + k^{\underset{―}{4}}) = \frac{1}{2} (n + 1)^{\underset{―}{2}} + \frac{7}{3} (n + 1)^{\underset{―}{3}} + \frac{6}{4} (n + 1)^{\underset{―}{4}} + \frac{1}{5} (n + 1)^{\underset{―}{5}} = \frac{1}{30} n (n + 1) (2 n + 1) (3 n^{2} + 3 n - 1)$

だんだん下降階乗冪の和で表すのが辛くなってきますが，そういうときは，
$k^{5} = A k + B k (k - 1) + C k (k - 1) (k - 2) + D k (k - 1) (k - 2) (k - 3) + E k (k - 1) (k - 2) (k - 3) (k - 4)$
のようにおいて方程式を解きましょう．なんと驚くことに $k = 1, 2, 3, 4$ を順番に代入していけば係数が順番に求まっていくという仕掛けです．

下降階乗冪の和で表すこの方法，教科書に載っている「 $(k + 1)^{s} - k^{s}$ の総和を考えて〜 $\dots$ 」という方法よりよっぽど簡単な気がしませんか？

第二種スターリング数

特定の次数の累乗和の公式を作ることができるようになりましたが，やはり人は一般化したくなるものです．そこで，べき乗を下降階乗冪の和で表す時，その係数がどのような値になるかを見ていきましょう．
結論から言うとこれは以下に述べる「第二種スターリング数」というものになります．

第二種スターリング数

区別できる $s$ 個のものを空なしの $i$ 個の区別できないグループに分割する方法の総数を，第2種スターリング数といい， $_{s} S_{i}$ で表す．

第二種スターリング数は，べき乗を下降階乗冪の和として表したときの展開係数として現れる．
$k^{s} = \sum_{i = 1}^{s}_{s} S_{i} k^{\underset{―}{i}}$

一見驚きですが，下降階乗冪を順列の総数 $_{s} P_{i}$ だと思って見れば至極当たり前の等式です．

$k \geq s$ とする．区別できる $s$ 個のものを区別できる $k$ 個のグループに，(空を許して)分ける方法の総数は $k^{s}$ 通りである．
一方，この $k$ 個のグループのうち， $i$ 個にものが入っている分割の総数を考えると，
(区別できる $s$ 個を(空なしで) $i$ 個の区別できないグループに分割する方法の総数)
$\times$ ( $k$ 個のグループから $i$ 個を順序を区別して選ぶ方法の総数)
であるから， $_{s} S_{i}_{k} P_{i}$ に等しい
すなわち，次の等式が成り立つ
$k^{s} = \sum_{i = 1}^{s}_{s} S_{i}_{k} P_{i}$

$_{k} P_{i} = k^{\underset{―}{i}}$ であるから， $k \geq s$ の時，次の等式が成り立つことが分かる
$k^{s} = \sum_{i = 1}^{s}_{s} S_{i} k^{\underset{―}{i}}$
$k \geq s$ において等式が成り立つから，この等式の両辺は多項式として等しい．
よって $k < s$ においても等式が成り立つ事がわかる．

展開係数が第二種スターリング数になることが分かったので，あとは第二種スターリング数を与える計算式を用意すればOKです．

第二種スターリング数には，次の漸化式が成立する．
$_{s} S_{1} =_{s} S_{s} = 1 ，_{s} S_{i} =_{s - 1} S_{i - 1} + i_{s - 1} S_{i}$

特定の1つが単独で1つのグループに入るか否かで場合分けすれば導くことができます．

$_{s} S_{1} =_{s} S_{s} = 1$ の成立は定義より明らかであるから， $_{s} S_{i} =_{s - 1} S_{i - 1} + i_{s - 1} S_{i}$ を示す
区別できる $s$ 個のもののうち，特定の一つを $e$ とする．

$e$ が単独で一つのグループに入る場合
$e$ 以外の $s - 1$ 個を区別できない $i - 1$ 個に分ける方法の総数なので，
${{s-1}}S{i-1}$通り
それ以外の場合
$e$ 以外の $s - 1$ 個を区別できない $i$ 個に分ける方法の総数は${{s-1}}S_i$通り
$e$ を入れるグループの選び方が $i$ 通りだから
$i{{s-1}}S_i$通り

以上より，
$_{s} S_{i} =_{s - 1} S_{i - 1} + i_{s - 1} S_{i}$

こんな感じで表を書いていけばわかりやすいですね．

	$i = 1$	$i = 2$	$i = 3$	$i = 4$	$i = 5$	$i = 6$
$s = 1$	1
$s = 2$	1	1
$s = 3$	1	3	1
$s = 4$	1	7	6	1
$s = 5$	1	15	25	10	1
$s = 6$	1	31	90	65	50	1

結論

これらを踏まえると，第二種スターリング数を用いた次の累乗和の公式が得られます．

$1$ から $n$ までの自然数の累乗の和は,次のように表せる
$\sum_{k = 1}^{n} k^{s} = (n + 1) \sum_{i = 1}^{s} \frac{_{s} S_{i}}{i + 1} n^{\underset{―}{i}}$
ただし $s \in N, n \in N$ , $_{s} S_{i}$ は第二種スターリング数.
$n^{\underset{―}{i}} = n (n - 1) (n - 2) \dots (n - i + 1)$

$\sum_{k = 1}^{n} k^{s} = \sum_{k = 1}^{n} (\sum_{i = 1}^{s}_{s} S_{i} k^{\underset{―}{i}}) = \sum_{i = 1}^{s} (_{s} S_{i} \sum_{k = 1}^{n} k^{\underset{―}{i}})$
公式2(下降階乗冪の総和)より，
$\sum_{i = 1}^{s} (_{s} S_{i} \sum_{k = 1}^{n} k^{\underset{―}{i}}) = \sum_{i = 1}^{s} \frac{_{s} S_{i}}{i + 1} (n + 1)^{\underset{―}{i + 1}} = (n + 1) \sum_{i = 1}^{s} \frac{_{s} S_{i}}{i + 1} n^{\underset{―}{i}}$
よって
$\sum_{k = 1}^{n} k^{s} = (n + 1) \sum_{i = 1}^{s} \frac{_{s} S_{i}}{i + 1} n^{\underset{―}{i}}$