Permutación en capas

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 primeros trabajos que establecieron la importancia de las permutaciones en capas fue Bóna (1999), que estableció la conjetura de Stanley-Wilf para clases de permutaciones que prohibían una permutación en capas, antes de que la conjetura se demostrara de manera más general. ^[2]

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

Las permutaciones en capas también pueden describirse de manera equivalente como las permutaciones que no contienen los patrones de permutación 231 o 312. Es decir, ningún tres elementos en la permutación (independientemente de si son consecutivos) tiene el mismo orden que cualquiera de estos triples prohibidos.

Una permutación en capas de los números de a se puede describir de forma única mediante el subconjunto de los números de a que son el primer elemento de un bloque invertido. (El número siempre es el primer elemento de su bloque invertido, por lo que es redundante para esta descripción). Debido a que existen subconjuntos de los números de a , también existen permutaciones en capas de longitud . ${\estilo de visualización 1}$${\estilo de visualización n}$${\estilo de visualización 1}$${\estilo de visualización n-1}$${\estilo de visualización n}$$Estilo de visualización 2^{n-1}}$${\estilo de visualización 1}$${\estilo de visualización n-1}$$Estilo de visualización 2^{n-1}}$${\estilo de visualización n}$

Las permutaciones en capas son equivalentes de Wilf a otras clases de permutaciones, lo que significa que la cantidad de permutaciones de cada longitud es la misma. Por ejemplo, las permutaciones de Gilbreath se cuentan con la misma función . ^[3]$Estilo de visualización 2^{n-1}}$

El superpatrón más corto de las permutaciones de longitud en capas es en sí mismo una permutación en capas. Su longitud es un número de ordenación , el número de comparaciones necesarias para que la ordenación por inserción binaria ordene los elementos. ^{[1] [4]} Para estos números son ${\estilo de visualización n}$${\estilo de visualización n+1}$${\displaystyle n=1,2,3,\dots }$

1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, ... (secuencia A001855 en la OEIS )

y en general se dan por la fórmula

${\displaystyle (n+1){\bigl \lceil }\log _{2}(n+1){\bigr \rceil }-2^{\left\lceil \log _{2}(n+1)\right\rceil }+1.}$^[1]

Toda permutación en capas es una involución . Son exactamente las involuciones que evitan 231 y también son exactamente las involuciones que evitan 312. ^[5]

Las permutaciones en capas son un subconjunto de las permutaciones ordenables por pila , que prohíben el patrón 231 pero no el patrón 312. Al igual que las permutaciones ordenables por pila, también son un subconjunto de las permutaciones separables , las permutaciones formadas por combinaciones recursivas de sumas directas y sesgadas.