5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – mathreadler Jan 14 '16 at 22:14
  • $\begingroup$ I wonder why each index of summation starts at $1$ rather than at $0$. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jan 14 '16 at 22:16
  • $\begingroup$ Sorry I mistyped the expression, it should start at 0 and $a_i$ should be in the denominator - Sloppy me $\endgroup$ – Luke Taylor Jan 14 '16 at 22:31
  • $\begingroup$ In what context did you encounter this? $\endgroup$ – CommonerG Jan 14 '16 at 22:40
  • $\begingroup$ According to the logic how I derived the expression all the ratios should summate to an integer $\endgroup$ – Luke Taylor Jan 14 '16 at 22:45
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Sorry I mistyped the expression $\endgroup$ – Luke Taylor Jan 14 '16 at 22:32
  • $\begingroup$ This was such a nice answer though, can we keep it? $\endgroup$ – CommonerG Jan 14 '16 at 22:33
  • $\begingroup$ Of course we can! It is very informative :) $\endgroup$ – Luke Taylor Jan 14 '16 at 22:38
  • $\begingroup$ @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!) $\endgroup$ – Clive Newstead Jan 14 '16 at 23:15

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.