Ｕ嬢からの問題「１月１日から１２月３１日までの誕生日がすべてそろうためには，最低何人の集団が必要か？」

　その確率が５０％を超えるには何人かという問題だろう．　答えは帰路，車の運転中にわかった．それは第２種スターリング数と関係している．車の運転中に答えがでることは私にはよくあることだが，やはり職場では気が散るということなのだろう．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　ｎ人をｋチームに分ける場合の数はｋ^n通り．このうち，チームにだれも属さない場合の数を除けばよい．

　それは包除原理より，

　　kＣ1（ｋ−１）^n−kＣ2（ｋ−２）^n＋・・・＋（−１）^k-2kＣk-1１^n

これを後ろから足し合わせると

　　Σ(1,k-1)（−１）^k-j-1kＣk^jｊ^n＝Σ(1,k-1)（−１）^k-j-1kＣk^jｊ^n

　ｋ^nからこれを引くと

　　ｋ^n−Σ(1,k-1)（−１）^k-j-1kＣk^jｊ^n＝Σ(1,k)（−１）^k-jkＣjｊ^n

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　ｎ個をｋ個の区別のあるコンパートメントに分ける場合の数は

　　nＴk＝Σ（−１）^k-jkＣjｊ^n

　これはすべてのコンパートメントに少なくとも１つは属するように分けるという意味です．nＳkは第２種スターリング数と呼ばれるもので，漸化式

　　n+1Ｓk＝nＳk-1＋ｋnＳk

が成り立ちます．

　　nＴk＝ｋ！・nＳk

ですから

　　ｋ！・n+1Ｓk＝n+1Ｔk

　　ｋ！・nＳk-1＝ｋnＴk-1

　　ｋ！・nＳk＝nＴk

　　n+1Ｔk＝ｋnＴk-1＋ｋnＴk

　nＴ1＝１を出発点として

　　nＴ2＝２^n−２

　　nＴ3＝３^n−３・２^n＋３

　　nＴ4＝４^n−４・３^n＋６・２^n−４

　　nＴ5＝（５^n−５・４^n＋１０・３^n−１０・２^n＋５）

　　nＴ6＝（６^n−６・５^n＋１５・４^n−２０・３^n＋１５・２^n−６）

　　nＴn＝Σ（−１）^n-jnＣjｊ^n＝｛ｎ！−・・３^nnＣ2・・２^nnＣ2・・nＣ1｝

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