Baxterova permutace - Baxter permutation

v kombinační matematika, a Baxterova permutace je permutace ${ displaystyle sigma v S_ {n}}$ který splňuje následující zobecněné vyhýbání se vzorům vlastnictví:

Neexistují žádné indexy i < j < k takhle σ(j + 1) < σ(i) < σ(k) < σ(j) nebo σ(j) < σ(k) < σ(i) < σ(j + 1).

Ekvivalentně, použití notace pro vinkulární vzory, Baxterova permutace je taková, která se vyhýbá dvěma přerušovaným vzorům 2-41-3 a 3-14-2.

Například permutace σ = 2413 palců S₄ (napsáno v jednorázová notace ) je ne Baxterova permutace, protože, brát i = 1, j = 2 a k = 4, tato permutace porušuje první podmínku.

Tyto permutace zavedl Glen E. Baxter v kontextu matematická analýza.^[1]

Výčet

Pro n = 1, 2, 3, ..., číslo A_n Baxterových permutací délky n je

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

Toto je sekvence OEIS: A001181 v OEIS. Obecně, A_n má následující vzorec:

{ displaystyle a_ {n} , = , součet _ {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]

Ve skutečnosti je tento vzorec odstupňován podle počtu sestupy v permutacích, tj. existují ${ displaystyle { frac {{ binom {n + 1} {k-1}} { binom {n + 1} {k}} { binom {n + 1} {k + 1}}} {{ binom {n + 1} {1}} { binom {n + 1} {2}}}}}$ Baxterovy permutace v S_n s k - 1 sjezd.^[3]

Další vlastnosti

Počet střídavý Baxterovy permutace délky 2n je (C_n)², čtverec a Katalánské číslo a délky 2n +1 je C_nC_n+1.
Počet dvojnásobně se střídajících Baxterových permutací délky 2n a 2n + 1 (tj. Ty, pro které oba σ a jeho inverzní σ⁻¹ se střídají) je katalánské číslo C_n.^[4]
Baxterovy permutace souvisí s Hopfovy algebry,^[5] rovinné grafy,^[6] a obklady.^[7]^[8]

Motivace: funkce dojíždění

Baxter zavedl Baxterovy permutace při studiu pevných bodů dojíždění spojité funkce. Zejména pokud F a G jsou spojité funkce od intervalu [0, 1] k sobě takové, že F(G(X)) = G(F(X)) pro všechny X, a F(G(X)) = X pro konečně mnoho X v [0, 1], pak:

počet těchto pevných bodů je lichý;
pokud jsou pevné body X₁ < X₂ < ... < X_{2k + 1} pak F a G působí jako vzájemně inverzní permutace na {X₁, X₃, ..., X_{2k + 1}} a {X₂, X₄, ..., X_2k};
permutace vyvolaná F na {X₁, X₃, ..., X_{2k + 1}} jednoznačně určuje permutaci vyvolanou F na {X₂, X₄, ..., X_2k};
pod přirozeným rebrandingem X₁ → 1, X₃ → 2 atd., Permutace indukovaná na {1, 2, ..., k + 1} je Baxterova permutace.

Viz také

Výčty konkrétních permutačních tříd

Reference

^ Baxter, Glen (1964), „O pevných bodech složených funkcí dojíždění“, Proceedings of the American Mathematical Society, 15: 851–855, doi:10.2307/2034894.
^ Chung, F. R. K.; Graham, R. L.; Hoggatt, V. E., Jr.; Kleiman, M. (1978), "Počet Baxterových permutací" (PDF), Journal of Combinatorial Theory, Řada A, 24 (3): 382–394, doi:10.1016/0097-3165(78)90068-7, PAN 0491652.
^ Dulucq, S .; Guibert, O. (1998), „Baxterovy permutace“, Diskrétní matematika, 180 (1–3): 143–156, doi:10.1016 / S0012-365X (97) 00112-X, PAN 1603713.
^ Guibert, Olivier; Linusson, Svante (2000), „Doubly alternating Baxter permutations are Catalan“, Diskrétní matematika, 217 (1–3): 157–166, doi:10.1016 / S0012-365X (99) 00261-7, PAN 1766265.
^ Giraudo, Samuele (2011), „Algebraické a kombinatorické struktury na Baxterových permutacích“, 23. mezinárodní konference o formálních výkonových řadách a algebraické kombinatorice (FPSAC 2011), Diskrétní matematika. Teor. Comput. Sci. Proc., AO, Doc. Diskrétní matematika. Teor. Comput. Sci., Nancy, str. 387–398, arXiv:1011.4288, Bibcode:2010arXiv1011.4288G, PAN 2820726.
^ Bonichon, Nicolas; Bousquet-Mélou, Mireille; Fusy, Éric (říjen 2009), „Baxterovy permutace a rovinné bipolární orientace“, Seminář Lotharingien de Combinatoire, 61A, Umění. B61Ah, 29pp, arXiv:0805.4180, Bibcode:2008arXiv0805.4180B, PAN 2734180.
^ Korn, M. (2004), Geometrické a algebraické vlastnosti polyomino obkladů, Ph.D. teze, Massachusetts Institute of Technology.
^ Ackerman, Eyal; Barequet, Gill; Pinter, Ron Y. (2006), „A bijection between permutations and floorplans, and its applications“, Diskrétní aplikovaná matematika, 154 (12): 1674–1684, doi:10.1016 / j.dam.2006.03.018, PAN 2233287.

externí odkazy

OEIS posloupnost A001181 (počet Baxterových permutací délky n)

[1] Baxter, Glen (1964), „O pevných bodech složených funkcí dojíždění“, Proceedings of the American Mathematical Society, 15: 851–855, doi:10.2307/2034894.

[2] Chung, F. R. K.; Graham, R. L.; Hoggatt, V. E., Jr.; Kleiman, M. (1978), "Počet Baxterových permutací" (PDF), Journal of Combinatorial Theory, Řada A, 24 (3): 382–394, doi:10.1016/0097-3165(78)90068-7, PAN 0491652.

[3] Dulucq, S .; Guibert, O. (1998), „Baxterovy permutace“, Diskrétní matematika, 180 (1–3): 143–156, doi:10.1016 / S0012-365X (97) 00112-X, PAN 1603713.

[4] Guibert, Olivier; Linusson, Svante (2000), „Doubly alternating Baxter permutations are Catalan“, Diskrétní matematika, 217 (1–3): 157–166, doi:10.1016 / S0012-365X (99) 00261-7, PAN 1766265.

[5] Giraudo, Samuele (2011), „Algebraické a kombinatorické struktury na Baxterových permutacích“, 23. mezinárodní konference o formálních výkonových řadách a algebraické kombinatorice (FPSAC 2011), Diskrétní matematika. Teor. Comput. Sci. Proc., AO, Doc. Diskrétní matematika. Teor. Comput. Sci., Nancy, str. 387–398, arXiv:1011.4288, Bibcode:2010arXiv1011.4288G, PAN 2820726.

[6] Bonichon, Nicolas; Bousquet-Mélou, Mireille; Fusy, Éric (říjen 2009), „Baxterovy permutace a rovinné bipolární orientace“, Seminář Lotharingien de Combinatoire, 61A, Umění. B61Ah, 29pp, arXiv:0805.4180, Bibcode:2008arXiv0805.4180B, PAN 2734180.

[7] Korn, M. (2004), Geometrické a algebraické vlastnosti polyomino obkladů, Ph.D. teze, Massachusetts Institute of Technology.

[8] Ackerman, Eyal; Barequet, Gill; Pinter, Ron Y. (2006), „A bijection between permutations and floorplans, and its applications“, Diskrétní aplikovaná matematika, 154 (12): 1674–1684, doi:10.1016 / j.dam.2006.03.018, PAN 2233287.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]