About the Moments of the Generalized Ulam Problem

Given Sₙ, let Z₍, ₊ () =₁ ₈䃑<<₈䂵 ₍ 1 (\ ₈䃑<<₈䂵\ denote the number of increasing subsequences of length k. Consider the problem of studing the distribution of Z₍, ₊ for general k and n. For the 2nd moment, Ross Pinsky made a combinatorial study by considering a pair of subsequences i^ (r) ₁<<i^ (r) ₖ for r \1, 2\, and conditioning on the size of the intersection j = |\i₁^{ (1), , i^ (1) ₖ\} \i^{ (2) ₁, , i^ (2) ₖ\}|. We obtain the large deviation rate function for EZ₍, ₊ Z₍, in the asymptotic regime k n^1/2, n^1/2 as n, for, (0, ). This uses multivariate generating function techniques, as found in the textbook of Pemantle and Wilson. For higher moments, if one thinks of the ``overlap'' between two subsequences i^ (r) ₁<<i^ (r) ₖ for r \1, 2\, as the size of their intersection j, then an ultrametric ansatz leads to rigorous lower bounds for the higher moments. For the 3rd moment, the replica symmetric ansatz leads to a complete elliptic integral for the generating function, following a method similar to the diagonal method of Furstenberg, Hautus and Klarner.