6
$\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$
5
  • $\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$ Jan 14, 2016 at 22:14
  • $\begingroup$ I wonder why each index of summation starts at $1$ rather than at $0$. ${}\qquad{}$ $\endgroup$ Jan 14, 2016 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$ Jan 14, 2016 at 22:31
  • $\begingroup$ In what context did you encounter this? $\endgroup$
    – CommonerG
    Jan 14, 2016 at 22:40
  • $\begingroup$ According to the logic how I derived the expression all the ratios should summate to an integer $\endgroup$ Jan 14, 2016 at 22:45

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .