A Combinatorial Identity

Declan Stacy

Math illustration

Question

Let \(S\) be the set of \(n\)-tuples \(A = (a_1, a_2, \dots, a_n)\) such that \(a_i \geq 0\), \(\sum_{i = 1}^n a_i = k\), and \(\sum_{i = 1}^n i \cdot a_i = n\). Prove \(\sum_{A \in S} \frac{k!}{a_1!a_2! \cdots a_n!} = {n-1 \choose k-1}\).

Solution

One solution is to look at the number of ways to partition \(n\) identical objects into \(k\) ordered groups, where each group has at least one object, which is \({n-1 \choose k-1}\). (If you are not familiar with this type of “stars and bars" argument, think of a row of \(n\) objects. There are \(n-1\) empty spaces between them, and you can choose \(k-1\) of those spaces to place a separator. These separators split the \(n\) objects into \(k\) groups of objects, each with at least \(1\) object.) For each partition \(P\), let \(a_i\) be the number of groups with \(i\) objects in them for \(i = 1,2,\dots,n\). Since there are \(k\) groups, and each group must have between \(1\) and \(n\) objects, \(\sum_{i = 1}^n a_i = k\). Since the sum over all groups of the number of objects in each group is \(n\), \(\sum_{i = 1}^n i \cdot a_i = n\). Thus, \(A_P := (a_1, a_2, \dots, a_n) \in S\). Notice that two different partitions can have the same \(A\), since our definition of \(A_P\) does not reference the ordering of the groups. Any partition with \(A_P = A\) must have \(a_1\) groups with \(1\) object, \(a_2\) groups with \(2\) objects, etc. Thus, the number of partitions such that \(A_P = A\) is the number of \(k\)-tuples of \(a_1\) 1’s, \(a_2\) 2’s, ..., and \(a_n\) \(n\)’s, which is \(\frac{(\sum_{i = 1}^n a_i )! }{a_1!a_2!\cdots a_n!} = \frac{k!}{a_1!a_2! \cdots a_n!}\) (since there are \(k!\) ways to arrange the \(k\) numbers, but there are \(a_1\)! indistinguishable ways to permute the \(a_1\) 1’s, \(a_2\)! indistinguishable ways to permute the \(a_2\) 2’s, etc.). Thus, the number of ways to partition \(n\) identical objects into \(k\) ordered groups, where each group has at least one object, can also be counted by the sum over all \(A\) of the number of partitions \(P\) with \(A_P = A\), which is \(\sum_{A \in S} \frac{k!}{a_1!a_2! \cdots a_n!}\), which concludes the proof.