Permutation de Stirling

En mathématiques, et plus précisément en combinatoire, une permutation de Stirling d'ordre k est une permutation du multiensemble 1, 1, 2, 2,..., k, k (avec deux occurrences de chaque entier de 1 à k) possédant la propriété supplémentaire que, pour chaque entier i entre 1 et k, toute valeur comprise entre les deux occurrences de i est supérieure à i. Par exemple, les 15 permutations de Stirling d'ordre trois sont

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.

Le nombre de permutations de Stirling d'ordre k est la double factorielle ${\displaystyle (2k-1)!!}$.

Les permutations de Stirling ont été introduites par Gessel et Stanley^[1] afin de démontrer que certains nombres qui apparaissaient comme des coefficients dans des expressions rationnelles impliquant des nombres de Stirling sont positifs ou nuls. Plus précisément, soit la famille de nombres ${\textstyle \left\langle \!\left\langle {n \atop k}\right\rangle \!\right\rangle }$ être défini pour n et k entiers naturels par

${\displaystyle \sum _{m=0}^{\infty }\left\{{n+m \atop m}\right\}x^{m}={\frac {\sum _{k=0}^{n}\left\langle \!\left\langle {n \atop k}\right\rangle \!\right\rangle x^{k+1}}{(1-x)^{2n+1}}}}$,

où les ${\displaystyle \left\{{n \atop k}\right\}}$ sont les nombres de Stirling de seconde espèce. Gessel et Stanley ont démontré que ${\textstyle \left\langle \!\left\langle {n \atop k}\right\rangle \!\right\rangle }$ est le nombre de permutations de Stirling d'ordre ${\displaystyle n}$ qui ont exactement ${\displaystyle k}$ montées^{[n 1]}. C'est ce lien avec les nombres de Stirling qui explique le nom « permutations de Stirling ». Par ailleurs, les nombres ${\textstyle \left\langle \!\left\langle {n \atop k}\right\rangle \!\right\rangle }$ sont appelés nombres eulériens du second ordre.

Les permutations de Stirling permettent de paramétrer les suites décrivant la construction d'un arbre planaire enraciné à k arêtes en ajoutant les feuilles une à une. En effet, si les arêtes sont numérotées selon leur ordre d'insertion, la suite de nombres d'un parcours eulérien de l'arbre (obtenu en doublant les arêtes et en parcourant les fils de chaque nœud de gauche à droite) est une permutation de Stirling. Inversement, toute permutation de Stirling décrit une suite de construction d'un arbre : pour une arête étiquetée i, l'arête qui la relie à la racine a l'indice dont les deux occurrences entourent celles de i au plus près dans la permutation^[2]. Par exemple, pour la permutation 126624413355 ci-dessus, l'arête 6 est reliée à l'arête 2, laquelle est reliée à l'arête 1, laquelle est liée à la racine (car les 1 ne sont pas entourés d'autres indices).

Les permutations de Stirling ont été généralisées aux permutations d'un multiensemble comportant plus de deux copies de chaque valeur^[3]. Une autre ligne de recherche est l'étude des permutations de Stirling qui évitent certains motifs^[4].