第１種スターリング数 s(n,k) 計算ツール

結果

第１種スターリング数 s(n,k)

-50

符号付きの値

n	5
k	2

第１種スターリング数とは

符号付き第１種スターリング数 $s(n,k)$ は、下降階乗 $x(x-1)(x-2)\dots(x-n+1)$ を $x$ の通常のべき乗に展開したときに現れる係数です。その絶対値 $c(n,k) = |s(n,k)|$ は、n 個の要素の順列のうち、ちょうど k 個の互いに素な巡回置換（サイクル）に分解されるものの個数を表します。両者は符号の規則 $s(n,k) = (-1)^{n-k} c(n,k)$ によって結びついています。本ツールは下降階乗の係数の慣習に合わせ、符号付きの値を返します。

使い方

2 つの非負整数を入力します。n（サイズを表すパラメータ）と k（サイクル数、すなわちべき指数）です。計算ボタンを押すと $s(n,k)$ が表示されます。k が n より大きい場合は 0、$s(n,n)$ は常に 1、$s(0,0)$ は定義により 1 となります。

計算式の解説

漸化式 $$s(n+1,k) = s(n,k-1) - n\,s(n,k)$$ を用いて、小さな動的計画法（DP）の表を作ります。初期値は $s(0,0)=1$ で、$n>0$ のとき $s(n,0)=0$、$k>0$ のとき $s(0,k)=0$ とします。各行は直前の行から計算できるため、大きな参照表は不要です。漸化式の負の項が、符号が交互に入れ替わる仕組みを生み出しています。

s(n+1,k) が s(n,k-1) と s(n,k) から作られることを示す漸化式の図 — 漸化式は、前の行の2つの値から各スターリング数を組み立てます。

計算例

$s(5,2)$ を求めてみましょう。第 5 行の符号なしサイクル数は $c(5,1)=24$、$c(5,2)=50$、$c(5,3)=35$、$c(5,4)=10$、$c(5,5)=1$ です。符号は $(-1)^{5-2} = -1$ なので、$$s(5,2) = -50$$ となります。検算: $$x(x-1)(x-2)(x-3)(x-4) = x^5 - 10x^4 + 35x^3 - 50x^2 + 24x$$ であり、$x^2$ の係数はたしかに $-50$ です。