第１８話　「第２種スターリング数Ｓ（ｎ，ｋ）」ＮＯ１

まとめていきます。

皆さんは、ｎの階乗はｎ！＝ｎ(ｎ−１)(ｎ−２)・・・３×２×１ということをご存じです。

では、ｘの階乗関数はｘ^[k]＝ｘ(ｘ−１)(ｘ−２)・・・(ｘ−ｋ＋１)と表される関数をいいます。

例えば、ｘ^［１］＝ｘ，ｘ^［２]＝ｘ(ｘ−１)，ｘ^［３]＝ｘ(ｘ−１)(ｘ−２)，ｘ^［４]＝ｘ(ｘ−１)(ｘ−２) (ｘ−３)です。

ここで、問題です。ｘ＾２＝S(2,1)ｘ^［１］＋S(2,2)ｘ^［２] となる係数S(2,1)、S(2,2)を求めてください。

さらに、ｘ＾３＝S(3,1)ｘ^［１］＋S(3,2)ｘ^［２]＋S(3,3)ｘ^［３]となる係数S(3,1)、S(3,2)、S(3,3)を求めてください。

　勿論、皆さんは恒等式の性質で、未定係数法を使って、S(2,1)＝１，S(2,2)＝１，S(3,1)＝１，S(3,2)＝３、S(3,3)＝１

と出します。ここで、他の求め方もあります。それが、連続組立除法という方法です。この方法は、整式Ａを１次の整式Ｂで割った商をＰ、あまりをＱとしたときに、一度に求めてくれる方法です。よく、因数分解するとき、１次因数を発見するのに使います。

　詳しく、下の図を見て下さい。ご覧のように、次々と、「第２種スターリング数」が生まれてきます。

したがって、一般に、ｘ＾ｎ＝S(ｎ,1)ｘ^［１］＋S(ｎ,2)ｘ^［２]＋S(ｎ,3)ｘ^［３]＋・・・＋S(ｎ,ｎ)ｘ^［ｎ]

となる係数S(ｎ,1)、S(ｎ,2)、S(ｎ,3)、・・・、S(ｎ,ｎ)はこの連続組立除法で続けていけば、簡単に求められます。

「ｎ冊の異なる本を、ｋ個の同じ棚に入れる方法は何通りあるでしょうか。ただし、空の本棚があってはいけないとし、ｎ≧ｋとする。」この入れ方をS(ｎ,ｋ)とします。

例えば、分かり易くするために、ｎ＝４、ｋ＝３として考えてみます。本をａ，ｂ，ｃ，ｄとして、縛って本棚に入れることにします。実際には、［｛ａ，ｂ｝，｛ｃ｝，｛ｄ｝］，［｛ａ｝，｛ｂ，ｃ｝，｛ｄ｝］，［｛ａ｝，｛ｂ｝，｛ｃ，ｄ｝］，［｛ａ，ｃ｝，｛ｂ｝，｛ｄ｝］，［｛ａ，ｄ｝，｛ｂ｝，｛ｃ｝］，［｛ｂ，ｄ｝，｛ａ｝，｛ｃ｝］の６通りあります。S(４,３)＝６

　これらの入れ方を、ｄが単独で棚に入っている入れ方とそうでない入れ方に分類してみます。

『１』ｄが単独で棚に入っているのは［｛ａ，ｂ｝，｛ｃ｝，｛ｄ｝］，［｛ａ｝，｛ｂ，ｃ｝，｛ｄ｝］，［［｛ａ，ｃ｝，｛ｂ｝，｛ｄ｝］である。ｄの棚を除くと、［｛ａ，ｂ｝，｛ｃ｝］，［｛ａ｝，｛ｂ，ｃ｝］，［［｛ａ，ｃ｝，｛ｂ｝］となる、

これは異なる３冊の本ａ，ｂ，ｃを２個の同じ本棚に空の棚がないような入れ方になっている。すなわち、S(３,２)＝３

『２』ｄが単独で棚に入っていないのは［｛ａ｝，｛ｂ｝，｛ｃ，ｄ｝］、［｛ａ，ｄ｝，｛ｂ｝，｛ｃ｝］，［｛ｂ，ｄ｝，｛ａ｝，｛ｃ｝］である。これらの入れ方は棚をそのままにしてｄのみを除くと、いずれも本ａ，ｂ，ｃとなる。

