2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.$$

$\endgroup$
  • $\begingroup$ This is exactly what I was looking for. I couldn't figure it out because when the $n_i$ are repeating, I have to correct that. Thanks! $\endgroup$ – Theodor Oct 21 '15 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.