Permutació de Stirling
En combinatòria, una permutació de Stirling d'ordre k és una permutació del multiconjunt 1, 1, 2, 2, ..., k, k (amb dues còpies de cada valor d'1 a k) amb la propietat afegida que, per cada valor i que apareix a la permutació, els valors entre les dues còpies d'i són més grans que i. Per exemple, les 15 permutacions de Stirling d'ordre tres són:
- 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.
El nombre de permutacions de Stirling d'ordre k està donat pel doble factorial (2k - 1) !!. Les permutacions de Stirling van ser introduïdes per Gessel & Stanley (1978) per a demostrar que certs nombres (els nombres de les permutacions de Stirling amb un nombre fix de descendents) són no-negatius. Van triar el nom a causa d'una connexió a certs polinomis definits pels nombres de Stirling, que es van anomenar així després del segle xvii en honor del matemàtic escocès James Stirling.[1]
Les permutacions de Stirling poden usar-se per a descriure les seqüències per les quals és possible construir un arbre pla arrelat amb k vores afegint fulles una per una a l'arbre. Si les vores estan numerades per l'ordre en què van ser inserides, llavors la seqüència de nombres en una torre d'Euler de l'arbre (formada al doblegar les vores de l'arbre i travessar als descendents de cada node d'esquerra a dreta) és una permutació de Stirling. Per contra, cada permutació de Stirling descriu una seqüència de construcció d'arbre, en la qual la següent vora més propera a l'arrel d'una vora ordenada i és aquella la qual el parell de valors envolta més estretament al parell de valors i en la permutació.[2]
Les permutacions de Stirling s'han generalitzat a les permutacions d'un multiconjunt amb més de dues còpies de cada valor.[3] Els investigadors també han estudiat el nombre de permutacions de Stirling que eviten certs patrons.[4]
Referències
modifica- ↑ Gessel, Ira; Stanley, Richard P «Stirling polynomials» (en angles). Journal of Combinatorial Theory, 24(1), 1978, pàg. 24–33. DOI: 10.1016/0097-3165(78)90042-0.
- ↑ Janson, Svante «Fifth Colloquium on Mathematics and Computer Science» (en anglès). Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2008, pàg. 541–547. arXiv: 0803.1129. Bibcode: 2008arXiv0803.1129J.
- ↑ Klingsberg, Paul; Schmalzried, Cynthia «Proceedings of the Twenty-first Southeastern Conference on Combinatorics, Graph Theory, and Computing» (en anglès). Congressus Numerantium [Boca Raton, Florida], 78, 1990, pàg. 11–15.
- ↑ Kuba, Markus; Panholzer, Alois «Enumeration formulæ for pattern restricted Stirling permutations» (en anglès). Discrete Mathematics, 312(21), 2012, pàg. 3179-3194. DOI: 10.1016/j.disc.2012.07.011.
Vegeu també
modifica- Aparellament de Langford, un altre tipus de permutació del mateix multiconjunt.