Número de permutaciones con subsecuencias crecientes más largas de longitud máxima $n$

Question

¿Existe una expresión conocida o un límite superior no trivial para el número de permutaciones en $S_k$ con la subsecuencia creciente más larga de longitud como máximo $n$ ?

Dejemos que $l(\sigma)$ denotan la longitud de la subsecuencia creciente más larga de una permutación $\sigma\in S_k$ . Parece que se sabe mucho sobre $l(\sigma)$ para una permutación aleatoria (y su escalado asintótico), pero ¿existen límites superiores para el número de permutaciones en $\sigma\in S_k$ con $l(\sigma)\leq n$ .

Motivación/contexto de esta pregunta: los momentos de las trazas de los unitarios aleatorios. Se sabe que $\int dU |{\rm tr}(U)|^{2k} = k!$ para $k\leq n$ donde integramos sobre el grupo unitario $U(n)$ con respecto a la medida de Haar. En general, para cualquier $k$ y $n$ se puede escribir la expresión como [1] $$ \int dU |{\rm tr}(U)|^{2k} = \sum_{\lambda \vdash k,~\ell(\lambda)\leq n} \chi_\lambda(\mathbb{I})^2\,, $$ suma de particiones de números enteros $\lambda$ de $k$ con una longitud máxima de $n$ y donde $\chi_\lambda(\mathbb{I})$ es el carácter de identidad con respecto a $\lambda$ . En el lado derecho se cuenta el número de pares de tablas de Young con anchura $\leq n$ que equivale a contando el número de permutaciones en $S_k$ sin subsecciones crecientes más largas que $n$ . Estoy esencialmente interesado en los límites superiores de esta cantidad que son más ajustados que el límite trivial de $k!$ .

[1] E. Rains, "Increasing Subsequences and the Classical Groups", Electron. J. Comb. 5 (1998) R12. http://eudml.org/doc/119270 .

Answer 1

Existe una fórmula determinista explícita para estos números debida a Gessel en Funciones simétricas y recursividad P (JCTA, 1990). La asintótica se conocía mucho antes y aparece en un artículo de Amitai Regev Valores asintóticos de los grados asociados a las franjas de los diagramas jóvenes (Adv. Math. 1981). La asintótica bruta es que el $k$ raíz del número de tales permutaciones se aproxima $n^2$ . Tenga en cuenta que en la mayoría de la literatura, $k$ y $n$ desempeñarán los papeles opuestos, es decir, la pregunta será sobre la enumeración de permutaciones en $S_n$ sin una subsecuencia creciente de tamaño superior a $k$ .

Answer 2

Una fórmula explícita es la fórmula del producto gancho, debida a Schensted, creo. Esta fórmula se utiliza en el trabajo clásico de Logan y Shepp, así como en Vershik-Kerov. Véase, por ejemplo, la ecuación (1.1) en el Documento Logan-Shepp

La asintótica dependerá en gran medida de si $n>2\sqrt{k}$ o no. Supongo que querías decir $n<2\sqrt{k}$ . En ese caso, la asintótica (bajo el nombre de principio de las grandes desviaciones) son conocidas, e implican el funcional Logan-Shepp. Véase Subsecuencias crecientes de muestras iid y Grandes desviaciones para secuencias crecientes en el plano . También hay trabajos en el régimen de desviaciones moderadas debido a Lowe.

Answer 3

Esto está relacionado con la conjetura de Stanley-Wilf ( ahora un teorema ). De forma más general, se puede considerar $S_k(\sigma)$ el número de permutaciones de $k$ elementos que no contienen el patrón dado por la permutación $\sigma$ . Aquí se está viendo el caso particular $S_k(12\cdots(n+1))=:u_n(k)$ . Referencias exhaustivas sobre el tema son los libros "Combinatoria de Permutaciones" por Bóna y "Patrones en Permutaciones y Palabras" por Kitaev. El teorema 4.10 del libro de Bóna da una prueba combinatoria muy elemental para el límite $$ u_n(k)\le n^{2k}\ . $$ Un límite similar fue conjeturado por Arratia para cualquier patrón $\sigma$ de longitud $n+1$ pero esto es se sabe que fallan para $\sigma=1324$ .

Obsérvese que el límite es trivial a partir de la fórmula de la integral de Haar porque $U$ tiene valores propios de módulo uno y por tanto $|{\rm tr} (U)|\le n$ . Además, los números forman una secuencia supermultiplicativa por un resultado de Arratia (mismo artículo que el anterior). La propiedad supermultiplicativa también se deduce de la integral de Haar: la $S_k(12\cdots(n+1))$ secuencia en $k$ siendo una secuencia de momentos de Stieltjes es log-convexa.

Primero pensé que este hecho ( El lema subaditivo de Feteke ) combinada con la fórmula asintótica de Regev podría dar un mejor límite superior exponencial (en lugar de asintótico). Sin embargo, uno termina con el mismo límite superior. Eso es porque la fórmula de Regev da, después de calcular una integral de Selberg $$ u_n(k)\sim 1!2!\cdots(n-1)!\ (2\pi)^{-\frac{n-1}{2}} \ 2^{-\frac{n^2-1}{2}}\ n^{\frac{n^2}{2}}\ \frac{n^{2k}}{k^{\frac{n^2-1}{2}}} $$ cuando $k\rightarrow\infty$ (He tomado la fórmula de Encuesta ICM de Stanley ). Por lo tanto, el crecimiento exponencial correcto de $n^{2k}$ ya está en el límite trivial.