En el estudio de permutaciones y patrones de permutación , una clase de permutación es un conjunto de permutaciones tales que cada patrón dentro de una permutación en también está en . En otras palabras, una clase de permutación es una propiedad hereditaria de las permutaciones, o una bajada en el orden del patrón de permutación. [1] Una clase de permutación también puede conocerse como clase de patrón , clase cerrada o simplemente clase de permutaciones.
Cada clase de permutación puede definirse por 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 consiste en una única permutación. Así, por ejemplo, las permutaciones clasificables en 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 permutación que no incluye todas las permutaciones se llama propia. A finales de la década de 1980, Richard Stanley y Herbert Wilf conjeturaron que para cada clase de permutación adecuada, hay algo constante tal que el numero de longitudpermutaciones en la clase es superior delimitado por. Esto se conocía como la conjetura de Stanley-Wilf hasta que Adam Marcus y Gábor Tardos la probaron . [3] Sin embargo, aunque el límite
(un límite estricto en la base de la tasa de crecimiento exponencial) existe para todas las clases de permutación principales, está 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, ambos tienen el mismo número de permutaciones de longitud . 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 clases de permutación. Se conocen las funciones de conteo y las equivalencias de Wilf entre muchas clases de permutación específicas .
Referencias
- ^ Kitaev, Sergey (2011), Patrones en permutaciones y palabras , Monografías en informática teórica, Heidelberg: Springer, p. 59, doi : 10.1007 / 978-3-642-17333-2 , ISBN 978-3-642-17332-5, MR 3012380
- ^ Kitaev (2011) , Definición 8.1.3, p. 318.
- ^ Marcus, Adam; Tardos, Gábor (2004), "Matrices de permutación excluidas y la conjetura de Stanley-Wilf", Journal of Combinatorial Theory , Serie A, 107 (1): 153–160, doi : 10.1016 / j.jcta.2004.04.002 , MR 2063960.
- ^ Albert, Michael (2010), "Introducción a los métodos estructurales en patrones de permutación", Patrones de permutación , London Math. Soc. Lecture Note Ser., 376 , Cambridge Univ. Press, Cambridge, págs. 153-170, doi : 10.1017 / CBO9780511902499.008 , MR 2732828