Salié permutaciones y justo permutaciones

Question

En octubre de 2010, publiqué un Mensual problema , que introdujo el concepto de una feria de permutación, que es una permutación $\pi$ tal que para cada $i$, o bien $\pi(i) > i$ e $\pi^{-1}(i) > i$ o $\pi(i) \le i$ e $\pi^{-1}(i) \le i$. De forma equivalente, de cada ciclo de $\pi$ es un punto fijo o una alternancia de ciclo de longitud, lo que significa que si $z$ es el mayor elemento del ciclo, entonces $$z > \pi(z) < \pi(\pi(z)) > \pi(\pi(\pi(z))) < \cdots < z.$$

No creo que nadie se ha estudiado la feria de permutaciones de forma explícita antes. Sin embargo, una permutación $\sigma$ a $\lbrace1, 2, \ldots, 2m\rbrace$ se dice que es un Salié permutación si para algunos $r\le m$, $$\sigma(1) < \sigma(2) > \sigma(3) < \cdots < \sigma(2r)$$ y $$\sigma(2r) < \sigma(2r+1) < \sigma(2r+2) < \cdots < \sigma(2m).$$ Estos han sido estudiados antes, y se puede demostrar por generatingfunctionology que el número de la feria de permutaciones es dos veces el número de Salié permutaciones. Esto es muy sugerente y sugerencias en una estrecha relación.

Pregunta: ¿Puede uno construir una explícita 2-a-1 mapa de la feria de permutaciones para Salié permutaciones?

Answer 1

Escriban una permutación en el ciclo de la forma, de la siguiente manera. Escribe todos ciclos de longitud $>1$ en orden decreciente de su elemento más pequeño, con el elemento más pequeño de cada ciclo de escritos como el de la izquierda elemento del ciclo. A continuación, agregar todos los puntos fijos en el aumento de la orden. Un ejemplo es $$ (3,9,4,6)(1,7,2,10)(5)(8). $$ Ahora borre el paréntesis. Obtenemos un Salié de permutación. Cada Salié permutación surge exactamente de dos maneras. Si el primer punto fijo a menos que el elemento que le precede en la representación sólo se describe (como es el caso del ejemplo anterior), entonces podemos absorber los dos primeros puntos fijos en el ciclo anterior (es decir, la de más a la derecha ciclo). De lo contrario, podemos convertir los dos últimos elementos de la de más a la derecha ciclo en puntos fijos. Para el ejemplo anterior obtenemos el adicional feria de permutación $$ (3,9,4,6)(1,7,2,10,5,8) $$ dando el mismo Sailé de permutación.

Adenda. Hay una pequeña inexactitud de arriba. Si 1 es un punto fijo, a continuación, en lugar de absorber el 1 y el punto fijo $j$ siguiente en el ciclo anterior, debemos crear un nuevo ciclo de $(1,j)$.