これは異なる３冊の本ａ，ｂ，ｃを３個の同じ本棚に空の棚がないような入れ方になっている。すなわち、S(３,３)＝１になっている。この逆操作をすることは、３個の棚のそれぞれにｄを戻すことに相当するので、３Ｓ(３,３)だけの入れ方があったことになる。

　これらをまとめると、S(４,３)＝S(３,２)＋３Ｓ(３,３)　が成り立つことがわかる。ここで、次の定理が発見できる。

　　＜証明＞異なる（ｎ＋１）冊の本を棚に入れるときに、最初のｎ冊と最後の１冊に分けて考える。すると、最後の１冊が単独で棚にいれる場合とそうでない場合に場合分けができる。

『１』最後の１冊が単独で棚に入る場合は、最初のｎ冊は（ｋ―１）個の棚に空き棚を作らないように入っているので、入れ方はS(ｎ,ｋ―１)通りである。

『２』最後の１冊が単独で棚に入らない場合は、最初のｎ冊だけでｋ個の棚に空き棚を作らないように入っているはずです。このような場合はS(ｎ,ｋ)通りあるが、最後の１冊をどの棚に入れるかがｋ通りに選べるので、これらの積ｋS(ｎ,ｋ)が入れ方の数になる。

　これら２つの場合の数の和S(ｎ,ｋ―１)＋ｋS(ｎ,ｋ)が、異なる（ｎ＋１）冊の本をｋ個の棚に空き棚を作らないように入れる入れ方の数S(ｎ＋１,ｋ)に等しくなる。

　次は、当然明らかなことです。　＜証明終わり＞　　

ここで、「第２種スターリング数」S(ｎ,ｋ)を表にします。ただし、１≦ｋ≦ｎ

「ｎ冊の異なる本を、ｋ個の異なる棚に空の本棚を作らないように入れる方法は何通りあるでしょうか。」

この答がｋ！S(ｎ,ｋ)だったのです。導いてみましょう。

＜証明＞　異なるｎ冊の本を異なるｋ個の棚に空の棚を作らないように入れる１つの入れ方に対して、そのときの棚同士をｋ！通りに交換したものすべてが異なるｎ冊の本を同じｋ個の棚に空の棚を作らないように入れる１つの入れ方に対応するので、異なるｎ冊の本を異なるｋ個の棚に空の棚を作らないように入れる入れ方の数はｋ！S(ｎ,ｋ)となる。＜証明終わり＞

「異なるｎ冊の本を、ｋ個の同じ棚に入れる方法は何通りあるでしょうか。ただし、空の本棚があってもよい、ｎ≧ｋとする。」

この答は、S(ｎ,１)＋S(ｎ,２)＋S(ｎ,３)＋・・・＋S(ｎ,ｋ)　になります。

＜証明＞　異なるｎ冊の本を同じｋ個の棚に空の棚なしに入れる方法がS(ｎ,ｋ)通りである。

異なるｎ冊の本を同じｋ個の棚に空の棚が１個の状態で入れる方法が、すなわち、異なるｎ冊の本を同じ（ｋ―１）個の棚に空の棚なしの状態で入れる方法のことで、S(ｎ,ｋ―１)通りある。

　同様に考えて、異なるｎ冊の本を同じｋ個の棚に空きの棚が２個の状態で入れる方法がS(ｎ,ｋ―２)通り、・・・、異なるｎ冊の本を同じｋ個の棚に空きの棚が（ｋ−１）個の状態で入れる方法がS(ｎ,１)通りある。

　したがって、これらの総和、S(ｎ,１)＋S(ｎ,２)＋S(ｎ,３)＋・・・＋S(ｎ,ｋ)が求める入れ方になります。

ただ、ｎ＜ｋの場合について、述べておくと、本の数より棚の数の方が多いので、

S(ｎ,ｎ＋１)＝S(ｎ,ｎ＋２)＝・・・＝S(ｎ,ｋ―１)＝S(ｎ,ｋ)＝０と考えて差し支えない。

　ここで、次のようなことが分かる

＜証明＞（３）S(ｎ,２)は、異なるｎ冊の本を同じ２個の棚に空の棚を作らないように入れる入れ方です。

最初の１冊をどちらの棚に入れても、棚自体に区別がないので選択の余地がなく、したがって１通りの選び方しかできない。しかし、最初の１冊を入れることにより、２個の棚には区別ができる。

