# Sum over all permutations

Playing with another question, I got this equality by probabilistic considerations. I guess there is a simple proof, but I'm not strong at this...

Let $x_i >0$, $i=1,2 \cdots N$

Then

$$\frac{1}{\displaystyle \prod_{i=1}^N x_i}=\sum_{\sigma}\prod_{s=1}^N \frac{\displaystyle 1}{\displaystyle \sum_{i=1}^s x_{\sigma(i)}}$$

where the sum is over all permutations of $\{ 1,2 \cdots N\}$

(I suspect that the assumption $x_i > 0$ is not necessary)

• I suppose the all terms positive is just there to ensure one of the terms in denominator doesn't vanish! :-) – r9m Jan 22 '16 at 15:43
• Yes, the question is whether $x_i \ne 0$ is enough – leonbloy Jan 22 '16 at 15:43
• I meant try $\{1,2,-3\}$. If not all terms are of the same sign, we might have a term in RHS with $0$ in denominator. – r9m Jan 22 '16 at 15:46
• Ah, yes, you are right. I guess that that should be a removable singularity, in the limit all is right. – leonbloy Jan 22 '16 at 16:12

## 1 Answer

Group the permutations into pairs with the same $\{\sigma(1),\sigma(2)\}$, and add their contributions. From the first two factors, you get $$\frac{x_{\sigma(1)}+x_{\sigma(2)}}{x_{\sigma(1)}x_{\sigma(2)}(x_{\sigma(1)}+x_{\sigma(2)})}$$
and all the other factors are the same for that pair. So you can replace $\frac1{x_{\sigma(1)}}\frac1{x_{\sigma(1)}+x_{\sigma(2)}}$ in every permutation by $\frac1{2x_{\sigma(1)}x_{\sigma(2)}}$, and you won't change the overall sum.
Now group the permutations into sets of six with the same $\{\sigma(1),\sigma(2),\sigma(3)\}$. When you add their contributions, the first three factors simplify in the same way, so you get the same overall sum by replacing the first three factors by $\frac1{6x_{\sigma(1)}x_{\sigma(2)}x_{\sigma(3)}}$. And so on.