we know that $S(n,k)$ is the number of ways we can partition a set with $n$ members to $k$ subsets ( each subset has at least one member).
imagine we have a set with $k*n$ members. we want to partition this set to $k$ subsets such that each of them has $n$ members. how many ways can we do this ?
partitioning of a set with kn members into k subsets such that each subset has n members [duplicate]
$\begingroup$ $\endgroup$
1 
- $\begingroup$ @ArukaJ can we show that number with stirling-numbers ? $\endgroup$Arman Malekzadeh– Arman Malekzadeh2016-01-03 16:23:10 +00:00Commented Jan 3, 2016 at 16:23
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
1 This is a multinomial coefficient "in disguise" and has little to do with the Stirling numbers.
Imagine that the set elements are arranged in some sequence, and we take the subsets of size $n$ as they appear from left to right. Permutations of the $k$ blocks of size $n$ do not change the partition, nor do permutations within any of the $k$ blocks of size $n$.
It follows that the count is:
$$ \frac{(kn)!}{k! (n!)^k} $$
- $\begingroup$ It's tedious, but you can get the same result by choosing one $n$-subset after the other (counting with the binomial coefficient), for a sequence of $k$ such subsets. Thus we divide by $k!$ again to get the final expression. $\endgroup$hardmath– hardmath2016-01-03 16:39:06 +00:00Commented Jan 3, 2016 at 16:39