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

Update. After Lucia's answer, I got motivated to ask:

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.

  • $\begingroup$ Is it true for $n=2$? 3? 4? $\endgroup$ Commented Feb 16, 2017 at 5:21
  • $\begingroup$ Yes, for $n<7$. $\endgroup$ Commented Feb 16, 2017 at 5:27
  • 1
    $\begingroup$ Are all these identities in question computer-generated? $\endgroup$ Commented Feb 16, 2017 at 8:54
  • 1
    $\begingroup$ 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". $\endgroup$ Commented Feb 16, 2017 at 12:46

3 Answers 3


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

  • $\begingroup$ Interesting approach. Please see my update. $\endgroup$ Commented Feb 16, 2017 at 5:49
  • 11
    $\begingroup$ Same proof works. $\endgroup$
    – Lucia
    Commented Feb 16, 2017 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.

  • 1
    $\begingroup$ I like it, neat. $\endgroup$ Commented Feb 16, 2017 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$.

  • 6
    $\begingroup$ And the identity holds for $n=0$ :) $\endgroup$
    – js21
    Commented Feb 16, 2017 at 8:39
  • 1
    $\begingroup$ @js21 Indeed, this is important! $\endgroup$ Commented Feb 16, 2017 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.