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

第二種スターリング数 S(n,k)S(n,k) と呼ばれる数について,同値な性質を3つ解説します。

スターリング数とは

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

  • 二項係数と同様,nn00 の場合も考えることがあります。具体的には S(0,0)=1,S(n,0)=0(n=1,...)S(0,0)=1, S(n,0)=0\:(n=1,...) です。

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

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

スターリング数の漸化式

二項係数における漸化式: nCk=n1Ck1+n1Ck{}_{n}\mathrm{C}_k={}_{n-1}\mathrm{C}_{k-1}+{}_{n-1}\mathrm{C}_{k}→二項係数の有名公式)に対応するものです。

スターリング数の性質1
  • 任意の自然数 nn に対して
    S(n,1)=S(n,n)=1\:S(n,1)=S(n,n)=1\:

  • 任意の n,k(k2,nk+1)n,k\:(k\geq 2, n \geq k+1) に対して
    S(n,k)=S(n1,k1)+kS(n1,k)S(n,k)=S(n-1,k-1)+kS(n-1,k)

スターリング数

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

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

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

スターリング数の性質2

区別できる nn 個のものを区別できない kk グループに分類する方法の数は S(n,k)S(n,k) である。

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

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

証明

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

あとは漸化式が成立すること証明する。

S(n,k)S(n,k) は以下の 22 つの場合の数の和で表される。

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

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

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

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

スターリング数の性質3

fk(x)=x(x1)(xk+1)f_k(x)=x(x-1)\cdots(x-k+1)

とおくとき

xn=k=1nS(n,k)fk(x)x^n=\displaystyle\sum_{k=1}^nS(n,k)f_k(x)

fk(x)f_k(x) は順列 xPk{}_x\mathrm{P}_{k} を関数とみなしたものです。

  • n=3n=3 の場合:
    x3=x+3x(x1)+x(x1)(x2)x^3=x+3x(x-1)+x(x-1)(x-2)
    より
    S(3,1)=1,S(3,2)=3,S(3,3)=1S(3,1)=1, S(3,2)=3, S(3,3)=1

  • n=4n=4 の場合:
    x4=x+7x(x1)+6x(x1)(x2)+x(x1)(x2)(x3)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)=1S(4,1)=1, S(4,2)=7, S(4,3)=6, S(4,4)=1

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

性質3→性質1の証明

xn=k=1nS(n,k)fk(x)x^n=\displaystyle\sum_{k=1}^nS(n,k)f_k(x)

において最高次の係数を比較すると S(n,n)=1S(n,n)=1 が分かる。

また,x=1x=1 を代入すると S(n,1)=1S(n,1)=1 が分かる。

あとは漸化式を示すのが目標なので xn1x^{n-1} の展開式を変形して xnx^n の展開式を作っていく。

xn1=k=1n1S(n1,k)fk(x)=k=2nS(n1,k1)fk1(x)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)

この両辺に xx をかけて x=(xk+1)+(k1)x=(x-k+1)+(k-1) であることに注意すると,

xn=k=2nS(n1,k1)(xk+1)fk1(x)+k=2nS(n1,k1)(k1)fk1(x)=k=2nS(n1,k1)fk(x)+k=1n1S(n1,k)kfk(x)()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)\:\:(※)

ここで右辺第一項は fk(x)f_{k}(x) の定義を使い,第二項は添字を平行移動させた。

fk(x)f_k(x) の係数を比較して性質1の漸化式を得る。

性質1→性質3の証明

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

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

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

第一種スターリング数

スターリング数の性質3では, x(x1)(xk+1)x(x-1)\cdots (x-k+1) という「下降階乗冪」が登場しましたが,そのかわりに x(x+1)(x+k1)x(x+1)\cdots (x+k-1) という「上昇階乗冪」を考えると第一種スターリング数(の定義 or 性質)になります。第一種スターリング数は2023年の名大第4問に登場しました。

今回はかなり時間をかけた自信作です!