　異なる２個の棚に残りの（ｎ―１）冊の本を入れる入れ方は、１冊ごとに２通りあるので、全部で２＾(n-1)通りある。しかし、この中には最初の１冊を入れた方の棚に残りの（ｎ―１）冊をすべてを入れる場合を含んでいる。これは空の棚を作らないという規定に反するので、この１通りを除外すると、２＾(n-1)−１　となる。

（４）S(ｎ,ｎ−１)は異なるｎ冊の本を同じ（ｎ―１）個の棚に空の棚を作らないように入れる入れ方です。

空の棚を作らないためには、（ｎ―１）個の棚の内の１個の棚にだけ２冊の本を入れ、それ以外の棚には１冊の本を入れなければならない。棚どうしには区別がないので、異なるｎ冊の本から１つの棚に入れる２冊の本を選ぶ選択しかないことになる。これは、異なるｎ冊の本から２冊を選ぶことになるので、Ｃ（ｎ，２）とおりある。

（５）異なる（ｎ＋１）冊の本ａ_１，ａ_２，ａ_３，・・・、ａ_ｎ，ａ_ｎ＋１を同じｋ個の棚に空の棚を作らないように入れる方法はＳ（ｎ＋１，ｋ）通りある。

　このような入れ方の１つを実際に作成し、その上でａ_ｎ＋１の入っている棚とその中にあるすべての本を取り除くと、その残りは、｛ａ_１，ａ_２，ａ_３，・・・、ａ_ｎ｝の部分集合Ｊを同じ（ｋ−１）個の棚に空の棚を作らないように入れる入れ方になる。Ｊの要素の数がｊの時、そのような入れ方はＳ（ｊ，ｋ−１）通りある。

　ただし、取り除いた棚に入っていた本の数は１から（ｎ＋１）の間の数になるので、Ｊの要素の数は０からｎまでの値をとる可能性がある。

　また、集合Ｊの要素の数がｊのとき、｛ａ_１，ａ_２，ａ_３，・・・、ａ_ｎ｝からＪを選ぶ選び方はＣ（ｎ，ｊ）通りある。

よって、�煤iｊ＝０・・・ｎ）Ｃ（ｎ，ｊ）・Ｓ（ｊ，ｋ−１）がＳ（ｎ＋１，ｋ）と等しくなる。

第２種スターリング数の和として次の定義式で表されるＢ（ｎ）をベル指数と言います。

　Ｂ（ｎ）＝S(ｎ,１)＋S(ｎ,２)＋S(ｎ,３)＋・・・＋S(ｎ,ｎ) 　（ｎ≧１）、　　Ｂ（０）＝１

ベル指数Ｂ（ｎ）は、その定義から異なるｎ冊の本を（同じいくつかの棚に）空の棚なく入れる入れ方の総数を表す。

ｋ＞ｎ＋１のとき、Ｓ（ｎ＋１，ｋ）＝０を使います。

Ｂ（ｎ＋１）＝�煤iｋ＝１・・・ｎ＋１）Ｂ（ｎ＋１，ｋ）＝�煤iｋ＝１・・・∞）Ｂ（ｎ＋１，ｋ）

さらに、定理（５）を用いると、次の関係式が得られる。

Ｂ（ｎ＋１）＝�煤iｋ＝１・・・∞）�煤iｊ＝０・・・ｎ）Ｃ（ｎ，ｊ）・Ｂ（ｊ，ｋ−１）　

　　　　　　＝�煤iｊ＝０・・・ｎ）｛Ｃ（ｎ，ｊ）�煤iｋ＝１・・・∞）Ｂ（ｊ，ｋ−１）｝

　　　　　　＝Ｃ（０，０）｛S(０,０)＋S(０,１)＋・・・｝

　　　　　　　　＋�煤iｊ＝１・・・ｎ）｛Ｃ（ｎ，ｊ）�煤iｋ＝１・・・∞）Ｂ（ｊ，ｋ−１）｝

　　　　　　＝１（０＋０＋・・・）＋�煤iｊ＝１・・・ｎ）｛Ｃ（ｎ，ｊ）�煤iｋ＝２・・・ｊ＋１）Ｂ（ｊ、ｋ−１）｝

　　　　　　＝１＋�煤iｊ＝１・・・ｎ）｛Ｃ（ｎ，ｊ）�煤iｋ＝１・・・ｊ）Ｂ（ｊ、ｋ）｝

　　　　　　＝Ｃ（０，０）Ｂ（０）＋�煤iｊ＝１・・・ｎ）｛Ｃ（ｎ，ｊ）・Ｂ（ｊ）｝

