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

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

• It's probbably to early for me, but I can't follow the pattern of your summand. I would guess that writing it clearly is a half of solution... Jul 3, 2010 at 23:28
• I've written it slightly differently in an edit at the bottom; let me know if this is more transparent. Jul 4, 2010 at 0:11
• Or more concretely: for r=2, the situation is to sum over the following sets for $(p_0,p_1,...)$: (2,0,0,...), (0,2,0,0,...), (0,0,2,0,...),... ;(1,1,0,0,...), (1,0,1,0,0...), ... ;(0,1,1,0,0,...), (0,1,0,1,0,...),...; ... Using partial fractions, it is not difficult to see that sum over all these entries is 1/2. Jul 4, 2010 at 0:55
• I'm just realizing how messed up combinatorics must be when the word "ordered" may mean two completely different things... (I first thought it meant $p_0\geq p_1\geq ...$) Jul 4, 2010 at 9:22
• Ah, maybe that was Wadim's confusion as well. Probably the clarifying remark under the sum actually added confusion in retrospect. I made one more edit changing 'ordered set' to 'sequence.' Jul 4, 2010 at 11:25

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

• This certainly 'smells' like the right reduction to make! My suspicion is that from here one has to group the remaining terms in the right way (as opposed to considering them in isolation) to get a nice identity, but I haven't been able to see how to do it yet... Jul 8, 2010 at 8:33

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

• This is an interesting idea. I have to admit, an expansion of Bessel functions (and some rearrangement) is how I originally came to this identity. To me it would be a bit surprising if the behavior of $S_\lambda(x)$ follows from some sort of concentration, but I could very well be wrong. Jul 8, 2010 at 8:37
• Yes, "concentration" does not tell the whole story, for it still does not explain the role of the Bessel function. Actually, I would have trusted more in: find a convenient equation satisfied by the complete sum, and prove that it identifies the exponential function (that's what I had in mind with that integral representation...). Jul 8, 2010 at 9:39