■集合の分割(その4)
【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
===================================