　　　　　　＝�煤iｊ＝０・・・ｎ）Ｃ（ｎ，ｊ）・Ｂ（ｊ）　　　　＜証明終わり＞

＊ちなみに、ベル指数Ｂ（ｎ）はこの漸化式に従って、計算すると、１，１，２，５，１５，５２，２０３，８０７，・・・

　次回は、第２種スターリング数S(ｎ,ｋ) の一般項を出す予定です。

＜参考文献：「やさしい組み合わせ数学：西岡弘明著（コロナ社）＞

「ｎ冊の異なる本を、ｋ個の異なる棚に空の本棚を作らないように入れる方法は何通りあるでしょうか。」

この答がｋ！S(ｎ,ｋ)です。ここで、ｋ！S(ｎ,ｋ)＝Ｆ(ｎ,ｋ)とおきます。

「ｎ冊の異なる本を、ｋ個の異なる棚に空の本棚を作ってもよい入れる方法は何通りあるでしょうか。」

この答が重複順列で、ｋ^ｎ通りある。

　そこで、ｋ^ｎをＦ(ｎ,ｒ)　（ｒ＝０，１，２，・・・ｋ）で表わすことを考えます。

異なるｋ個の棚に空の棚がない場合、異なるｋ個の棚に空の棚が１個の場合、異なるｋ個の棚に空の棚が２個の場合、・・・、

異なるｋ個の棚に空の棚がｋ個の場合、これは便宜的に考えておきます。よって、次の式が成り立ちます。

ｋ^ｎ＝Ｆ(ｎ,ｋ)＋Ｃ(k,1)・Ｆ(ｎ,k−１)＋Ｃ(k,2)・Ｆ(ｎ,k−2)＋・・・＋Ｃ(k,r)・Ｆ(ｎ,k−r) ＋・・・＋Ｆ(ｎ,0)

Ａ(０)＝Ｆ(ｎ,0)，Ａ(１)＝Ｆ(ｎ,1) ＋Ｆ(ｎ,0)，Ａ(２)＝Ｆ(ｎ,2) ＋Ｃ（2，1）Ｆ(ｎ,1) ＋Ｆ(ｎ,0)、

Ａ(３)＝Ｆ(ｎ,3) ＋Ｃ（3，1）Ｆ(ｎ,2) ＋Ｃ（3，2）Ｆ(ｎ,1)＋Ｆ(ｎ,0)、・・・・

これを、逆に、Ｆ(ｎ,ｋ)について、解いていきます。

Ｆ(ｎ,0)＝Ａ(０)＝０^ｎ＝０　として、Ｆ(ｎ,1)＝Ａ(1)−Ｆ(ｎ,0)＝１^ｎ−０＝１，

Ｆ(ｎ,２) ＝Ａ(２)−｛Ｃ（2，1）Ｆ(ｎ,1) ＋Ｆ(ｎ,0)｝＝Ａ(２)−Ｃ（2，1）｛Ａ(1)−Ｆ(ｎ,0)｝ −Ａ(０)

　　　　　＝Ａ(２)−Ｃ（2，1）Ａ(1) −Ａ(０)

・・・・

Ｆ(ｎ,ｋ)＝Ａ(ｋ)―Ｃ（k，1）Ａ(k―1) ＋ Ｃ（k，2）Ａ(k―2) −Ｃ（k，3）Ａ(k―3) ＋・・・＋

　　　　（−１）^ｒＣ（k，r）Ａ(ｋ−ｒ) ＋・・・＋（−１）^ｋ Ａ(０)

　　　　＝�煤iｒ＝０・・・ｋ）（−１）^ｒＣ（k，r）Ａ(ｋ−ｒ)

　　　　＝�煤iｒ＝０・・・ｋ）（−１）^ｒＣ（k，r）（ｋ−ｒ）^ｎ

したがって、ｋ！S(ｎ,ｋ)＝Ｆ(ｎ,ｋ)　にもどしてみると、

S(ｎ,ｋ)＝Ｆ(ｎ,ｋ)／ｋ！＝�煤iｒ＝０・・・ｋ）（−１）^ｒＣ（k，r）（ｋ−ｒ）^ｎ／ｋ！　　・・・（答）

これが、太郎さんが探し求めていた「第２種スターリング数」の一般項でした。

　次回は、この値を、積率母関数（指数型母関数）から求めてみます。