stringtranslate.com

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 :

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

.

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:

y ;

en ;

Véase también

Referencias

  1. ^ 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.
  2. ^ 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.
  3. ^ 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.
  4. ^ 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.
  5. ^ 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.
  6. ^ 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.
  7. ^ Korn, M. (2004), Propiedades geométricas y algebraicas de teselados poliominós, tesis doctoral, Instituto Tecnológico de Massachusetts.
  8. ^ 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