■集合の分割(その3)

【2】第2種スターリング数

 シェフェ数はn個の数字を3つのグループA,B,Cに分ける方法の総数で,ただし,A,Bは少なくとも1つの数字を含むものとしたものですが,ここでは,n個の数字を3つのグループA,B,Cに分ける方法の総数で,ただし,各グループA,B,Cは少なくとも1つの数字を含むものとします.

 もっと一般に,1≦k≦nとし,n個の数字をk個のグループに分ける方法の総数で,ただし,各グループは少なくとも1つの数字を含むものの数をnSkとします.

 nSkは第2種スターリング数と呼ばれるもので,漸化式

  n+1Sk=nSk-1+knSk

が成り立ちます.

 nS1=1を出発点として

  nS2=2^n-1−1

  nS3=3^n-1/2−2^n-1+1/2

  nS4=4^n-1/6−3^n-1/2+2^n-2−1/6

一般項は

  nSk=1/k!Σ(−1)^k-jkCjj^n

となります.

===================================