About the Moments of the Generalized Ulam Problem

Given π ∈ Sₙ, let Zn,k(π)=∑1≤ i₁<<iₖ≤ n 1(\ πi₁<<πiₖ\ denote the number of increasing subsequences of length k. Consider the problem of studing the distribution of Zn,k for general k and n. For the 2nd moment, Ross Pinsky made a combinatorial study by considering a pair of subsequences i⁽ʳ⁾₁<<i⁽ʳ⁾ₖ for r ∈ \1,2\, and conditioning on the size of the intersection j = |₁⁽¹⁾,,i⁽¹⁾ₖ\ ∩ ⁽²⁾₁,,i⁽²⁾ₖ\|. We obtain the large deviation rate function for E[Zn,k Zn,] in the asymptotic regime k~ κ n1/2, ~ λ n1/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⁽ʳ⁾₁<<i⁽ʳ⁾ₖ 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.