I stumbled upon the following question: given a set of size $k$, how many partitions of sizes $(n_1, ..., n_m)$ exist, for $n_1 + ... + n_m = k$. I am not sure I can explain it exactly like this, so I'll just show an example:
A set of size 4 $(abcd)$ can be partitioned into
- $(abcd)$, i.e. $n_1 = 4$, and number of partitions is 1
- $(abc)(d), (abd)(c), (acd)(b), (a)(bcd)$, i.e. $n_1 = 3, n_2 = 1$ and number of partitions is 4
- $(ab)(cd), (ac)(bd), (ad)(bc)$, i.e. $n_1 = 2, n_2 = 2$ and number of partitions is 3
- $(ab)(c)(d), (ac)(b)(d), (ad)(b)(c), (bc)(a)(d), (bd)(a)(c), (cd)(a)(b)$, i.e. $n_1 = 2, n_2 = 1, n_3 = 1$ and 6 number of partitions is 6
- $(a)(b)(c)(d)$, i.e. $n_1 = 1, n_2 = 1, n_3 = 1, n_4 = 1$ and number of partitions is 1
Can I find out the number of partitions given the $n_i$s?
You can do this using binomial coefficients: if the $n_i$ are distinct then the answer will be $${k \choose n_1}{k-n_1 \choose n_2}{k-n_1-n_2 \choose n_3}\cdots \\ = {k! \over n_1!(k-n_1)!}{(k-n_1)! \over n_2!(k-n_1-n_2)!}{(k-n_1-n_2)! \over n_3!(k-n_1-n_2-n_3)!} \cdots \\ = {k! \over n_1!n_2!\cdots n_m!}$$
This is known as a multinomial coefficient. For example, when $n_1=3, n_2=1$, we have ${4! \over 3!1!} = 4$.
Now, if the $n_i$ are not distinct, the above formula will count too high, because it considers $(ab)(cd)$ to be distinct from $(cd)(ab)$. Of the $n_i$, if there are $r$ that are identical, you need to compensate by dividing by $r!$. For instance, when $n_1=2, n_2=2$, we have $${{4! \over 2!2!} \over 2!} = {6 \over 2} = 3.$$
As another example, suppose $k = 11$ and that $n_1=3, n_2=3, n_3=2, n_4=2, n_5=1$. Then the number of partitions is $${{11! \over 3!3!2!2!1!} \over 2!2!} = 69300.$$