En las matemáticas de las permutaciones , una permutación en capas es una permutación que invierte bloques contiguos de elementos. De manera equivalente, es la suma directa de permutaciones decrecientes. [1]
Uno de los trabajos anteriores que estableció la importancia de las permutaciones en capas fue Bóna (1999) , que estableció la conjetura de Stanley-Wilf para las clases de permutaciones que prohíben una permutación en capas, antes de que la conjetura se probara de manera más general. [2]
Ejemplo
Por ejemplo, las permutaciones en capas de longitud cuatro, con los bloques invertidos separados por espacios, son las ocho permutaciones
- 1 2 3 4
- 1 2 43
- 1 32 4
- 1 432
- 21 3 4
- 21 43
- 321 4
- 4321
Caracterización por patrones prohibidos
Las permutaciones en capas también se pueden describir de manera equivalente como las permutaciones que no contienen los patrones de permutación 231 o 312. Es decir, no hay tres elementos en la permutación (independientemente de si son consecutivos) que tengan el mismo orden que cualquiera de estos triples prohibidos.
Enumeración
Una permutación en capas de los números de a puede ser descrito de forma única por el subconjunto de los números de a que son el primer elemento en un bloque invertido. (El número es siempre el primer elemento en su bloque invertido, por lo que es redundante para esta descripción). subconjuntos de los números de a , también hay permutación en capas de longitud .
Las permutaciones en capas son Wilf equivalente a otras clases de permutación, lo que significa que el número de permutaciones de cada longitud es el mismo. Por ejemplo, las permutaciones de Gilbreath se cuentan por la misma función. [3]
Superpatrones
El superpatrón más corto de las permutaciones de longitud en capases en sí mismo una permutación en capas. Su longitud es un número de orden , el número de comparaciones necesarias para la inserción binaria especie a especieelementos. [1] [4] Para estos números son
y en general vienen dados por la fórmula
Clases de permutación relacionadas
Cada permutación en capas es una involución . Son exactamente las involuciones que evitan el número 231, y también son exactamente las involuciones que evitan el número 312. [5]
Las permutaciones en capas son un subconjunto de las permutaciones ordenables en pila , que prohíben el patrón 231 pero no el patrón 312. Al igual que las permutaciones ordenables en pila, también son un subconjunto de las permutaciones separables , las permutaciones formadas por combinaciones recursivas de directo y sumas sesgadas.
Referencias
- ^ a b c Albert, Michael ; Engen, Michael; Pantone, Jay; Vatter, Vincent (2018), "Permutaciones universales en capas", Electronic Journal of Combinatorics , 25 (3): P23: 1 – P23: 5
- ^ Bóna, Miklós (1999), "La solución de una conjetura de Stanley y Wilf para todos los patrones en capas", Journal of Combinatorial Theory , Serie A, 85 (1): 96-104, doi : 10.1006 / jcta.1998.2908 , MR 1659444
- ^ Robertson, Aaron (2001), "Permutaciones restringidas por dos patrones distintos de longitud tres", Advances in Applied Mathematics , 27 (2–3): 548–561, arXiv : math / 0012029 , doi : 10.1006 / aama.2001.0749 , MR 1868980
- ^ Gray, Daniel (2015), "Límites en superpatrones que contienen todas las permutaciones en capas", Gráficos y combinatorios , 31 (4): 941–952, doi : 10.1007 / s00373-014-1429-x , MR 3357666
- ^ Egge, Eric S .; Mansour, Toufik (2004), "231-evitando involuciones y números de Fibonacci", The Australasian Journal of Combinatorics , 30 : 75–84, arXiv : math / 0209255 , MR 2080455