MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
    
Is it true for $n=2$? 3? 4? – Gerry Myerson 21 hours ago
    
Yes, for $n<7$. – T. Amdeberhan 21 hours ago
    
Are all these identities in question computer-generated? – Martin Rubey 18 hours ago
1  
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 14 hours ago

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

share|cite|improve this answer
    
Interesting approach. Please see my update. – T. Amdeberhan 21 hours ago
7  
Same proof works. – Lucia 21 hours ago

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

share|cite|improve this answer
6  
And the identity holds for $n=0$ :) – js21 18 hours ago
1  
@js21 Indeed, this is important! – Fedor Petrov 18 hours ago

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.

share|cite|improve this answer
1  
I like it, neat. – T. Amdeberhan 12 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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