組分け問題:異なるn個のものを異なるk組に分ける場合の数(0個の組なし)

 いいURLを見つけました。
組分けする場合の数
 もう少し分かりやすく、まとめなおしてみます。
 異なるn個のものを異なるk組に分ける方法の数(0個の組なし、定員不定)M(k,n)は、
M(k,n)=k^n-(kCk-1)M(k-1,n)-…-(kC3)M(3,n)-(kC2)M(2,n)-(kC1)M(1,n)
M(1,n)=1
 これから、k=2,3,4と次々に求めていくと
M(2,n)=2^n-(2C1)M(1,n)=2^n-2*1=2^n-2
M(3,n)=3^n-(3C2)M(2,n)-(3C1)M(1,n)=3^n-3(2^n-2)-3*1=3^n-3*2^n+3
M(4,n)=4^n-(4C3)M(3,n)-(4C2)M(2,n)-(4C1)M(1,n)
=4^n-4(3^n-3*2^n+3)-6(2^n-2)-4*1
=4^n-4*3^n+6*2^n-4
∴M(4,6)=4^6-4*3^6+6*2^6-4=1560
 ちなみに、一般式はこうなりそうです。o(^-^)o
 M(k,n)=Σ[j=0,k-1](-1)^j (kCk-j)(k-j)^n)=Σ[j=0,k](-1)^j (kCj)(k-j)^n
 はてな記法を使うと次の通りです。形が綺麗なのでどこかの公式集を探せばありそうですね。(^_^;
M(k,n) = \sum_{j=0}^{k-1}(-1)^{j}(_{k}C_{k-j})(k-j)^{n} = \sum_{j=0}^{k}(-1)^{j}(_{k}C_{j})(k-j)^{n}
M(1,n)=(_{1}C_{1})1^{n}
M(2,n)=(_{2}C_{2})2^{n}-(_{2}C_{1})1^{n}
M(3,n)=(_{3}C_{3})3^{n}-(_{3}C_{2})2^{n}+(_{3}C_{1})1^{n}
M(4,n)=(_{4}C_{4})4^{n}-(_{4}C_{3})3^{n}+(_{4}C_{2})2^{n}-(_{4}C_{1})1^{n}
M(5,n)=(_{5}C_{5})5^{n}-(_{5}C_{4})4^{n}+(_{5}C_{3})3^{n}-(_{5}C_{2})2^{n}+(_{5}C_{1})1^{n}

 やっぱり、公式集にあるようですね。第2種スターリング数に関連があるようです。(^_^;

※参考URL
http://q.hatena.ne.jp/1305635262
https://manabitimes.jp/math/841
http://zakii.la.coocan.jp/enumeration/11_stirling_partition.htm
https://q.hatena.ne.jp/1639295402
組み分け全パターン
スターリング数 - Wikipedia
第二種スターリング数の問題 [PDF] ←(4)式参照

\left{n\\r\right}=\frac{1}{r!}\sum_{j=0}^{r}\left(r\\j\right)\left(-1\right)^{j}\left(r-j\right)^{n}

 r!で割っているということは、第2種スターリング数の場合、組に区別がないということかな!?

●『離散数学「数え上げ理論」』 野崎昭弘著