I'm looking for an elementary combinatorial/generating function/etc proof of the following result:
For nonnegative integers $r$,
$$\frac{1}{r!} = \sum_{p_0+p_1+\cdots = r} \frac{1}{(p_0!)^2(p_1!)^2\cdots{p_0+p_1+1\choose 1}{p_1+p_2+2\choose 2}{p_2+p_3+3\choose 3}\cdots}.$$
Here the sum is over all sequences of nonnegative integers $(p_0,p_1,…)$ that sum to $r$. (Only finitely many terms in each such sequence will be nonzero.)
It is related to a result of Diaconis and Shahshahani that the trace of a random unitary matrix (with probability measure being given by the Haar measure) is distributed like a Gaussian variable, and indeed can be proven using this result, but I had initially hoped to proceed in the other direction. The above sum, after all, can be evaluated for specific $r$ by inspection (although this rapdily becomes a bit tedious for $r > 2$), and it ought to be possible to somehow summarize this information in a general.
Edit:
Alternatively phrased, we want
$$e^x = \sum_{p_0,p_1,.. = 0}^\infty \frac{x^{p_0+p_1+\cdots}}{\left(\prod_{j \geq 0}(p_j!)^2\right)\cdot\left(\prod_{k\geq 1}{p_{k-1}+p_k+k\choose k}\right)} = \lim_{\lambda \rightarrow \infty} \sum_{p_0,p_1,.. p_\lambda = 0}^\infty \frac{x^{p_0+p_1+\cdots + p_\lambda}}{\left(\prod_{j=0}^\lambda(p_j!)^2\right)\cdot\left(\prod_{k=1}^\lambda{p_{k-1}+p_k+k\choose k}\right){p_\lambda+\lambda+1\choose \lambda+1}}$$
Best Answer
I may as well write down how I've been attacking this, although I don't have a solution yet. Sequences $(p_i)$ of nonnegative integers with sum $r$ are in bijection with weakly increasing $r$-tuples $(n_1, n_2, \ldots, n_r)$ of positive integers. Specifically, given the sequence $(p_0, p_1, p_2, \ldots)$, form the sequence of partial sums $(q_1, q_2, \ldots)$ given by $q_i:=p_0+p_1+\ldots+p_{i-1}$. Let $n_j$ be the minimal $i$ for which $q_i \geq j$. For example, $(1,0,0,1,0,0,2,0,0,\ldots)$ corresponds to $(1, 4, 7,7)$. So, we want to compute the sum over all weakly increasing $r$-tuples and prove it is equal to $1/r!$.
For each weakly increasing $r$-tuple, let us sum instead over all $r!$ permutations of the $r$-tuple. So we can view our sum as being over all $r$-tuples of nonnegative integers, and we want to prove now that the sum is $1$. One difficulty is that some $r$-tuples will appear more than once. For example, $(1,4,7,7)$ will appear twice, because the permutation which switches the $7$'s stabilizes this quadruple. It turns out that the multiplicity of an $r$-tuples is precisely $\prod (p_i)!$. So, what we want to show is that $$\sum_{n_1, n_2, \ldots, n_r \geq 0} \frac{1}{\prod (p_i)! \prod \binom{p_{k-1}+p_k+k}{k}} =1$$
Now, when none of the $n_i$ are equal to each other, and when none of them differ by $1$, the summand is $$\frac{1}{n_1(n_1+1)n_2(n_2+1) \cdots n_r(n_r+1)} = \left( \frac{1}{n_1} - \frac{1}{n_1+1} \right) \cdot \left( \frac{1}{n_2} - \frac{1}{n_2+1} \right) \cdots \left( \frac{1}{n_r} - \frac{1}{n_r+1} \right).$$
This is set up beautifully to telescope. If I could just find a similar nice description for when the $n_i$ collide or are adjacent ...