Permutació de Stirling
En combinatòria, una permutació de Stirling d'orde k és una permutació del multiconjunto 1, 1, 2, 2, ..., k, k (en dos còpies de cada valor d'1 a k) en la propietat afegida de que, per cada valor i que apareix en la permutació, els valors entre les dos còpies de i són majors que i. Per eixemple, les 15 permutació de Stirling d'orde 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 número de permutació de Stirling d'orde k està donat pel doble factorial (2k − 1)!!. Les permutació de Stirling varen ser introduïdes per Gessel y Stanley (1978) per a demostrar que certs números (els números de les permutació de Stirling en un número fix de descendents) són no-negatius. Varen elegir el nom a causa d'una conexió a certs polinomis definits pels números de Stirling, que es varen cridar aixina despuix de el XVII en honor al matemàtic escocés James Stirling.[1]
Les permutació de Stirling poden usar-se per a descriure les seqüències per les quals és possible construir un arbre pla arraïlat en k brodes afegint fulls una per una a l'arbre. Si les vores estan numerades per l'orde en que varen ser insertats, llavors la seqüència de números en una torre de Euler de l'arbre (formada en doblar les vores de l'arbre i travessar als descendents de cada nodo d'esquerra a dreta) és una permutació de Stirling. Pel contrari, cada permutació de Stirling descriu una seqüència de construcció d'arbre, en la qual la següent vora més propenc a la raïl d'una vora ordenada i és aquell el parell del qual de valors rodeja més estretament al parell de valors i en la permutació.
Les permutació de Stirling s'han generalisat a les permutació d'un multiconjunto en més de dos còpies de cada valor. Els investigadors també han estudiat el número de permutació de Stirling que eviten certs patrons.[2]
Vore també
[editar | editar còdic]- Emparejamiento de Langford, un atre tipo de permutació del mateix multiconjunto.
Referències
[editar | editar còdic]- ↑ (1978).«Stirling polynomials».Journal of Combinatorial Theory.24(1)
- 24–33.doi:10.1016/0097-3165(78)90042-0..
- ↑ (2012).«Enumeration formulæ for pattern restricted Stirling permutations».Discrete Mathematics.312(21)
- 3179–3194.doi:10.1016/j.disc.2012.07.011..
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Permutación de Stirling» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.