About the Moments of the Generalized Ulam Problem

Abstract

Given $\pi \in S_n$, let $Z_{n,k}(\pi )={\sum }_{1\le i_1<\cdots <i_k\le n}1(\{{\pi }_{i_1}<\cdots <{\pi }_{i_k}\}$ denote the number of increasing subsequences of length $k$. Consider the "generalized Ulam problem," studying the distribution of $Z_{n,k}$ for general $k$ and $n$. For the 2nd moment, Ross Pinsky initiated a combinatorial study by considering a pair of subsequences $i_1^{(r)}<\cdots <i_k^{(r)}$ for $r\in \{1,2\}$, and conditioning on the size of the intersection $j=|\{i_1^{(1)},\dots ,i_k^{(1)}\}\cap \{i_1^{(2)},\dots ,i_k^{(2)}\}|$. We obtain the exact large deviation rate function for $\mathbf{E}[Z_{n,k}{Z}_{n,\ell }]$ in the asymptotic regime $k\sim \kappa n^{1/2}$, $\ell \sim \lambda n^{1/2}$ as $n\to \infty$, for $\kappa ,\lambda \in (0,\infty )$. This uses multivariate generating function techniques, as found in the textbook of Pemantle and Wilson. The requisite generating function enumerates pairs of up-right paths in $d=2$, which both end at $(k,\ell )$ with a given number of intersections. We also evaluate the analogous generating function for pairs of $(+\mathbf{i},+\mathbf{j},+\mathbf{k})$ paths in $d=3$, which both end at $(k,\ell ,m)$, which has some utility in calculating the 3rd moment. Finally, we consider a simpler problem involving partitions instead of permutations, where all moments are calculable and the replica symmetric ansatz can be stated if not proved.

36 pages, 1 figure, made one correction