Clase de permutación

En el estudio de permutaciones y patrones de permutación , una clase de permutación es un conjunto${\displaystyle C}$de permutaciones para las cuales cada patrón dentro de una permutación en${\displaystyle C}$también está en${\displaystyle C}$En otras palabras, una clase de permutación es una propiedad hereditaria de las permutaciones, o un conjunto descendente en el orden del patrón de permutación. ^{[ 1 ]} Una clase de permutación también puede conocerse como una clase de patrón , una clase cerrada o simplemente una clase de permutaciones.

Cada clase de permutación se puede definir mediante las permutaciones mínimas que no se encuentran dentro de ella, su base . ^{[ 2 ]} Una clase de permutación principal es una clase cuya base consta de una sola permutación. Así, por ejemplo, las permutaciones ordenables por pila forman una clase de permutación principal, definida por el patrón prohibido 231. Sin embargo, algunas otras clases de permutación tienen bases con más de un patrón o incluso con infinitos patrones.

Una clase de permutaciones que no incluye todas las permutaciones se denomina propia. A finales de la década de 1980, Richard Stanley y Herbert Wilf conjeturaron que para cada clase de permutaciones propia${\displaystyle C}$, hay alguna constante${\displaystyle K}$de tal manera que el número${\displaystyle |C_{n}|}$de longitud-${\displaystyle n}$Las permutaciones en la clase están limitadas superiormente por${\displaystyle K^{n}}$. Esto se conocía como la conjetura de Stanley-Wilf hasta que fue demostrada por Adam Marcus y Gábor Tardos . ^{[ 3 ]} Sin embargo, aunque el límite

${\displaystyle \lim _{n\to \infty }|C_{n}|^{1/n}}$

(Existe una cota ajustada en la base de la tasa de crecimiento exponencial) para todas las clases de permutación principales; queda abierto si existe para todas las demás clases de permutación. ^{[ 4 ]}

Dos clases de permutación se denominan equivalentes de Wilf si, para cada${\displaystyle n}$, ambos tienen el mismo número de permutaciones de longitud${\displaystyle n}$La equivalencia de Wilf es una relación de equivalencia y sus clases de equivalencia se denominan clases de Wilf. Son las clases combinatorias de las clases de permutación. Se conocen las funciones de conteo y las equivalencias de Wilf entre muchas clases de permutación específicas .