# integer partitions and Faà di Bruno coefficients

I'm trying to check whether the following statement is true.

Let $n$ be a non-negative integer and $p(n)$ the number of integer partitions of $n$. Is it true that \begin{equation} p(n)=\sum_{m_1+2m_2+\dots+nm_n=n} \frac{n!}{\prod_{i=1}^n m_i! (i!)^{m_i}} \end{equation} where the notation for the sum means summing over all $\{m_i\}$ possible solutions of the equation \begin{equation} m_1+2m_2+\dots+nm_n=n, \end{equation} where all $m_i$ are non-negative integers? The fractions in the sum are Faà di Bruno coefficients.

It this is true, then I would assume a similar result applies to the extension to partitions in which the maximum element is restricted, say to $k<n$. Concretely, \begin{equation} p(n,k)=\sum_{m_1+2m_2+\dots+km_k=n} \frac{n!}{\prod_{i=1}^k m_i! (i!)^{m_i}} \end{equation}

• Something's wrong. On your right hand side is a sum over all integer partitions of $n$, and every summand is a positive integer. If it is to yield $p\left(n\right)$, then all the summands would have to be $1$. Maybe your $p\left(n\right)$ count (some kind of) set partitions rather than integer partitions? – darij grinberg Jan 1 '13 at 13:30
• So to rephrase: if the summans on the right hand side were all 1, then $p(n)$ would indeed be the number of integer partitions to $n$. It would also mean that $p(n)$ is the total number of different solutions to the equation $m_1+2m_2+\dots+nm_n=n$, right? – Ed Wolf Jan 1 '13 at 15:26

Your $p(n)$ is not the number of integer partitions of $n$. Your $p(n)$ is the number of ways to partition a set of size $n$ (as darij grinberg indicates). In other words, it's the $n$th Bell number. Your expression does not appear on the Wikipedia page for the Bell numbers, although it does appear in the main formula for the Bell polynomials. There are simpler formulas for the Bell numbers, too.

The argument below gives a combinatorial explanation that your $p(n)$ is the $n$th Bell number. The same reasoning indicates that your interpretation for $p(n,k)$ is on the right track: $p(n,k)$ is the number of ways to partition a set of size $n$ in which $k$ is the size of the maximum set allowed in the partition.

Here's the combinatorial explanation (that $p(n)$ is the $n$th Bell number). Suppose we have non-negative integers $m_1, m_2, \ldots, m_n$ such that $m_1 + 2m_2 + \cdots + nm_n = n.$ Then $$\frac{n!}{\prod_{i=1}^n m_i! (i!)^{m_i}}$$ is the number of ways to partition a set of size $n$ so that the partition contains $m_1$ sets of size $1$, $m_2$ sets of size $2$, and so forth.

Why is this? Well, we can construct such a partition by creating a permutation of the elements in the set of size $n$, in $n!$ ways, and taking the first $m_1$ elements to be singleton sets, the next $2m_2$ elements, in pairs, to be sets of size $2$, and so forth. For example, with $m_1 = 1, m_2 = 2, m_3 = 1$, and $n=8$, we could take the permutation 12345678. This gives us the partition $\{1\}, \{2, 3\}, \{4, 5\}, \{6,7,8\}$ of the set $\{1, 2, \ldots, 8 \}$.

However, this overcounts in two ways. For example, the permutation 14523678 gives us the same set partition as above because it just swaps the ordering of the two-element sets $\{2,3\}$ and $\{4,5\}$. In general, for any sets of the same size in the partition, they could be ordered in any way in the original permutation. The number of ways to order $m_i$ sets of size $i$ is $m_i!$, so to correct for this type of overcounting we have to divide by $\prod_{i=1}^m m_i!$.

The second way this overcounts is that there's no order to the elements inside the sets. Thus, for example, the permutation 13254876 yields the same partition as above. To correct for this type of overcounting we have to divide by the number of ways to order the elements of each set in our partition. There are $i!$ ways to order the elements in a set of size $i$, and we have $m_i$ sets of size $i$, so to correct for this type of overcounting we have to divide by $\prod_{i=1}^m (i!)^{m_i}$.

Summing up over all the ways to choose the $m_i$'s, we have that the number of ways to partition a set of size $n$ is $$\sum_{m_1+2m_2+\dots+nm_n=n} \frac{n!}{\prod_{i=1}^n m_i! (i!)^{m_i}},$$ which, as I said before, is better-known as the $n$th Bell number.

• Dear Mike, Thanks for your answer, and particularly the example. It is clear to me that my confusion stems from not distinguishing well enough the difference between integer and set partitions. Moreover, my confusion started by trying to see if I could count distinct Ferrer diagrams, and mistakenly imagined that for given $m1,m2,\dots,m_n$, the answer was the Faa di Bruno coefficients. Is there a way to count those in a similar combinatorial argument? Finally, in the first paragraph of combinatorial explanation, I assume you meant $m_1+2m_2+\dots nm_n=n$? Thanks again – Ed Wolf Jan 2 '13 at 9:49
• @EdWolf: Yes, I did mean $m_1 + 2m_2 + \cdots + nm_n = n$. Thanks for pointing that out; I have now corrected it. As far as counting distinct Ferrer diagrams, I am not sure how one would go about counting those. – Mike Spivey Jan 2 '13 at 22:20