suppose that I have N distinct elements, I would like to count the number of ways that they can be arranged in subsets of cardinality m1,m2,…,mK such that m1+m2+…+mK = N.
Example: I have N=4 elements, and I want to count the number of partitions of cardinality [2,1,1], that is
{1,2}{3}{4}
{1,3}{2}{4}
{1,4}{2}{3}
{2,3}{1}{4}
{2,4}{1}{3}
{3,4}{1}{2}
=6
Is there any general formula to compute this number? I expect something in the form P(m1,m2,…,mK).
Many thanks.
Best Answer
To come to a result you need a slightly different setup. For a fixed cardinality of a subset it is important to know how many subsets in the arrangement have this cardinality. These subsets cannot be distinghuished on base of cardinality so we must be aware of the "danger" of multiple counting.
Let's say that $N=r_1.m_1+\cdots+r_k.m_k$ where $m_i$ corresponds with the cardinality of the subset and $r_i$ stands for the number of times that a subset of this cardinality occurs in the partition.
E.g. $4=2.1+1.2$ corresponds with a splitup of $\{1,2,3,4\}$ in two singletons and one set of $2$ elements.
At first hand we find: $$\frac{N!}{\left(m_1!\right)^{r_1}\times\cdots\times\left(m_k!\right)^{r_k}}$$ possibilities, but this with multiple counting that must be repaired.
The endresult is:$$\frac1{r_1!\times\cdots\times r_k!}\frac{N!}{\left(m_1!\right)^{r_1}\times\cdots\times\left(m_k!\right)^{r_k}}$$
Let's return to example $4=2.1+1.2$. The first formula give $\frac{4!}{1!1!2!}=12$ possibilities. But here the possibilities $\{1\}\{2\}\{3,4\}$ and $\{2\}\{1\}\{3,4\}$ are thought of as "distinct". The second formula divides by $2$ to repair that. There are $6$ possibilities (each of them corresponds with a selection of $2$ elements out of $4$ that are "condemned" to be elements of the same subset and there are $\binom42=6$ possible selections).