Generating Function for Pinsky's Combinatorial Second Moment Formula for the Generalized Ulam Problem

Abstract

Given a uniform random permutation $\pi \in S_n$, let $Z_{n,k}$ be equal to the number of increasing subsequences of length $k$: so $Z_{n,k}=|\{(i_1,\dots ,i_k)\in {\mathbb{Z}}^k:1\le i_1<\cdots <i_k\le n,{\pi }_{i_1}<\cdots <{\pi }_{i_k}\}|$. In an important paper, Ross Pinsky proved $\mathbf{E}\left[Z_{n,k}^2\right]$ is equal to ${\sum }_{i}A(k-i,i)B(n,2k-i)$, where for any nonnegative integers $N$ and $j$, we have $B(N,j)=\left(\genfrac{}{}{0ex}{}{N}{j}\right)/j!$ and $A(N,j)$ is a particular nonnegative integer, which Pinsky characterized in two different ways. One characterization of $A(N,j)$ involves the occupation time of the $x$-axis prior to a first return to the origin. Using this, he proved a law of large numbers for the sequence $Z_{n,k_n}$ when $k_n=o(n^{2/5})$ as $n\to \infty$. In a follow-up paper, he also proved the sequence $Z_{n,k_n}$ fails to obey a law of large numbers when $1/k_n=o(1/n^{4/9})$ as $n\to \infty$. Here, we return to his combinatorial formula for the the second moment of $Z_{n,k}$, and we obtain a generating function for the $A(N,j)$ triangular array. We are motivated by the hope of applying spin glass techniques to the well-known Ulam's problem to see if this gives a new perspective.

35 pages, 6 figures: added complete Elliptic integrals