Unimodalité dans le triangle eulérien

La question de l’unimodalité des suites associées aux triangles arithmétiques trouve ses racines dans dans les travaux de Tanny et Zuker [TZ74, TZ76, TZ78] sur l’unimodalité des suites se trouvant sur les diagonales du triangle de Pascal. Plusieurs autres travaux ont traité la question de l’unimodalité des suites associées au triangle de Pascal. En 2015, Belbachir et Szalay [BS08] ont prouvé que les suites se trouvant sur n’importe quelle direction finie dans le triangle de Pascal sont unimodales. Le triangle de Pascal n’est pas le seul triangle arithmétique qui a été étudié, d’autres triangles comme les triangles de Stirling de première et deuxième espèce ont aussi été étudiés dans ce sens. Dans ce chapitre, nous nous intéressons aux suites associées aux différentes directions dans le triangle eulérien. Nous commençons dans le paragraphe 3.1 par une étude combinatoire de ces suites en donnant l’interprétation combinatoire ainsi que la relation de récurrence des suites associées à la direction (1, 1) dans le triangle eulérien, puis on généralise ce résultat pour les suites associées à la direction (1, t), où t est un entier positif. Nous démontrons ensuite dans le paragraphe 3.2 que les suites se trouvant sur n’importe quelle direction finie sont log-concaves et donc unimodales. Pour aboutir à ce résultat, nous passons par trois étapes : nous démontrons dans un premier temps que les suites associées à la direction (1, 1) dans le triangle eulérien sont log-concaves et donc unimodales. Puis, nous généralisons ce résultat aux directions (1, t) dans le triangle eulérien, où t est un entier positif. Enfin, nous démontrons que les suites associées aux directions (r, q), où r est un entier positif ou nul et q est un entier, tel que r + q > 0, sont log-concaves et donc unimodales. Ce chapitre est un travail en commun avec Hacène Belbachir et Assia Tebtoub suite à un séjour d’Assia à l’université de Marne-la-Vallée. 107 Unimodalité dans le triangle eulérien Chapitre 3. Unimodalité dans le triangle eulérien 3.1 Combinatoire des suites associées aux différentes directions 3.1.1 Nombres eulériens avec succession d’ordre 2 Dans ce paragraphe, on s’intéresse aux suites se trouvant sur les diagonales principales du le triangle eulérien. En d’autres mots, ce sont les suites associées à la direction (1, 1) du triangle eulérien (cf. table 3.1.1). On donne n\k 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 4 11 26 57 120 1 11 66 302 1191 1 26 302 2416 1 57 1191 1 120 1 Table 3.1.1 : Direction (1, 1) dans le triangle eulérien. une interprétation combinatoire de ces suites en terme de permutations et de chemins nord-est étiquetés, puis on présente la relation de récurrence associée à ces suites. Définition 3.1.1. Soit σ = σ1σ2 · · · σn une permutation de taille n et soit i un entier positif, où 1 6 i 6 n−2. On dit que la position i est une 2-descente de σ si σi > σi+1 > σi+2. Définition 3.1.2. Soit S [2] n l’ensemble des permutations de taille n tel que le nombre de descentes dans chaque bloc maximal de descentes consécutives est pair. La permutation de taille n n’ayant pas de descentes est aussi dans S [2] n .

Exemple 3.1.3.

La permutation 753214986 à deux blocs maximaux de descentes consécutives. Le premier bloc 75321 comporte quatre descentes et le deuxième 986 en comporte deux. Chaque bloc a un nombre pair de descentes. La permutation 753214986 appartient donc à l’ensemble S [2] 9 . En revanche, la permutation 431975286 a trois blocs maximaux de descentes consécutives. Le premier bloc 431 comporte deux descentes, le deuxième 9752 108 3.1 Combinatoire des suites associées aux différentes directions en comporte trois et le troisième 86 comporte une seule descente. Le nombre de descentes dans le deuxième et troisième bloc n’est pas un nombre pair. La permutation 431975286 n’appartient donc pas à l’ensemble S [2] 9 . Exemple 3.1.4. Les éléments de S [2] 6 ayant deux 2-descentes disjointes sont 165432, 265431, 321654, 365421, 421653, 431652, 432651, 465321, 521643, 531642, 532641, 541632, 542631, 543216, 543621, 564321, 621543, 631542, 632541, 641532, 642531, 643215, 643521, 651432, 652431, 653214, 653421, 654213, 654312. Définition 3.1.5. Soient n et k deux entiers positifs vérifiant 0 6 2k < n. On notera E [2](n, k) l’ensemble des permutations de S [2] n ayant k 2-descentes disjointes tel que par récurrence sur n : • soit σ|{1,…,n−2} ∈ E[2](n − 2, k − 1); • ou σ|{1,…,n−1} ∈ E[2](n − 1, k). Le nombre eulérien avec succession d’ordre 2, noté E [2](n, k), est le cardinal de E [2](n, k). Exemple 3.1.6. Les éléments de E [2](6, 2) sont 165432, 321654, 365421, 431652, 543216, 543621, 564321, 651432, 653214, 653421, 654312. Remarque 3.1.7. Entre autres, la permutation 654213 qui appartient à S [2] 6 n’est pas dans E [2](6, 2) puisque la permutation 654213|{1,2,3,4,5} = 54213 comporte un nombre impair de descentes (elle n’est donc pas dans E [2](5, 2)) et la permutation 654213|{1,2,3,4} = 4213 n’est pas dans E [2](4, 1), car la permutation 4213|{1,2,3} = 213 comporte un nombre impair de descentes (elle n’est donc pas dans E [2](3, 1)), la permutation 4213|{1,2} = 21 a aussi un nombre impair de descentes (elle n’est donc pas dans E [2](2, 0)). 

