2014/08/30

スターリング数の漸化式と3つの意味

分野: 場合の数  レベル: マニアック

第二種スターリング数 $S(n,k)$ の同値な性質を3つ解説します。あまり馴染みのない数ですが美しい性質を持っています。

スターリング数とは

スターリング数は(基本的には)自然数 $n$ と $k$(ただし $n\geq k$)に対して定まる自然数です。このような意味では二項係数${}_{n}C_{k}$ と似ているのでスターリング数のことを${}_{n}S_{k}$ と表すこともあります。

※二項係数の場合と同様に,$n$ が $0$ の場合もスターリング数を定義することができます。便宜上 $S(0,0)=1, S(n,0)=0\:(n\in \mathbb{N})$ となっています。

第二種スターリング数に似た概念(本質的には同じ)として第一種スターリング数もあります。このページでは組み合わせ的な意味がより分かりやすい第二種スターリング数のみを扱います。

以下の3つの性質うち1つを定義とすれば残りの2つは定理として導かれます。

スターリング数の漸化式

二項係数における漸化式:${}_{n}C_k={}_{n-1}C_{k-1}+{}_{n-1}C_{k}$(→二項係数の有名公式)に対応するものです。

スターリング数の性質1:
任意の自然数 $n$ に対して $\:S(n,1)=S(n,n)=1\:$かつ任意の $n,k$
$(k\geq 2, n \geq k+1)$ に対して $S(n,k)=S(n-1,k-1)+kS(n-1,k)$

スターリング数

この漸化式を用いてスターリング数を順々に求めることができます。表を書くと分かりやすいです。特定のマスの値は左上と上の値から求まります。

二項係数におけるパスカルの三角形よりは少し複雑ですがそれでも美しい関係式です。

スターリング数と組み合わせ

スターリング数の性質2:
区別できる $n$ 個のものを区別できない $k$ グループに分類する方法の場合の数は $S(n,k)$ である。

※ $0$ 人のグループはあってはなりません。

性質1と性質2が同値であることを証明します。

証明

まず,任意の自然数 $n$ に対して $S(n,1)=S(n,n)=1$ は自明。

あとは漸化式が成立すること証明する。
$S(n,k)$ は以下の $2$ つの場合の数の和で表される。

  • まず特定の $n-1$ 個のものを $k-1$ グループに分けておいて最後の $1$ つを $k$ グループ目とする場合の数
  • まず特定の $n-1$ 個のものを $k$ グループに分けておいて最後の $1$ つをいずれかに加える場合の数

ひとつめは $S(n-1,k-1)$ 通りでふたつめが $kS(n-1,k)$ 通りなので「性質1」の漸化式が成立することが分かる。

スターリング数と展開係数

二項係数における二項定理に対応するものです。Wikipediaではこれをスターリング数の定義としています。

スターリング数の性質3:
$f_k(x)=x(x-1)\cdots(x-k+1)$ とおくとき $x^n=\displaystyle\sum_{k=1}^nS(n,k)f_k(x)$

$f_k(x)$ は順列${}_xP_{k}$ を関数とみなしたものです。

$n=3, 4$ の場合のスターリング数
$x^3=x+3x(x-1)+x(x-1)(x-2)$
より $S(3,1)=1, S(3,2)=3, S(3,3)=1$

$x^4=x+7x(x-1)+6x(x-1)(x-2)+x(x-1)(x-2)(x-3)$
より $S(4,1)=1, S(4,2)=7, S(4,3)=6, S(4,4)=1$

性質1と性質3の同値性はやや手強いです,もしかしたら難関大学の入試にでるかもしれません。まず性質3→性質1を示します。その結果を使えば性質1→性質3の証明は簡単です。

性質3→性質1の証明

$x^n=\displaystyle\sum_{k=1}^nS(n,k)f_k(x)$
において最高次の係数を比較すると $S(n,n)=1$ が分かる。
また,$x=1$ を代入すると $S(n,1)=1$ が分かる。

あとは漸化式を示すのが目標なので $x^{n-1}$ の展開式を変形して $x^n$ の展開式を作っていく。
$x^{n-1}=\displaystyle\sum_{k=1}^{n-1}S(n-1,k)f_k(x)\\
=\displaystyle\sum_{k=2}^{n}S(n-1,k-1)f_{k-1}(x)$
この両辺に $x$ をかけて $x=(x-k+1)+(k-1)$ であることに注意すると,
$x^n=\displaystyle\sum_{k=2}^{n}S(n-1,k-1)(x-k+1)f_{k-1}(x)\\+\displaystyle\sum_{k=2}^{n}S(n-1,k-1)(k-1)f_{k-1}(x)\\
=\displaystyle\sum_{k=2}^nS(n-1,k-1)f_{k}(x)
+\displaystyle\sum_{k=1}^{n-1}S(n-1,k)kf_{k}(x)\:\:(※)$
ここで右辺第一項は $f_{k}(x)$ の定義を使い,第二項は添字を平行移動させた。
$f_k(x)$ の係数を比較して性質1の漸化式を得る。

(性質1→性質3の証明)
帰納法で示す。 $n-1$ のときまで性質3が正しいと仮定すると,上式の(※)と性質1より $n$ のときも成立。

このようにスターリング数は漸化式,組み合わせの意味,代数的性質のどれを使っても特徴づけできます!組み合わせの分野ではこのようにいろいろな特徴づけができる量が多いです。場面に応じて都合の良いものを使いましょう。

なお,スターリング数は二項係数とシグマを使って書き表すことができます。→全射の個数の証明とベル数

今回はかなり時間をかけた自信作です!
分野: 場合の数  レベル: マニアック