Vés al contingut

Permutació de Stirling

De la Viquipèdia, l'enciclopèdia lliure
Construcció d'una permutació de Stirling a partir d'una torre d'Euler d'un arbre pla amb les seves arestes per ordre de construcció

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]
  1. 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.
  2. 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.
  3. 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.
  4. 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]