■源氏香図(その6)

【3】第2種スターリング数(nS3の場合)

[1]A,B,Cへの割り付け全体  3^n

[2]Aを除いてB,Cに割り付ける  2^n

[3]Bを除いてA,Cに割り付ける  2^n

[4]Cを除いてA,Bに割り付ける  2^n

[5]Aだけに割り付ける  1

[6]Bだけに割り付ける  1

[7]Cだけに割り付ける  1

  (3^n−3・2^n+3)/3!=3^n-1/2−2^n-1+1/2

 包除原理を用いると,一般項は

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

となることがわかります.

  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

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