■包除原理(その5)
[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]スターリング数の和です(ベル数).
===================================