# Sum over permutations is 1

This might be easy, but let's see.

Question 1. If $\mathfrak{S}_n$ is the group of permutations on $[n]$, then is the following true? $$\sum_{\pi\in\mathfrak{S}_n}\prod_{j=1}^n\frac{j}{\pi(1)+\pi(2)+\cdots+\pi(j)}=1.$$

Question 2. Let $z_1,\dots,z_n$ be indeterminates. Is this identity true too? $$\sum_{\pi\in\mathfrak{S}_n}\prod_{j=1}^n\frac{z_j}{z_{\pi(1)}+z_{\pi(2)}+\cdots+z_{\pi(j)}}=1.$$

Update. Now that we've an analytic and an algebraic proof, is there a combinatorial argument too? At least for Question 1.

• Is it true for $n=2$? 3? 4? – Gerry Myerson Feb 16 '17 at 5:21
• Yes, for $n<7$. – T. Amdeberhan Feb 16 '17 at 5:27
• Are all these identities in question computer-generated? – Martin Rubey Feb 16 '17 at 8:54
• Computer-tested. In the present case, you can't go far with your data because $\mathfrak{S}_n$ grows very quickly. So, you also need a "leap of faith". – T. Amdeberhan Feb 16 '17 at 12:46

Yes. Write the sum as $$\sum_{\pi \in S_n} n! \int_0^{\infty} e^{-\pi(1) x_1} \int_{0}^{\infty} e^{-(\pi(1)+\pi(2)) x_2} \ldots \int_0^{\infty} e^{-(\pi(1) + \ldots +\pi(n))x_n} dx_n \ldots dx_1.$$ Upon writing $y_n = x_n$, $y_{n-1}=x_n+x_{n-1}$, etc this becomes $$\sum_{\pi \in {S_n} } n! \int_{y_1 \ge y_2 \ge \ldots y_n \ge 0} e^{-\sum_{i=1}^{n} \pi(i)y_i } dy_1 \ldots dy_n.$$ Since the sum is over all $\pi \in S_n$, it doesn't matter that we are in the region $y_1 \ge y_2 \ge \ldots \ge y_n$ -- for any other ordering of the non-negative variables $y_i$, the answer would be the same. So recast the above as $$\int_0^{\infty} \ldots \int_0^{\infty} \sum_{\pi \in S_n} e^{-\sum_{i=1}^{n} \pi(i) y_i} dy_1 \ldots dy_n = \sum_{\pi \in S_n} \frac{1}{n!} = 1.$$

• Interesting approach. Please see my update. – T. Amdeberhan Feb 16 '17 at 5:49
• Same proof works. – Lucia Feb 16 '17 at 5:52

Here is a probabilistic, or, if you wish, combinatorial proof. Assume that we have $n$ baskets containing $z_1,\dots,z_n$ balls respectively (well, let them be positive integers). Choose a random ball (all balls have equal probability) and forbid all the balls from its basket. Repeat with $n-1$ remaining baskets and so on. What is the probability that we consecutively get balls from baskets $\pi_n,\pi_{n-1},\dots,\pi_1$? Yes, it equals $$\prod_{j=1}^n\frac{z_{\pi_j}}{z_{\pi(1)}+z_{\pi(2)}+\cdots+z_{\pi(j)}}$$ (we start multiplying from $j=n$ downto $j=1$). The sum of all these probabilities equals 1.

• I like it, neat. – T. Amdeberhan Feb 16 '17 at 14:56

Purely algebraic proof. We induct on $n$. Fix $\pi_n$. This part of the sum equals $z_{\pi_n}/(z_1+\dots+z_n)$ by induction proposition. Now sum up by all values of $\pi_n$.

• And the identity holds for $n=0$ :) – js21 Feb 16 '17 at 8:39
• @js21 Indeed, this is important! – Fedor Petrov Feb 16 '17 at 8:41