Permutación de Baxter

En matemáticas combinatorias , una permutación de Baxter es una permutación que satisface la siguiente propiedad generalizada de evitación de patrones : ${\displaystyle \sigma \en S_{n}}$

• No existen índices tales que o .${\displaystyle i<j<k}$${\displaystyle \sigma(j+1)<\sigma(i)<\sigma(k)<\sigma(j)}$${\displaystyle \sigma(j)<\sigma(k)<\sigma(i)<\sigma(j+1)}$

De manera equivalente, utilizando la notación para patrones vinculares , una permutación de Baxter es aquella que evita los dos patrones discontinuos y . ${\estilo de visualización 2-41-3}$${\estilo de visualización 3-14-2}$

Por ejemplo, la permutación en (escrita en notación de una línea ) no es una permutación de Baxter porque, tomando , y , esta permutación viola la primera condición. ${\displaystyle \sigma = 2413}$$Estilo de visualización S_{4}$${\displaystyle i=1}$${\displaystyle j=2}$${\estilo de visualización k=4}$

Estas permutaciones fueron introducidas por Glen E. Baxter en el contexto del análisis matemático . ^[1]

Para , el número de permutaciones de Baxter de longitud es ${\displaystyle n=1,2,3,\lpuntos}$${\displaystyle a_{n}}$${\estilo de visualización n}$

1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560, 67329992, 414499438, 2593341586, 16458756586,...

Esta es la secuencia OEIS : A001181 en la OEIS . En general, tiene la siguiente fórmula: ${\displaystyle a_{n}}$

${\displaystyle a_{n}\,=\,\sum _ {k=1}^{n}{\frac {{\binom {n+1}{k-1}}{\binom {n+1} {k}}{\binom {n+1}{k+1}}}{{\binom {n+1}{1}}{\binom {n+1}{2}}}}.}$^[2]

De hecho, esta fórmula se clasifica por el número de descensos en las permutaciones, es decir, hay permutaciones de Baxter con descensos. ^[3]${\displaystyle {\frac {{\binom {n+1}{k-1}}{\binom {n+1}{k}}{\binom {n+1}{k+1}}}{{ \binom {n+1}{1}}{\binom {n+1}{2}}}}}$$Estilo de visualización S_{n}$${\estilo de visualización k-1}$

• El número de permutaciones alternas de Baxter de longitud es , el cuadrado de un número de Catalan , y de longitud es${\estilo de visualización 2n}$${\displaystyle (C_{n})^{2}}$${\estilo de visualización 2n+1}$

$Estilo de visualización C_{n}C_{n+1}}$.

• El número de permutaciones de Baxter doblemente alternadas de longitud y (es decir, aquellas para las que tanto y su inversa son alternadas) es el número de Catalan . ^[4]${\estilo de visualización 2n}$${\estilo de visualización 2n+1}$${\estilo de visualización \sigma}$${\displaystyle \sigma ^{-1}}$$Estilo de visualización C_{n}$
• Las permutaciones de Baxter están relacionadas con las álgebras de Hopf , ^[5] los grafos planares , ^[6] y los teselaciones . ^{[7] [8]}

Baxter introdujo las permutaciones de Baxter al estudiar los puntos fijos de las funciones continuas conmutativas . En particular, si y son funciones continuas desde el intervalo hasta sí mismo tales que para todo , y para un número finito de en , entonces: ${\estilo de visualización f}$${\estilo de visualización g}$${\estilo de visualización [0,1]}$${\displaystyle f(g(x))=g(f(x))}$${\estilo de visualización x}$${\displaystyle f(g(x))=x}$${\estilo de visualización x}$${\estilo de visualización [0,1]}$

• el número de estos puntos fijos es impar;
• Si los puntos fijos son entonces y actúan como permutaciones mutuamente inversas en${\displaystyle x_{1}<x_{2}<\ldots <x_{2k+1}}$${\estilo de visualización f}$${\estilo de visualización g}$

${\displaystyle \{x_{1},x_{3},\ldots ,x_{2k+1}\}}$y ; ${\displaystyle \{x_{2},x_{4},\ldots ,x_{2k}\}}$

• La permutación inducida por on determina de forma única la permutación inducida por${\displaystyle f}$${\displaystyle \{x_{1},x_{3},\ldots ,x_{2k+1}\}}$

${\displaystyle f}$en ; ${\displaystyle \{x_{2}<,x_{4},\ldots ,x_{2k}\}}$

• bajo el reetiquetado natural , , etc., la permutación inducida en es una permutación de Baxter.${\displaystyle x_{1}\to 1}$${\displaystyle x_{3}\to 2}$${\displaystyle \{1,2,\ldots ,k+1\}}$

• Enumeraciones de clases de permutación específicas

• Secuencia OEIS A001181 (Número de permutaciones de Baxter de longitud n)