Formule des équerres, fractions continues

Formule des équerres, fractions continues

 Introduction

La formule des équerres donnant le nombre de tableaux de Young standard pour un diagramme de Young donné est un résultat essentiel de la combinatoire énumérative, et a ainsi été l’étude d’un grand nombre de travaux. Cette formule a été découverte par Frame, Robinson et Thrall [FRT+54] en 1954, et plus récemment, une formule similaire a été prouvée dans le cas des tableaux gauches par Naruse [Nar14] en 2014. Deux ans plus tard, Morales, Pak et Panova [MPP16] prouvent une q-généralisation de la formule de Naruse. De plus, en appliquant cette formule `a une certaine famille de tableaux gauches, ils obtiennent une relation non triviale entre permutations alternantes et chemins de Dyck pondérés. Ce chapitre s’intéresse aux différentes implications de cette relation, ainsi qu’`a une preuve bijective de la formule n’utilisant pas la formule des équerres généralisée. Cette preuve se base sur la fraction continue de la série exponentielle des nombres d’Euler, bien que la théorie des fractions continues étudiée par Flajolet [Fla80] s’applique principalement aux séries naturelles. Dans la Section II.2, nous introduisons les principales définitions et les résultats qui seront employés pendant ce chapitre. Nous introduisons les définitions des permutations alternantes et des nombres d’Euler. Nous continuons avec les chemins de Dyck, puis nous présentons les fonctions hypergéométriques ainsi que leur rˆole dans la théorie des fractions continues de Flajolet. Enfin nous faisons une présentation de la formule des équerres et ses applications. Dans la Section II.3, nous donnons une preuve du Théorème II.2.11 qui n’utilise pas la formule des équerres, puis nous 31 Formule des équerres, fractions continues  prouvons une formule similaire pour les permutations alternantes de taille paire. Dans la Section II.4, nous tentons d’étendre la formule aux permutations k-alternantes.

Définitions et résultats préliminaires 

Permutations alternantes et nombres d’Euler

Les permutations alternantes sont des permutations dont l’ensemble de descentes vérifie plusieurs propriétés naturelles. Définition II.2.1. Soit σ ∈ Sn, et i ∈ {1, . . . , n−1}. On décrit l’indice i comme une descente de σ si σi > σi+1. L’ensemble de descentes de σ, noté D(σ), est l’ensemble des indices de σ qui en sont des descentes. Définition II.2.2. Soit σ ∈ Sn. On définit σ comme alternante si D(σ) = {1, 3, . . . , 2 bn/2c − 1}, c’est-`a-dire σ1 > σ2 < σ3 > · · · . On note Altn l’ensemble des permutations alternantes de Sn. Similairement, σ est alternante renversée si D(σ) = {2, 4, . . . , 2 dn/2e − 2}, c’est-`a-dire σ1 < σ2 > σ3 < · · · . On note RevAltn l’ensemble des permutations alternantes renversées de Sn. Les permutations alternantes de Sn sont comptées par les nombres d’Euler En. Dans son article de synthèse [Sta10], Stanley donne quelques propriétés énumératives des permutations alternantes. En particulier, tan(z) = X n≥0 E2n+1 (2n + 1)!z 2n+1 , sec(z) = X n≥0 E2n (2n)!z 2n . (II.2.1) Ainsi, les nombres {E2n+1} sont parfois appelés nombres tangents, et {E2n} sont les nombres sécants. Stanley introduit aussi ce q-analogue des nombres d’Euler En(q) := X σ∈RevAltn q maj(σ−1 ) , E∗ n (q) := X σ∈Altn q maj(σ−1 ) , o`u maj(σ) := X i∈D(σ) i est l’indice majeur de σ. Notons que En(1) = E ∗ n (1) = En, et plus généralement on a la relation  E ∗ n (q) = q ( n 2)En(1/q). (II.2.2) Ces raffinements s’étendent aux q-analogues des fonctions trigonométriques tan et sec. Pour tout a ∈ N, soit (a)n = nY−1 i=0 (a + i) le symbole de Pochhammer, et (a; q)n = nY−1 i=0 (1 − aqi ) son q-analogue. Si sinq(z) :=X n≥0 (−1)n u 2n+1 (q; q)2n+1 , cosq(z) :=X n≥0 (−1)n u 2n (q; q)2n , sin∗ q (z) :=X n≥0 (−1)n q ( 2n+1 2 ) u 2n+1 (q; q)2n+1 , cos∗ q (z) :=X n≥0 (−1)n q ( 2n 2 ) u 2n (q; q)2n , alors, avec le Théorème 2.1 de [Sta10], on a X n≥0 u n (q; q)n En(q) = sinq(z) cosq(z) + 1 cosq(z) := tanq(z) + secq(z), X n≥0 u n (q; q)n E ∗ n (q) = sin∗ q (z) cos∗ q (z) + 1 cos∗ q (z) := tan∗ q (z) + sec∗ q (z). De plus, remarquons les identités suivantes, mettant en relation les variantes de cos et sin cos∗ q (x) = cos1/q(−x/q), sin∗ q (x) = sin1/q(−x/q). Remarque Avec (II.2.2), on a directement que tan∗ q = tanq. Cette égalité résulte aussi d’une simple bijection entre RevAltn et Altn conservant maj(σ −1 ) quand n est impair : soit σ ∈ Altn, on définit σ 0 par σ 0 (i) = n − σ(n − i). Alors σ 0 ∈ RevAltn, et maj(σ −1 ) = maj(σ 0−1 ).

Chemins de Dyck

Pour comprendre la relation entre les chemins de Dyck et les permutations alternantes, il est important de connaitre l’écriture de la fonction génératrice des chemins de Dyck sous forme d’une fraction continue.   Définition II.2.3. Un chemin de Dyck de longueur 2n est un chemin dans le quart de plan supérieur droit dont les pas sont soit (1, 1), soit (1, −1), le chemin commen¸cant en (0, 0) et finissant en (2n, 0). On note Dn l’ensemble de ces chemins. Nous choisissons de représenter les chemins de Dyck par la suite des hauteurs atteintes par le chemin plutˆot que par la suite de ses pas. Soit (h0, h1, . . . , h2n) ∈ Dn, tel que h0 = h2n = 0, et pour tout i, hi ≥ 0 et |hi − hi+1| = 1. Ainsi, hi est la hauteur que le chemin atteint après i pas. Par la suite dans ce chapitre, afin de représenter les fractions continues, nous utiliserons la notation suivante a0 b0 − a1 b1 − a2 b2 − · · · = a0 b0 − a1 b1 − a2 b2 − . . . . Le lemme suivant est un corollaire originaire des résultats de Flajolet sur les fractions continues dans [Fla80].