Nombres eulériens avec succession d’ordre t + 1 Dans ce paragraphe, on s’intéresse aux suites se trouvant sur les diagonales de directions (1, t) dans le triangle eulérien, où t est un entier supérieur à 1. On donne une interprétation combinatoire de ces suites en termes de permutations et de chemins nord-est étiquetés, et on présente la relation de récurrence de ces suites. Les suites de direction (1, 2) dans le triangle eulérien sont illustrées dans la table 1.3.2. 116 3.1 Combinatoire des suites associées aux différentes directions Définition 3.1.25. Soit σ = σ1σ2 · · · σn une permutation de taille n et soient i et t deux entiers positifs, tel que t > 1 et 1 6 i 6 n − t − 1. On dit que la position i est une (t + 1)-descente de σ si σi > σi+1 > · · · > σi+t+1. Définition 3.1.26. Soit S [t+1] n l’ensemble des permutations de taille n tel que le nombre de descentes dans chaque bloc maximal de descentes consécutives est un multiple de (t+1). La permutation de taille n n’ayant pas de descentes est aussi dans S [t+1] n . Exemple 3.1.27. La permutation 752184319 à deux blocs maximaux de descentes consécutives. Le premier bloc 7521 comporte trois descentes et le deuxième 8431 en comporte aussi trois. Chaque bloc a un nombre multiple de trois de descentes. La permutation 752184319 appartient donc à l’ensemble S [3] 9 . En revanche, la permutation 976532184 à deux blocs maximaux de descentes consécutives. Le premier bloc 9765321 comporte six descentes et le deuxième 81 comporte une seule descente. Le nombre de descentes dans le deuxième bloc n’est pas un nombre multiple de trois. La permutation 976532184 n’appartient donc pas à l’ensemble S [3] 9 . Exemple 3.1.28. Les éléments de S [3] 6 ayant une 3-descentes sont 126543, 136542, 146532, 154326, 156432, 164325, 165324, 165423, 236541, 246531, 254316, 256431, 264315, 265314, 265413, 346521, 354216, 356421, 364215, 365214, 365412, 432156, 453216, 456321, 463215, 465213, 465312, 532146, 542136, 543126, 563214, 564213, 564312, 632145, 642135 643125, 652134, 653124, 654123. Définition 3.1.29. Soient n et k deux entiers positifs vérifiant 0 6 (t+1)k < n. On notera E [t+1](n, k) l’ensemble des permutations de S [t+1] n ayant k t+ 1- descentes disjointes tel que par récurrence sur n : • soit σ|{1,…,n−t} ∈ E[t+1](n − t − 1, k − 1); • ou σ|{1,…,n−1} ∈ E[t+1](n − 1, k). Le nombre eulérien avec succession d’ordre (t + 1), noté E [t+1](n, k), est le cardinal de E [t+1](n, k). Exemple 3.1.30. Les éléments de E [3](6, 1) sont 126543, 154326, 156432, 165423, 432156, 453216, 463215, 456321, 543126, 564312, 654123. 117 Chapitre 3. Unimodalité dans le triangle eulérien Les nombres eulériens avec succession d’ordre (t + 1) vérifient la relation de récurrence suivante : Théorème 3.1.31. Soient n, k et t des entiers positifs, avec n > 1, 0 6 k < n et t > 1. On a : E [t+1](n, k) =    1 si k = 0 et 0 6 n < 2, (k + 1)E [t+1](n − 1, k) + (n − k(t + 1))E [t+1](n − t − 1, k − 1) si n > 2 et 0 6 (t + 1)k < n, 0 sinon. (3.8) Démonstration. Pour obtenir une permutation de taille n ayant k (t + 1)- descentes à partir d’une permutation σ de E [t+1](n−1, k), on place n soit à la fin de σ, soit entre les deux premiers éléments qui forment une des k (t + 1)- descentes de σ. Dans ce cas, on a k+1 positions possibles pour placer n. Pour obtenir une permutation de taille n ayant k (t + 1)-descentes à partir d’une permutation σ de E [t+1](n−t−1, k−1), on place n, n−1, . . . , n−t qui forment une (t)-descente dans toutes les positions sauf celles qui forment les k−1 (t+1)- descentes de σ, et on a (n − t − 1) − (t + 1)(k − 1) = n − k(t + 1) positions possibles pour le faire. Les permutations obtenues à partir des permutations de E [t+1](n − 1, k) et E [t+1](n − t − 1, k − 1) sont toujours différentes. En effet, les premières sont obtenues en posant n soit à la fin de σ, soit entre les deux premières positions qui forment une des k (t + 1)-descentes de σ et donc n, n − 1, . . . , n − t ne forment jamais de t-descente. Et comme on prend en compte toutes les positions possibles, on obtient tous les éléments de E [t+1](n, k).