■集合の分割(その9)

[1]n個をk個の区別のあるコンパートメントに分ける場合の数は

  nTk=Σ(−1)^k-jkCjj^n

 これはすべてのコンパートメントに少なくとも1つは属するように分けるという意味です.包除原理を使って証明することができます.原始的平行多面体のk次元面数公式にも出てきます.

[2]n個をk個の区別のないコンパートメントに分ける場合の数は

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

 これは[1]をk!で割ったものです(スターリング数)

[3]n個をk個以下の区別のないコンパートメントに分ける場合の数は

  nBk=nS1+nS2+・・・+nSk=Σ1/i!・Σ(−1)^k-jkCjj^n

 これは[2]スターリング数の和です(ベル数).

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