Bijección entre permutaciones "circularmente no consecutivas" y permutaciones con un punto fijo

Question

Una permutación $\pi$ de $[n]:=\{1,2,\dots,n\}$ se llama circularmente no consecutiva (CNC) si $\pi_{i+1}-\pi_i\neq 1$ para todos $i=1,2,\dots,n-1$ y además $\pi_1-\pi_n\ne 1$ . En otras palabras, $i+1$ no se produce inmediatamente después de $i$ para cualquier $i\in \{1,2,\dots,n-1\}$ donde consideramos que la primera entrada de la permutación se produce inmediatamente después de la última de forma circular.

Hay $3$ Permutaciones CNC de $[3]$ : $(1,3,2)$ y sus dos rotaciones, $(3,2,1)$ y $(2,1,3)$ . En general, todos los $n$ Las rotaciones de una permutación CNC también son CNC.

Se puede demostrar que el número de permutaciones CNC es igual al número de permutaciones con exactamente un punto fijo. Se pueden contar ambas cantidades con un argumento de exclusión de la inclusión y encontrar que las expresiones resultantes son casualmente las mismas, ambas iguales a $$n!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}$$

¿Se puede dar una biyección entre las permutaciones CNC de $[n]$ y permutaciones de $[n]$ con un punto fijo?

De forma equivalente, las permutaciones con un punto fijo pueden dividirse en $n$ clases iguales basadas en qué punto es fijo, al igual que las permutaciones CNC pueden dividirse en clases de rotación circular. Así que sería equivalente a encontrar una biyección entre permutaciones CNC para las que $\pi_n=n$ y permutaciones donde el único punto fijo es $\pi_n=n$ . Esta última está obviamente en biyección con las derivaciones de $[n-1]$ .

Answer 1

He aquí una respuesta potencialmente insatisfactoria, que publicaría en un comentario si tuviera suficiente reputación para comentar.

Una forma de ver que el número de permutaciones CNC de $[n]$ con $\pi_n=n$ es igual al número de desviaciones de $[n-1]$ es observar que ambas funciones de recuento satisfacen la misma relación de recurrencia $f(n)=(n-2)f(n-1)+(n-2)f(n-2)$ .

Para las permutaciones del CNC, estos dos términos corresponden a los dos casos de si nuestra permutación de $[n]$ sigue siendo CNC después de borrar el $n$ desde el final. Si lo hace, la permutación resultante de $[n-1]$ es uno de los $n-2$ rotaciones no triviales de una permutación CNC arbitraria de $[n-1]$ que termina con $n-1$ . En caso contrario, nuestra permutación de $[n]$ es de la forma $(a+1,\dots,a,n)$ , donde el $(\dots,a)$ es una permutación CNC arbitraria de $[n-2]$ (después de restar uno a cada valor mayor que $a$ ).

Del mismo modo, para las alteraciones de $[n-1]$ los dos términos corresponden a los dos casos de $n-1$ está en un ciclo de 2. Si no lo está, nuestro desvarío se obtiene empalmando el $n-1$ en un ciclo en un desorden arbitrario de $[n-2]$ (después de cualquiera de sus $n-2$ elementos). De lo contrario, nuestro trastorno de $[n-1]$ se obtiene emparejando el $n-1$ con un elemento arbitrario de $[n-2]$ y elegir una desviación arbitraria del resto $n-3$ elementos.

Basándonos en estas observaciones, podríamos definir recursivamente la biyección deseada (básicamente identificando cada permutación con un camino a través del árbol de decisión utilizado para construirla), pero no estoy seguro de que esto revele una estructura más interesante.

Answer 2

Bien, he encontrado la respuesta en un maravillosa entrada de blog de Mike Spivey . La siguiente discusión implica una mejor manera de ver el problema.

A partir de ahora, un sucesión en una permutación es un índice $i\in \{1,\dots,n-1\}$ para lo cual $\pi({i+1})=\pi(i)+1$ . Además, un sucesión ampliada se define como sigue; dada una permutación $\pi:\{1,\dots,n\}\to \{1,\dots,n\}$ , extienda esto a una función $\pi':\{0,\dots,n\}\to\{0,\dots,n\}$ al establecer $\pi'(0)=0$ y $\pi'(i)=\pi(i)$ para $i\in \{1,\dots,n\}$ . A continuación, una larga sucesión de $\pi$ se define como una sucesión de $\pi'$ . La única diferencia entre ambos conceptos es que $\pi(1)=1$ cuenta como una sucesión ampliada, pero no una sucesión.

La razón de esta curiosa definición es que las sucesiones extendidas se comportan igual que los puntos fijos, en el sentido de que para cualquier $k\in \{0,\dots,n\}$ , el número de permutaciones con $k$ puntos fijos es igual al número de permutaciones con $k$ éxitos prolongados. Esto se demuestra con la siguiente biyección. En la columna de la derecha, $i$ representa un punto fijo genérico mayor que $1$ . Obsérvese cómo los puntos fijos, $3$ y $6$ se convierten en sucesiones en el resultado. También hay que demostrar que si $1$ es un punto fijo, que termina al principio del resultado (por lo que es una sucesión extendida).

Paso de biyección

Ejemplo           

Efecto sobre los puntos fijos

Escriba $\pi$ en notación de una línea.

$[2,5,\def\r{\color{red}}\r3,1,4,\r 6]$

$\pi(i)=i$

Mover cada entrada de $\pi$ un paso a la izquierda, y la primera entrada al final, para obtener una nueva permutación en notación de una línea.

$[5,\def\r{\color{red}}\r3,1,4,\r 6,2]$

$\pi(i-1)=i$

Escribe el resultado del último paso en notación de ciclo, de forma que cada ciclo tenga su más grande elemento escrito último y los ciclos disminuir en orden del elemento más grande.

$(2,3,1,5,6)(4)$

$i$ sigue $i-1$ en un ciclo.

Borra los paréntesis e interpreta el resultado en notación de una línea.

$[2,\r 3,1,5,\r 6,4]$

$i$ tiene éxito $i-1$ .