Log-concavity and q-Log-convexity Conjectures on the Longest Increasing Subsequences of Permutations

Abstract

Let $P_{n,k}$ be the number of permutations $\pi$ on [n]={1, 2,..., n} such that the length of the longest increasing subsequences of $\pi$ equals k, and let $M_{2n,k}$ be the number of matchings on [2n] with crossing number k. Define $P_n(x)={\sum }_k{P}_{n,k}{x}^k$ and $M_{2n}(x)={\sum }_k{M}_{2n,k}{x}^k$. We propose some conjectures on the log-concavity and q-log-convexity of the polynomials $P_n(x)$ and $M_{2n}(x)$. We also introduce the notions of $\infty$-q-log-convexity and $\infty$-q-log-concavity, and the notion of higher order log-concavity with respect to $\infty$-q-log-convex or $\infty$-q-log-concavity. A conjecture on the $\infty$-q-log-convexity of the Boros-Moll polynomials is presented. It seems that $M_{2n}(x)$ are log-concave of any order with respect to $\infty$-q-log-convexity.

7 pages