Evaluation of a combinatorial sum (that comes from random matrices)

Question

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

Answer 1

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

Answer 2

Some hints. The sum indicized on $\mathbb{N}^{< \omega}$ would like to be the expansion of an infinite product of absolutely convergent series, since it is close to be that, but it's not. To get a complete structure of such an expansion, a natural start seems to be: express the reciprocals of the binomial coefficients in terms of the corresponding Beta function integrals (using new integration variables $t_0, t_1,\dots,t_\lambda$ etc). I mean: let's use the identity: $$\frac{1}{{p+q+k \choose k }}=k \frac{(p+q)!(k-1)!}{(p+q+k)!}=k\int_0^1 s^{\\ p+q}(1-s)^{k-1}ds. $$

This way the sum in your last limit, that I will denoe $S_{\lambda+1}(x),$ becomes an integral of a certain product of $\lambda+1$ simpler functions, also depending on the parameter $x$ over $t\in[0,1]^{\lambda+1}.$ (Or, if you like it more, the whole sum $S_\infty$ can be represented as an integral over $[0,1]^{\mathbb{N}}$, with respect to the countable power of the uniform measure, of a certain function $F:\mathbb{C}\times [0,1]^{\mathbb{N}}\to\mathbb{C}$, expressed as infinite product).

Specifically, for $x\in \mathbb{C}$ let's consider the series (essentially, a Bessel function of order 0). $$J(x):=\sum_{n=0}^\infty\frac{ x^{\, n}}{(n!)^2}.$$ Then one finds: $$S_{\lambda}(x)=\int_{I^{\lambda}}\,J(xt_0)\,J(xt_0t_1)\,J(xt_1t_2)\dots J(xt_{\lambda-2}t_{\lambda-1})\,J(xt_{\lambda-1})\ \lambda!\!\!\prod_{0\leq k<\lambda}(1-t_j)^{\,j}\ dt.$$

(Now, this still needs some work before concluding as you want -the role of the Bessel function here is quite obscure to me; but notice that the latter expression at least gives an account of what's on. We are integrating the product $J(xt_0)J(xt_0t_1)\dots J(xt_{\lambda-2}t_{\lambda-1})J(xt_{\lambda-1})$ with probability measures on the cubes $I^\lambda,$ and these measures are slowly concentrating near $0.$ What makes delicate the evaluation, of course, is that the dimension of the cube is also going to infinity; nevertheless a reasonable guess is that the integral is close to the product of the $J$'s evaluated at the point $x/\lambda$, which would imply $$S_\lambda(x)=\left(1+\frac{x+o(1)}{\lambda}\right)^{\lambda}=\,e^x+o(1),$$ as $\lambda\to\infty.$)

(Edit: I have shifted by one the previous definition of $S_n$ so that now it is a sum over $n$-ples, and equals an $n$-fold iterated integral.)

Example: for $n=5$, the above integral, computed formally with Maple, is $$S_5(x)=1+x+\frac{1}{2}x^2+\frac{1}{6}x^3+\frac{1}{24}x^4+\frac{1}{120}x^5+\frac{1}{720}x^6+\frac{5039}{25401600}x^7+O(x^8).$$