第二種スターリング数の母関数の組合せ論・計数子による解釈

1,2,3,…,nのn個の数字を、k種類の区別のないグループに分ける場合の数を、第二種スターリング数と言って、ここでは、S(n,k) と書きます。

すると、1,2,3,…,nのn個の数字を、k種類の区別のあるグループに分ける場合の数は、k!*S(n,k) となります。
これは、f:{1,2,…,n}→{1,2,…,k}の全射の場合の数でもあります。

ところで、
Σ[n=0,∞] k!*S(n,k)x^n/n! = (e^x - 1)^k
という公式があります。
右辺のx^n/n!の係数は、1,2,…,kの数字を重複を許してn個並べて、全種類の数字が少なくとも1回は使われているという条件をつけたときの場合の数とみなせます。（指数型計数子）

ここまではいいのですが、似たような公式
Σ[n=0,∞] S(n,k)x^n = x^k/(1-x)(1-2x)…(1-kx)
を計数子によって解釈する方法があれば、どうか教えてください。

No.1 ベストアンサー 回答者： 20080715 回答日時： 2008/10/25 11:01

Σ[n=0,∞] S(n,k)x^n = x^k/(1-x)(1-2x)…(1-kx) -------(☆)

等式(☆)の組合せ論的証明：
(☆)を示すには、
S(n,k)=Σ1^(a[1]-1)*2^(a[2]-1)*3^(a[3]-1)*…*k^(a[k]-1)
(和は a[1]+a[2]+a[3]+…+a[k]=n を満たす全ての正整数a[1],a[2],a[3],…,a[k]を動く)
を示せばいいです。

集合 {1,2,3…,n} の k 個のブロックへの各分割 π に対し、n のひとつの組成
a[1]+a[2]+a[3]+…+a[k]=n を対応させ、ちょうど
1^(a[1]-1)*2^(a[2]-1)*3^(a[3]-1)*…*k^(a[k]-1) 個の分割πが
この組成に対応するようにできます。
すなわち、πから1,2,…,r を除いたときに、ブロックの数が k-i 個になる最小の
r を a[k]+a[k-1]+…+a[k-i+1] とおくことによって、πに組成を対応させることが
できます。

上の証明は次の本にありました。
『 数え上げ組合せ論(1) 』 リチャード・P. スタンレイ

この回答への補足

二重投稿で失礼します。本当に感謝いたします。

0≦a[1]≦a[2]≦…≦a[k]≦j かつ a[1]+a[2]+…+a[k]=n
を満たす整数の組(a[1],a[2],…,a[k])の個数を p(j,k,n) すると、
Σp(j,k,n)*q^n = [j+k,j]

すごいですね。まだ理解するには至っていませんが、不定方程式の解の個数についていろいろ考えていました。例えば、

α[1]+α[2]+…+α[n]=k、かつ、α[i]=0または1
を満たす解の個数は二項係数、C(n,k)

α[1]+α[2]+…+α[k+1]=n+1、かつ、α[i]≧1
を満たす自然数解の個数は二項係数、C(n,k)

α[1]+α[2]+…+α[n]=k、かつ、α[i]≧0
を満たす整数解の個数は重複組合せ、H(n,k)

α[1]+α[2]+…=n、かつ、α[i]=1または2
を満たす整数解の個数をT[n]とすると、T[n]=T[n-1]+T[n-2]が成立し、フィボナッチ数列F[n]と比べると、T[n]=F[n+1]
さらに、Σ[n=0,∞]T[n]z^n=1/(1-z-z^2)となるので、それから少し考察することで、
T[n]=Σ[β[1]+2*β[2]=nの0以上の整数解] {C(β[1]+β[2],β[1])}
------(*)
が分かる。
例えばn=3のとき、
α[1]+α[2]+…=3、かつ、α[i]=1または2
の解は、3=1+1+1=1+2=2+1より３通りあるので、T[3]=3
このとき、
Σ[β[1]+2*β[2]=3の0以上の整数解] {C(β[1]+β[2],β[1])}
=Σ[(β[1],β[2])=(1,1),(3,0)] {C(β[1]+β[2],β[1])}
=C(2,1)+C(3,0)
=3
となり確かに成立している。

このことと比べて下記のことを悩んでおります。

f:{1,2,…,n}→{1,2,…,k}の全射の個数k!*S(n,k)を考えると、
Σ[n=0,∞] k!*S(n,k)x^n = k!*x^k/(1-x)(1-2x)…(1-kx)
つまり、
Σ[a[1]+a[2]+a[3]+…+a[k]=nの自然数の解]1^(a[1])*2^(a[2])*3^(a[3])*…*k^(a[k]) = k!*S(n,k)

これを、(*)の右辺に対応するものとすると、(*)の左辺に対応するものは何でしょうか？
全射の個数k!*S(n,k)を、不定方程式の解の個数「のみ」で書くことはできるのでしょうか？

補足日時：2008/10/30 13:06

この回答へのお礼

ありがとうございます。
２日間ずっと考えていますが、難しいですね。

分割数に関しては、次のような流れで母関数を説明できました。

正の整数 n を k 個の正の整数の和として表す方法の総数をp(n,k)とする。
x^k/(1-x)(1-x^2)…(1-x^k)
=x^k(1+x+x^2+x^3+…)(1+x^2+x^4+x^6+…)…{1+x^k+x^(2k)+x^(3k)+…}
= Σ[k+α[1]+2α[2]+…+kα[k]=nの0以上の整数解]x^n
= Σ[(α[1]+α[2]+…+α[k]+1)+(α[2]+…+α[k]+1)+…+(α[k]+1)=nの0以上の整数解]x^n
= Σ[β[k]+β[k-1]+…+β[1]=n、β[k]≧β[k-1]≧…≧β[1]≧1の整数解]x^n
= Σ[n=0,∞]{同一のn個を、重複を許してk個に分割する場合の数}x^n
= Σ[n=0,∞]p(n,k)x^n

