# Simplify $\sum\limits_{a_1=0}^{p_1}\sum\limits_{a_2=0}^{p_2}\sum\limits_{a_3=0}^{p_3}…\sum\limits_{a_n=0}^{p_n}\frac{p!}{a_1!a_2!a_3!… a_n!}$

I am currently doodling around with some mathematics and stumbled across the following expression:

$$\sum\limits_{a_1=0}^{p_1}\sum\limits_{a_2=0}^{p_2}\sum\limits_{a_3=0}^{p_3}\cdots\sum\limits_{a_n=0}^{p_n}\frac{p!}{a_1!a_2!a_3!\cdots a_n!}$$

where $p=p_1+p_2+p_3+\cdots+p_n$ and $p_i \in \mathbb{N}$

This is a tedious expression to calculate and thus I was wondering whether it is possible to simplify it?

• the $a_i$ are not in the expression so you might as well just multiply with $p_1$, $p_2$ etc. or maybe you mistyped the expression and the $a_i$ should be in the denominator instead of the $p_i$s? – mathreadler Jan 14 '16 at 22:14
• I wonder why each index of summation starts at $1$ rather than at $0$. ${}\qquad{}$ – Michael Hardy Jan 14 '16 at 22:16
• Sorry I mistyped the expression, it should start at 0 and $a_i$ should be in the denominator - Sloppy me – Luke Taylor Jan 14 '16 at 22:31
• In what context did you encounter this? – CommonerG Jan 14 '16 at 22:40
• According to the logic how I derived the expression all the ratios should summate to an integer – Luke Taylor Jan 14 '16 at 22:45

## 1 Answer

As written, the summand doesn't depend on the variables being summed over, so it is simply equal to $$p_1p_2 \cdots p_n \cdot \dfrac{p!}{p_1!p_2! \cdots p_n!}$$ which, in turn, is equal to $$\frac{p!}{(p_1-1)!(p_2-1)! \cdots (p_n-1)!}$$ If, instead, you intended to sum over all $(p_1, p_2, \dots, p_n)$ such that $p_1+p_2+\cdots+p_n=p$, then the answer is quite simply $n^p$.

The reason for this is that $\frac{p!}{p_1!p_2!\cdots p_n!}$ is a multinomial coefficient, which counts the number of partitions of a set $A$ of size $p$ into $n$ sets $(A_1, A_2, \dots, A_n)$, where $|A_i|=p_i$ for each $1 \le i \le n$. Summing over all the possible sizes of such sets, i.e. all $(p_1, \dots, p_n)$ such that $p_1+p_2+\cdots+p_n=p$, the sum thus counts the number of partitions of a set of size $p$.

A partition of $A$ into $n$ sets is equivalent to a function $f : A \to [n]$, where $A_i = f^{-1}(\{i\})$ is the set of elements of $A$ mapped to $i$ by $f$. Thus the sum is equal to the number of functions $A \to [n]$ when $|A|=p$, which is precisely $n^p$.

• Sorry I mistyped the expression – Luke Taylor Jan 14 '16 at 22:32
• This was such a nice answer though, can we keep it? – CommonerG Jan 14 '16 at 22:33
• Of course we can! It is very informative :) – Luke Taylor Jan 14 '16 at 22:38
• @LukeTaylor: My instincts say there's not much simplification you can do with the updated expression in the question. For instance, when $n=1$ the expression becomes $$\frac{p!}{0!} + \frac{p!}{1!} + \cdots + \frac{p!}{p!}$$ Expressions like this are tricky to simplify (if they weren't, questions like this one would have less complicated solutions!) – Clive Newstead Jan 14 '16 at 23:15