第二種スターリング数

第二種スターリング数は組み合わせ数学に登場する.

次のような問題にスターリング数は登場する.n個のものを空でないk個のまとまりにまとめるときの場合の数を{}_n S_{k}とかく.

具体的な問題を考える.

5人を空でない3つのグループに分ける方法の数を求めよ.

…中学受験とかにありそうな問題だなオイ.

これは次のように解くのだった.まず5人が全員区別できるものとする.名前をA,B,C,D,Eという.

つぎに3つのグループも区別できるものとして名前をa,b,cという.

Aにどこのグループに入るかを聞く.a,b,cの3通り.Bに,Cに,と繰り返して,3^5通り.

空のグループは許されないので,全員がaを選ばなかった(全員がb,cを選んだ)のは2^5通り.

bやcも選ばなかったなら,これらは3\times 2^5通り.

最後に全員がaを選んだ場合は1通り.b,cを選んだ場合も含めて,3通り.

だから,3^5-3\times 2^5+3通り.グループに区別はないから,

\dfrac{3^5-3\times 2^5+3}{3!}=25

では,スターリング数を用いて解く.{}_5 S_{3}.できたー!

スターリング数には次の漸化式が知られている.

{}_n S_k={}_{n-1} S_{k-1}+k {}_{n-1}S_{k}

だから,

{}_5 S_{3}={}_4 S_{2}+3 {}_4 S_{3}={}_3 S_{1}+2 {}_3 S_{2}+3 ({}_3 S_{2}+3{}_3 S_{3}) \\    ={}_3 S_{1}+2 ({}_2 S_{1}+2{}_2 S_{2})+3 (({}_2 S_{1}+2{}_2 S_{2})+3{}_3 S_{3}) \\    =1+2(1+2)+3((1+2)+3)=25

ここで,n個のものを1グループに分けるのは1通りであることと,n個のものをnグループで分けるのも1通りであることを用いた.

もっとすごいのは次の公式である.

{}_n S_k = \Bigl[e^{1-kx-e^x} \dfrac{d^n}{dx^n}e^{e^x-1} \Bigr]の定数項

実際に使ってみよう.n=5, k=3より

e^{1-3x-e^x} \dfrac{d^5}{dx^5}e^{e^x-1}=e^{-2 x}+15 e^{-x}+10 e^x+e^{2 x}+25

ま,実用的じゃないよな.うん.

中学受験では答えしか要求されないことをいいことに

{}_n S_k={}_{n-1} S_{k-1}+k {}_{n-1}S_{k} を小学生に教えてみたい.

俺「第二種スターリング数覚えろよ,いろいろ捗るぞwww」

—-追記—-

第2種スターリング数 {n, k}
n\k 1 2 3 4 5 6 7 8 9 10
1 1 0 0 0 0 0 0 0 0 0
2 1 1 0 0 0 0 0 0 0 0
3 1 3 1 0 0 0 0 0 0 0
4 1 7 6 1 0 0 0 0 0 0
5 1 15 25 10 1 0 0 0 0 0
6 1 31 90 65 15 1 0 0 0 0
7 1 63 301 350 140 21 1 0 0 0
8 1 127 966 1701 1050 266 28 1 0 0
9 1 255 3025 7770 6951 2646 462 36 1 0
10 1 511 9330 34105 42525 22827 5880 750 45 1

漸化式はこの表では,次のような規則になる.

「{n,k}を求めるには, 真上の数にkをかけて,左上の数と加える.」

縦と対角線にははじめから1を書いておけば上の規則で次々と書き加えることができるし,見通しも良い.覚えやすい.

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中