今回の問題においては、第二種スターリング数S(n,k)よりも、f:{1,2,…,n}→{1,2,…,k}の全射の個数k!*S(n,k)を考えると、
Σ[n=0,∞] k!*S(n,k)x^n = k!*x^k/(1-x)(1-2x)…(1-kx)
つまり、
Σ[a[1]+a[2]+a[3]+…+a[k]=nの自然数の解]1^(a[1])*2^(a[2])*3^(a[3])*…*k^(a[k]) = k!*S(n,k)
を示せばいいことになります。

例えば、
Σ[a[1]+a[2]=4の自然数の解] 1^(a[1])*2^(a[2])
= Σ[(a[1],a[2])=(1,3),(2,2),(3,1)]1^(a[1])*2^(a[2])
= 1^1*2^3 + 1^2*2^2 + 1^3*2^1
=14,
2!S(4,2)=14

Σ[a[1]+a[2]+a[3]=5の自然数の解]1^(a[1])*2^(a[2])*3^(a[3])
= Σ[(a[1],a[2],a[3])=(1,1,3),(1,3,1),(3,1,1),(1,2,2),(2,1,2),(2,2,1)] 1^(a[1])*2^(a[2])*3^(a[3])
= 1^1*2^1*3^3 + 1^1*2^3*3^1 + 1^3*2^1*3^1 + 1^1*2^2*3^2 + 1^2*2^1*3^2 + 1^2*2^2*3^1
=150,
3!S(5,3)=150

ブロックの数が減るという考えは、具体例で確かめることはしましたが、式変形として、うまく書くことができません。
ヤング図形の共役とかと関係しているのかなあと思っていますが、なにかもっと上手に考える方法はないでしょうか。

お礼日時：2008/10/27 01:57

No.2 回答者： 20080715 回答日時： 2010/03/01 15:54

こんにちは、aiueo95240さん。

お久しぶりです。

第二種スターリング数の通常型母関数
Σ[n=0,∞] S(n,k)x^n = x^k/(1-x)(1-2x)…(1-kx)
について。

この等式がなぜ成り立つのかを、組合せ論を使ってわかりやすく
説明した本がありますので、報告をしておきます。
Analytic Combinatorics　(CAMBRIDGE)
という本です。
この本の62～63頁に説明があります。

この本の全内容が、web上で無料で閲覧できます。
↓ここを見てください。
http://algo.inria.fr/flajolet/Publications/book. …

この回答へのお礼

20080715様。いつも本当にありがとうございます。
http://algo.inria.fr/flajolet/Publications/book. …
の78、79頁を見ました。自分なりにまとめました。

1,2,3,…,nのn個の数字を、k種類の区別のないグループに分ける場合の数を、第二種スターリング数と言って、ここでは、S(n,k) と書く。n=4,k=3とすると、
{{1,2},{3},{4}}
{{1,3},{2},{4}}
{{1,4},{2},{3}}
{{1},{2,3},{4}}
{{1},{2,4},{3}}
{{1},{2},{3,4}}
なので、S(4,3)=6
これらの6通りはそれぞれ、次のようなb[1],b[2],b[3]の文字列に対応できる。
b[1],b[1],b[2],b[3]
b[1],b[2],b[1],b[3]
b[1],b[2],b[3],b[1]
b[1],b[2],b[2],b[3]
b[1],b[2],b[2],b[3]
b[1],b[2],b[3],b[3]
ただし、文字列の並べ方は次の規則に従う。
まず、b[1]を第一項に一つだけ置く。
続いて、b[1]をいくつか(0個or1個or2個or…)置く。
次の項に、b[2]を一つだけ置く。
続いて、b[1],b[2]をいくつか(0個or1個or2個or…)置く。
次の項に、b[3]を一つだけ置く。
続いて、b[1],b[2],b[3]をいくつか(0個or1個or2個or…)置く。
以上の規則で、全体が4項になるものを取り出すと、上記6種類になる。

一般に、それらの規則に従うb[1],b[2],…,b[k]の文字列を考え、それぞれを+で結ぶと、
b[1]{1+b[1]+b[1]^2+…}
b[2]{1+(b[1]+b[2])+(b[1]+b[2])^2+…}
b[3]{1+(b[1]+b[2]+b[3])+(b[1]+b[2]+b[3])^2+…}
…
b[k]{1+(b[1]+b[2]+…+b[k])+(b[1]+b[2]+…+b[k])^2+…}
で積を非可換とした展開式になる。この中で、n次になるものを取り出すと、それらの総数は、
b[1]=b[2]=…=b[k]=xとしたときのx^nの係数、つまり、
x{1+x+x^2+…}x{1+(2x)+(2x)^2+…}x{1+(3x)+(3x)^2+…}…x{1+(kx)+(kx)^2+…}
=x^k/(1-x)(1-2x)…(1-kx)
のx^nの係数に等しい。
また、それは、1,2,3,…,nのn個の数字を、k種類の区別のないグループに分ける場合の数に等しい。

機会があれば、No1のお礼や補足に書いた不定方程式の整数解との関連を考えてみたいと思います。

お礼日時：2010/03/16 05:13