Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.