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