Take the 2-minute tour ×

For given counting number $n$, consider all permutations $\pi$ of {$1,\ldots,n$}, generate for every $\pi$ its Robinson-Schensted pair of standard tableaux $(P_\pi,Q_\pi)$ and average together all the $P_\pi$ (viewed as functions on $\Bbb Z_+ \times \Bbb Z_+$). Now take the limit (which exists) as $n\rightarrow\infty$ to define a function $F(m,n)$.

Clearly $F(1,1)=1$, curiously $F(1,2)=F(2,1)=e$ and according to a calculation I just made $F(2,2)=1+e^2(BesselI(0, 2)-BesselI(1, 2))\approx 6.090678724$. (Maple's convention here for Bessel functions.) [Added later:] Another calculation now shows that $F(1,3)=F(3,1)=F(2,2)-1$; nevertheless, as yet I lack a combinatorial explanation why these two presumably transcendental quantities happen to differ by 1.

My question: does my function $F$ already appear in the literature?

One can use the hook formula to express values of $F$ as infinite series. The series converge quite rapidly but grow increasingly unwieldy with $m$ and $n$. What is known (or what can one say) about closed form expressions or simplified series expressions for the values?

The values of $F(m,n)$ have probabilistic interpretations as expected stopping times for certain random processes, as follows. Generate a sequence $(a_i)$ of independent uniform samples from $[0,1]$ until the cardinality of the largest union of $m$ increasing subsequences of $(a_i)$ exceeds by $n$ the cardinality of the largest union of $m-1$ increasing subsequences.

share|improve this question
I guess by "interpretations as the stopping times.." you mean the mean of the stopping times? –  John Jiang Dec 1 '11 at 7:30
Right! Thanks John Jiang –  David Feldman Dec 1 '11 at 7:46
I confirm that the interpretation in terms of unions of increasing subsequences is correctly stated. At the point where the mentioned difference first becomes $n$, the square $(m,n)$ in the tableau $Q$ gets filled with $i$, and it never changes since. (I don't think it is entirely obvious that the difference increases monotonically, but it does.) Of course the average over the tableaux $Q$ is the same as the average over the tableaux $P$. I've never seen this function $F$ mentioned before, but that's not saying much. –  Marc van Leeuwen Dec 1 '11 at 17:48
Thank you Marc van Leeuwen - I've now removed the hedge. –  David Feldman Dec 1 '11 at 19:05

1 Answer 1

This is a long comment:

My favourite object (right now) are the Gelfand-Tsetlin patterns, and are in a nice correspondence with Young tableaux. What happens if you do the same thing here, that is, elementwise average?

There is something called Macdonald processes, that has to do with these types of patterns, (I have just heard about them briefly), but perhaps you will obtain something related?

Note thought that this operation is quite different from what you are doing, but it might be easier to study.

Your question is What is the average value in a specific box, and the above question is essentially the dual; What is the average position of the box with content $i$.

share|improve this answer

Your Answer


