I have a set of 10 elements and I want to partition it in 5 sets.
Using stirling number there are 42525 possible partitions.
The partitioning sets can have
1,1,1,1,6 elements respectively
1,1,1,2,5 elements respectively
1,1,1,3,4 elements respectively
1,1,2,2,4 elements respectively
1,1,2,3,3 elements respectively
2,2,2,2,2 elements respectively
2,2,2,3,1 elements respectively
Could you help me to find how many partitions I have for each cardinality?
I am confused because if I consider this answer here Number of ways to partition a set into subsets of given cardinality
it seems that for example for the cardinalities 1,1,1,1,6 there are $\frac{10!}{6!}=5040$ ways, but by running a code in Matlab (which I think is right) I get instead $210$ ways. What am doing wrong? I do not want to consider the order of elements and sets.
Best Answer
The two problems are quite different. Once you decide which $6$ of the $10$ elements are to be in the $6$-element subset, you’ve determined the complete partition: each of the remaining $4$ elements will go into a separate $1$-element subset. There are $\binom{10}6=210$ ways to choose the $6$-element subset, so that’s how many partitions of this type there are. If the four $1$-element subsets were labelled, it would be a different story: then there would be $4!$ different ways to distribute the remaining $4$ objects to them, and there would indeed be $210\cdot4!=5040$ different partitions. But in your setting they’re not labelled, or otherwise intrinsically distinguishable, so once you’ve determined which $4$ objects aren’t in the $6$-element set, you’re done.
In the other problem the four subsets were in effect labelled by virtue of having different required cardinalities: one is the $9$-element subset, one is the $8$-element subset, and so on. If two of the required cardinalities had been the same, as in your case, the analysis in the other problem would have been a bit different.