Stirlingova permutace - Stirling permutation

v kombinatorická matematika, a Stirlingova permutace řádu k je permutace z multiset 1, 1, 2, 2, ..., k, k (se dvěma kopiemi každé hodnoty od 1 do k) s další vlastností, která pro každou hodnotu i v permutaci se objevují hodnoty mezi dvěma kopiemi i jsou větší než i. Například 15 Stirlingových permutací řádu tři je

1,1,2,2,3,3;   1,2,2,1,3,3;   2,2,1,1,3,3;
1,1,2,3,3,2;   1,2,2,3,3,1;   2,2,1,3,3,1;
1,1,3,3,2,2;   1,2,3,3,2,1;   2,2,3,3,1,1;
1,3,3,1,2,2;   1,3,3,2,2,1;   2,3,3,2,1,1;
3,3,1,1,2,2;   3,3,1,2,2,1;   3,3,2,2,1,1.

Počet Stirlingových permutací řádu k je dán dvojitý faktoriál (2k - 1) !!. Stirlingovy permutace byly zavedeny Gessel a Stanley (1978) aby se ukázalo, že určitá čísla (počty Stirlingových permutací s pevným počtem sestupů) jsou nezáporná. Jméno si vybrali kvůli spojení s jistým polynomy definované z Stirlingova čísla, které jsou zase pojmenovány po skotském matematikovi z 18. století James Stirling.[1]

Konstrukce Stirlingovy permutace z Prohlídka Euler a platan s okraji označenými podle stavební zakázky

Stirlingovy permutace lze použít k popisu sekvencí, pomocí kterých je možné sestrojit zakořeněné platan s k okraje přidáním listů jeden po druhém do stromu. Pokud jsou hrany očíslovány podle pořadí, ve kterém byly vloženy, pak posloupnost čísel v Prohlídka Euler stromu (vytvořeného zdvojnásobením okrajů stromu a procházením potomků každého uzlu zleva doprava) je Stirlingova permutace. Naopak každá Stirlingova permutace popisuje sekvenci konstrukce stromu, ve které je další hrana blíže ke kořenu od hrany označené i je ten, jehož dvojice hodnot nejblíže obklopuje dvojici i hodnoty v permutaci.[2]

Stirlingovy permutace byly zobecněny na permutace multisetu s více než dvěma kopiemi každé hodnoty.[3] Vědci také studovali počet Stirlingových permutací, které se vyhýbají určitým vzorům.[4]

Viz také

Reference

  1. ^ Gessel, Ira; Stanley, Richard P. (1978), "Stirlingovy polynomy", Journal of Combinatorial Theory, Řada A, 24 (1): 24–33, doi:10.1016/0097-3165(78)90042-0, PAN  0462961.
  2. ^ Janson, Svante (2008), „Plane rekurzivní stromy, Stirlingovy permutace a urnový model“, Páté kolokvium o matematice a informatice, Diskrétní matematika. Teor. Comput. Sci. Proc., AI, Doc. Diskrétní matematika. Teor. Comput. Sci., Nancy, str. 541–547, arXiv:0803.1129, Bibcode:2008arXiv0803.1129J, PAN  2508813.
  3. ^ Klingsberg, Paul; Schmalzried, Cynthia (1990), „Rodina konstruktivních bijekcí zahrnujících Stirlingovy permutace“, Sborník z dvacáté první jihovýchodní konference o kombinatorice, teorii grafů a práci na počítači (Boca Raton, Florida, 1990), Congressus Numerantium, 78, s. 11–15, PAN  1140465.
  4. ^ Kuba, Markus; Panholzer, Alois (2012), „Enumeration formulæ for pattern limited Stirling permutations“, Diskrétní matematika, 312 (21): 3179–3194, doi:10.1016 / j.disc.2012.07.011, PAN  2957938.