Let $$$a_1, a_2, \ldots, a_n$$$ be the array of $$$n$$$ positive numbers. Then
$$$ \sum_{p \in S_n} \frac{1}{a_{p_1}} \cdot \frac{1}{a_{p_1} + a_{p_2}} \cdot \frac{1}{a_{p_1} + a_{p_2} + a_{p_3}} \cdot \ldots \cdot \frac{1}{a_{p_1} + a_{p_2} + a_{p_3} + \ldots + a_{p_n}} = \frac{1}{a_{1}} \cdot \frac{1}{a_{2}} \cdot \ldots \cdot \frac{1}{a_{n}} $$$,
where the sum is taken over all permutations of size $$$n$$$.
I can prove it by induction, but it doesn't feel satisfying. Is there a combinatorial approach (maybe if $$$a_i$$$ are integers)? Or some simple transformation that would make this identity trivial? Is this well-known?
Imagine you have $$$n$$$ boxes, with the $$$i-th$$$ box having $$$a_i$$$ balls. Consider the experiment of first selecting a random permutation $$$p$$$ of the boxes. Then you perform $$$n$$$ rounds, where in the $$$n$$$-th round you take a random ball among the ones first $$$i$$$ boxes from your permutation.
The probability that in the $$$i$$$-th round you take a ball from the $$$i$$$-th box for all $$$i$$$ is exactly $$$LHS/(n!RHS)$$$, so if we prove that the probability of the experiment succeding is $$$1/n!$$$, then we are done.
In order to prove that it is $$$n!$$$, suppose that we fix any choice function that given a subset S of $$$[n]$$$ choooses one of its elements. Then, when we have to choose a ball from those S cages, we choose according to our function. If this function is fixed, then it is easy to check exactly one of the $$$n!$$$ permutation of the boxes will work. So the probability of a random permutation succeding is $$$1/n!$$$.
(i had to write this pretty fast, sorry for missing details)
This sounds super cool and exactly what I wanted by a "combinatorial" approach, but I'm not sure about the validity of the argument. The probability distribution on the choice function depends on the choice of the permutation.
Upd: While writing the comment, I thought more about it, and I suppose it doesn't really depend on the permutation? For each set the choices are independent and the probabilities to choose $$$i$$$ are proportional to $$$a_i$$$.
Yeah, I think that works! Thank you!
Consider $$$n$$$ exponential R.V. $$$X_1, \dots, X_n$$$, first of all:
$$$P(X_1 \lt X_2, X_3, \dots X_n) = \int_{0}^{\infty} a_i e^{-a_i t} \prod_{j \ne i} e^{-a_j t} \, dt = \frac{a_i}{\sum_{i=1}^n a_i}.$$$
Now notice that $$$P(X_1 \lt X_2 \lt \dots \lt X_n) = \frac{a_1}{\sum_{i=1}^n a_i} \cdot \frac{a_2}{ \sum_{i=2}^n a_i} \cdot \dots \cdot \frac{a_n}{a_n}$$$ (I guess this is quite well-known?)
The sum of this over all permutations should be 1, and you get your identity.
IMO, It is the most intuitive way to simplify. Try n = 1, 2, 3 ---> guess the formula ---> done, since the induction proof is easy.
Perhaps well-known in China. Interesting extension: https://qoj.ac/contest/1422/problem/7774
Imagine that you have a box with $$$\sum{a_i}$$$ balls colored $$$1$$$ to $$$n$$$, with exactly $$$a_i$$$ balls of color $$$i$$$. You do the following $$$n$$$ times: pick (uniformly independently) a random ball from the box, then remove all balls of the same color from the box.
For a permutation (or linear order if you are into combinatorial species) $$$p = (p_1, \ldots, p_n)$$$, the probability that the colors disappear in this order is:
Summing this over all $$$p$$$ must give $$$1$$$, qed.
Very cool, thank you!
This is kinda the same as what I do but only works for integers. (Although it is more beautiful)
A multivariate polynomial is zero at any positive integer point, then it must be zero polynomial.
You can extend this proof for non-integers by changing the statements a bit:
Assume you have $$$n$$$ ranges, $$$i$$$-th of them has length $$$a_i$$$. Arrange them on a $$$x$$$ axis sequentially, so the first one will lie on $$$[0; a_1)$$$, the second on $$$[a_1, a_1 + a_2)$$$, the third on $$$[a_1 + a_2, a_1 + a_2 + a_3)$$$ and so on. All of them will lie on $$$[0; \sum{a_i})$$$. You do the following $$$n$$$ times: uniformly independently choose a random point on $$$[0; \sum\limits_{i\ \text{ is not removed}}{a_i})$$$, remove the segment in which a point lie, move the segments right after the removed one to the left so all other segments lie again on $$$[0; \sum\limits_{i\ \text{ is not removed}}{a_i})$$$.
The proof will remain the same.
Ohh.. great way to extend this into non integral values too...
Nice
Fix a permutation and let $$$S_k=a_{p_1}+a_{p_2}+\dots+a_{p_k}$$$ for all $$$k$$$, then
$$$\prod_{i=1}^n\frac{1}{S_i}=\int_{\left(0,\infty\right)^n}\exp\left(-\sum_{i=1}^nS_ix_i\right)dx_1\dots dx_n$$$
If we let $$$y_1=x_1$$$, $$$y_2=x_1+x_2$$$, $$$\dots$$$, $$$y_n=x_1+\dots+x_n$$$ ($$$0 \lt y_1 \lt \dots \lt y_n$$$) we get $$$\sum_{i=1}^nS_ix_i=\sum_{i=1}^na_{p_i}y_i$$$. Therefore,
$$$\sum_{p\in S_n}\prod_{i=1}^n\frac{1}{a_{p_1}+\dots+a_{p_i}}=\sum_{p\in S_n}\int_{0 \lt y_1 \lt \dots \lt y_n \lt \infty}\exp\left(-\sum_{i=1}^na_{p_i}y_i\right)dy=\int_{\mathbb R_{+}^n}\exp\left(-\sum_{i=1}^na_ix_i\right)dx$$$
In the last equality, we use that $$${y_1 \lt y_2 \lt \dots \lt y_n}$$$ (for all permutations) partition $$$\mathbb R_{+}^n$$$ up to measure zero and the result follows.