En matemáticas combinatorias , una permutación de Baxter es una permutación que satisface la siguiente propiedad generalizada de evitación de patrones :
- No existen índices tales que o .
De manera equivalente, utilizando la notación para patrones vinculares , una permutación de Baxter es aquella que evita los dos patrones discontinuos y .
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.
Estas permutaciones fueron introducidas por Glen E. Baxter en el contexto del análisis matemático . [1]
Enumeración
Para , el número de permutaciones de Baxter de longitud es
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:
- [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]
Otras propiedades
- El número de permutaciones alternas de Baxter de longitud es , el cuadrado de un número de Catalan , y de longitud es
.
- 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]
- Las permutaciones de Baxter están relacionadas con las álgebras de Hopf , [5] los grafos planares , [6] y los teselaciones . [7] [8]
Motivación: funciones de desplazamiento
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:
- el número de estos puntos fijos es impar;
- Si los puntos fijos son entonces y actúan como permutaciones mutuamente inversas en
y ;
- La permutación inducida por on determina de forma única la permutación inducida por
en ;
- bajo el reetiquetado natural , , etc., la permutación inducida en es una permutación de Baxter.
Véase también
Referencias
- ^ Baxter, Glen (1964), "Sobre puntos fijos de la composición de funciones conmutativas", Actas de la American Mathematical Society , 15 (6): 851–855, doi : 10.2307/2034894 , JSTOR 2034894.
- ^ Chung, FRK ; Graham, RL ; Hoggatt, VE Jr. ; Kleiman, M. (1978), "El número de permutaciones de Baxter" (PDF) , Journal of Combinatorial Theory , Serie A, 24 (3): 382–394, doi : 10.1016/0097-3165(78)90068-7 , MR 0491652.
- ^ Dulucq, S.; Guibert, O. (1998), "Permutaciones de Baxter", Matemáticas discretas , 180 (1–3): 143–156, doi : 10.1016/S0012-365X(97)00112-X , MR 1603713.
- ^ Guibert, Olivier; Linusson, Svante (2000), "Las permutaciones de Baxter doblemente alternadas son catalanas", Discrete Mathematics , 217 (1–3): 157–166, doi : 10.1016/S0012-365X(99)00261-7 , MR 1766265.
- ^ Giraudo, Samuele (2011), "Estructuras algebraicas y combinatorias en permutaciones de Baxter", 23.ª Conferencia internacional sobre series de potencias formales y combinatoria algebraica (FPSAC 2011) , Discrete Math. Theor. Comput. Sci. Proc., vol. AO, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, págs. 387–398, arXiv : 1011.4288 , Bibcode :2010arXiv1011.4288G, MR 2820726.
- ^ Bonichon, Nicolás; Bousquet-Mélou, Mireille ; Fusy, Éric (octubre de 2009), "Permutaciones de Baxter y orientaciones bipolares planas", Séminaire Lotharingien de Combinatoire , 61A , art. B61Ah, 29 páginas, arXiv : 0805.4180 , código Bib : 2008arXiv0805.4180B, SEÑOR 2734180.
- ^ Korn, M. (2004), Propiedades geométricas y algebraicas de teselados poliominós, tesis doctoral, Instituto Tecnológico de Massachusetts.
- ^ Ackerman, Eyal; Barequet, Gill; Pinter, Ron Y. (2006), "Una biyección entre permutaciones y planos de planta, y sus aplicaciones", Discrete Applied Mathematics , 154 (12): 1674–1684, doi : 10.1016/j.dam.2006.03.018 , MR 2233287.
Enlaces externos
- Secuencia OEIS A001181 (Número de permutaciones de Baxter de longitud n)