28
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is it true for $n=2$? 3? 4? $\endgroup$ – Gerry Myerson Feb 16 '17 at 5:21
  • $\begingroup$ Yes, for $n<7$. $\endgroup$ – T. Amdeberhan Feb 16 '17 at 5:27
  • 1
    $\begingroup$ Are all these identities in question computer-generated? $\endgroup$ – Martin Rubey Feb 16 '17 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$ – T. Amdeberhan Feb 16 '17 at 12:46
36
$\begingroup$

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

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

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.

$\endgroup$
  • 1
    $\begingroup$ I like it, neat. $\endgroup$ – T. Amdeberhan Feb 16 '17 at 14:56
22
$\begingroup$

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

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

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.