Un autre q-analogue des nombres d’Euler

G.-N. Han^{1}, A. Randrianarivony^{2} et J. Zeng^{3}

1IRMA, CNRS et Université Louis-Pasteur (Strasbourg 1), France 2 Faculté des Sciences, Université d’Antananarivo, Madagascar

3Institut Girard Desargues, Université Claude Bernard (Lyon 1), France

Dedicated to G. Andrews on the occasion of his 60th birthday

Résumé

The ordinary generating functions of the secant and tangent numbers have very simple continued fraction expansions. However, the classical q-secant and q-tangent numbers do not give a natural q-analogue of these continued fractions. In this paper, we introduce a different qanalogue of Euler numbers using q-difference operator and show that their generating functions have simple continued fraction expansions. Furthermore, by establishing an explicit bijection between some Motzkin paths and (k, r)-multipermutations we derive combinatorial interpretations for these q-numbers. Finally the allied q-Euler median numbers are also studied.

1 Introduction

Les nombres d’Euler E_{n} (n ≥ 0) sont classiquement définis comme les coefficients apparaissant dans le développement de Taylor suivant :

∑_{n≥0} E_{n} \frac{t^{n}}{n!} = 1 + t + \frac{t^{2}}{2!} + 2 \frac{t^{3}}{3!} + 5 \frac{t^{4}}{4!} + … = \frac{1}{cos t} + tan t.  (1)

Ainsi les nombres E_{2n} et E_{2n+1} sont appelés aussi nombres sécants et nombres tangents respectivement. En remplaçant cos t et tan t par leurs q-analogues dans (1) on obtient alors le q-analogue classique des nombres d’Euler comme les coefficients correspondants dans le développement en q-séries de Taylor. Ces q-nombres d’Euler généralisent effectivement certains aspects arithmétiques et combinatoires des nombres d’Euler [2, 3, 10], mais ils ne fournissent pas de q-analogues simples pour deux S-fractions continues remarquables de leurs séries génératrices ordinaires [8] :

∑_{n≥0} E_{2n}t^{n} = 1 + t + 5 t^{2} + 61 t^{3} + … = \frac{1}{1 − \frac{1^{2} t}{1 − \frac{2^{2} t}{1 − \frac{3^{2} t}{...}}}} ,  (2)

∑_{n≥0} E_{2n+1}t^{n} = 1 + 2 t + 16 t^{2} + 272 t^{3} + … = \frac{1}{1 − \frac{1 · 2 t}{1 − \frac{2 · 3 t}{1 − \frac{3 · 4 t}{...}}}} .(3)

Une autre suite de nombres liés intimement aux nombres sécants et tangents est la suite des nombres d’Euler médians L_{n}, qui sont les nombres apparaissant au milieu du triangle de Seidel-Arnold [4, 7]:

1

1 ← 0
0 → 1 → 1
2 ← 2 ← 1 ← 0
0 → 2 → 4 → 5 → 5
16 ← 16 ← 14 ← 10 ← 5 ← 0
0 → 16 → 32 → 46 → 56 → 61 → 61
. . . . . .

dont la construction est analogue à celle du triangle de Pascal pour les coefficients binomiaux. Par exemple, on trouve les premières valeurs de ces nombres : L_{0} = 1, L_{1} = 1, L_{2} = 4, L_{3} = 46, ainsi que celles des nombres d’Euler : E_{0} = E_{2} = 1, E_{4} = 5, E_{6} = 61 et E_{1} = 1, E_{3} = 2, E_{5} = 16. Dumont [7] a montré que la fonction génératrice des nombres L_{n} a aussi un développement simple en S-fraction continue :

∑_{n≥0} L_{n}t^{n} = 1+t+4 t^{2} +46 t^{3} +1024 t^{4} +… = \frac{1}{1 − \frac{1 · 1 t}{1 − \frac{1 · 3 t}{1 − \frac{2 · 5 t}{1 − \frac{2 · 7 t}{...}}}}} . (4)

Il s’avère [17, 18] qu’une telle formule pour une suite de nombres est généralement liée à une formule de type Gandhi de ces nombres. Plus précisément, soit α = (a, b, c, d) une suite d’entiers rationnels et P_{n}^{(α)}(x) (n ≥ 0) une suite de polynômes définis par

\{ \begin{matrix}P_{0}^{(α)}(x) = 1, \\ P_{n}^{(α)}(x) = (x + a) \{(x + b)P_{n−1}^{(α)}(x + c) − (x + d)P_{n−1}^{(α)}(x)\} . \end{matrix} (5)

Par la méthode de [17, 18], on obtient aisément le résultat suivant:

∑_{n≥0} P_{n}^{(α)}(x)t^{n} = \frac{1}{1 − \frac{(b − d)(x + a) t}{1 − \frac{c(x + b) t}{1 − \frac{(b − d + c)(x + a + c) t}{1 − \frac{2c(x + b + c) t}{1 − \frac{(b − d + 2c)(x + a + 2c) t}{1 − \frac{3c(x + b + 2c) t}{...}}}}}}} . (6)

D’où, par comparaison de leurs fractions continues, on déduit que

E_{2n+1} = P_{n}^{(1,2,2,1)}(1), E_{2n} = P_{n}^{(0,1,2,0)}(1), L_{n} = 4^{−n}P_{n}^{(0,2,4,−2)}(1). (7)

Par ailleurs, les polynômes P_{n}^{(α)}(x) interpolent les trois autres suites de nombres (R_{n}), (l_{n}) et (r_{n}) proposées dans [7, 18] par les ressemblances de leurs fractions continues à celles des nombres d’Euler médians:

R_{n} = 4^{−n}P_{n}^{(2,4,4,0)}(1), l_{n} = 2^{−n}P_{n}^{(0,1,2,−1)}(1), r_{n} = 2^{−n}P_{n}^{(1,2,2,0)}(1). (8)

Les premières valeurs de ces nombres sont : R_{0} = 1, R_{1} = 3, R_{2} = 24, R_{3} = 402, l_{0} = 1, l_{1} = 1, l_{2} = 3, l_{3} = 21 et r_{0} = 1, r_{1} = 2, r_{2} = 10, r_{3} = 98.

L’un des avantages d’une formule de type (5) est qu’elle ouvre une nouvelle voie pour des q-extensions en remplaçant la différence ordinaire par la q-différence. Ce qui a d’ailleurs été fructueux dans l’étude de q-nombres de Genocchi [13]. Le but de cet article est d’étudier le q-analogue des nombres plus haut dans cette optique.

Pour tout entier positif ou négatif de n, on définit son q-analogue [n] par

[n] : = [n]_{q} = \frac{1 − q^{n}}{1 − q} et [x, n]_{q} = xq^{n} + [n].  (9)

Pour n ≥ 0, on définit le q-analogue de (5) les polynômes P_{n}^{(α)}(x, q) par

\{ \begin{matrix}P_{0}^{(α)}(x, q) = 1, \\ P_{n}^{(α)}(x, q) = [x, a]_{q} \frac{[x, b]_{q}P_{n−1}^{(α)}([x, c]_{q}, q) − [x, d]_{q}P_{n−1}^{(α)}(x, q)}{1 + (q − 1)x}. \end{matrix}  (10)

Pour des entiers positifs r ≥ l ≥ 0, on note [12, p.73] l’ensemble des entiers compris entre l et r par

[l..r] = {l, l + 1, …, r − 1, r}.  (11)

Définition 1 Soient k et r deux entiers naturels. Une (k, r)-multipermu-tation ou (k, r)-MP de [1..n] est un réarrangement du mot 0^{k}1^{r}2^{r} ⋯ n^{r} tel qu’entre deux lettres identiques, il n’y a aucune lettre plus petite. On note S_{n}^{(k,r)} l’ensemble des (k, r)-multipermutations de [1..n].

Remarque: Si k = 0, une (k, r)-MP se réduit à une r-multipermutation de [1..n], qui a été introduite par Gessel et Stanley [11] et poursuivie par Park [15]. Si r = 1, une (k, r)-MP de [1..n] s’appelle simplement k-permuta-tion de [1..n]. On s’aperçoit assez facilement que le cardinal de S_{n}^{(k,r)} a une

formule explicite :

| S_{n}^{(k,r)} | = (k + 1) · (k + 1 + r) ⋯ (k + 1 + r(n − 1)).

Il en résulte que

∑_{n≥0} | S_{n}^{(k,r)} |\frac{x^{n}}{n!} = (1 − rx)^{−(k+1)/r},

ainsi (voir [8]) que

∑_{n≥0} | S_{n}^{(k,r)} |t^{n} = \frac{1}{1 − (k + 1)t − \frac{r(k + 1)t^{2}}{1 − (k + 1 + 2r)t − \frac{2r(k + 1 + r)t^{2}}{\frac{...}{1 − b_{i}t − \frac{λ_{i}t^{2}}{...}}}}} (12)

où b_{i} = k + 1 + 2ir et λ_{i} = r(i + 1)(k + 1 + ir) pour i ≥ 0.

En vertu de la théorie combinatoire des J-fractions continues [8], on en déduit l’existence d’une bijection de S_{n}^{(k,r)} sur un certain ensemble de chemins de Motzkin valués (voir Section 3). Nous allons construire une telle bijection Θ_{n} en généralisant la bijection classique de Françon-Viennot-Flajolet (voir [8]), qui correspond au cas où r = 1.

Cet article est organisé comme suit. Dans la section 2 on calcule d’abord la série génératrice ordinaire de P_{n}^{(α)}(x, q) (n ≥ 0) et puis définit des qextensions des nombres et des polynômes introduits plus haut. La section 3 est consacrée à la construction de la bijection Θ_{n}. En appliquant la théorie combinatoire générale des fractions continues, on en déduit des interprétations combinatoires de ces polynômes dans la section 4. Enfin on termine l’article par des liens avec les nombres de Genocchi.

2 Fractions continues et définitions

Posons Δ_{q}x = 1 + (q − 1)x et P (x, t) = ∑_{n≥0} P_{n}^{(α)}(x, q)t^{n}. La récurrence (10) equivaut alors à l’équation fonctionnelle suivante :

P (x, t) = \frac{Δ_{q}x}{Δ_{q}x + [x, a]_{q}[x, d]_{q}t} + \frac{[x, a]_{q}[x, b]_{q}t}{Δ_{q}x + [x, a]_{q}[x, d]_{q}t} · P ([x, c]_{q}, t). (13)

Comme 1 + (q − 1)[x, c]_{q} = q^{c}Δ_{q}x et [[x, c]_{q}, a]_{q} = [x, a + c]_{q}, on en déduit par itération le résultat suivant.

Proposition 1 On a

∑_{n≥0} P_{n}^{(α)}(x, q)t^{n} = ∑_{n≥0} \frac{q^{nc}t^{n}Δ_{q}x ∏_{i=0}^{n−1}[x, a + ic]_{q}[x, b + ic]_{q}}{∏_{i=0}^{n}\{q^{ic}Δ_{q}x + [x, a + ic]_{q}[x, d + ic]_{q}t\}}.  (14)

Comme dans [13, 17, 18], on obtient le développement en fraction continue de P (x, t) en appliquant une formule de Wall [20] à (13).

Théorème 1 La fonction génératrice ordinaire des polynômes P_{n}^{(α)}(x, q) admet le développement en S-fraction continue suivant :

∑_{n≥0} P_{n}^{(α)}(x, q)t^{n} = \frac{1}{1 − \frac{q^{d}[b − d][x, a]_{q} t}{1 − \frac{q^{a}[c][x, b]_{q} t}{1 − \frac{q^{d}[b − d + c][x, a + c]_{q} t}{1 − \frac{q^{a}[2c][x, b + c]_{q} t}{1 − \frac{q^{d}[b − d + 2c][x, a + 2c]_{q} t}{1 − \frac{q^{a}[3c][x, b + 2c]_{q} t}{...}}}}}}} .

Remarque: Le théorème ci-dessus a été découvert à l’aide de Maple. En effet, la formule de Wall (voir [13, 17, 18]) fournit une relation de récurrence pour les coefficients de la S-fraction continue, qui permet de calculer les premiers coefficients rapidement à l’aide de Maple dans des cas particuliers.

Pour des entiers positifs k et r, posons

E_{n}^{(k,r)}(x, q) = q^{−(k−1)n}P_{n}^{(k−1,k−1+r,2r,k−1)}(x, q).  (15)

Il vient du théorème 1 que

∑_{n≥0} E_{n}^{(k,r)}(x, q)t^{n} = \frac{1}{1 − \frac{[r][x, k − 1]_{q} t}{1 − \frac{[2r][x, k − 1 + r]_{q} t}{1 − \frac{[3r][x, k − 1 + 2r]_{q} t}{1 − \frac{[4r][x, k − 1 + 3r]_{q} t}{...}}}}} . (16)

Rappelons que les nombres d’Euler d’ordre k sont définis par

∑_{n≥0} E_{2n}^{(k)} \frac{t^{2n}}{(2n)!} = \frac{1}{(cos t)^{k}} .

Comparant avec le développement en S-fraction continue de la série génératrice de E_{2n}^{(k)} (voir [8]), on voit que

E_{2n}^{(k)} = E_{n}^{(k,1)}(1, 1).

Il est donc naturel de définir E_{n}^{(k,r)}(x, q) comme les q-polynômes d’Euler d’ordre k. En vertu de (7), on définit les q-polynômes sécants S_{n}(x, q) et les q-polynômes tangents T_{n}(x, q) par

S_{n}(x, q) = E_{n}^{(1,1)}(x, q), T_{n}(x, q) = E_{n}^{(2,1)}(x, q).  (17)

On a donc les formules suivantes :

∑_{n≥0} S_{n}(x, q)t^{n} = 1 + x t + x([2] + [3]x) t^{2} + …
= \frac{1}{1 − \frac{[1]x t}{1 − \frac{[2][x, 1]_{q} t}{1 − \frac{[3][x, 2]_{q} t}{1 − \frac{[4][x, 3]_{q} t}{...}}}}} ,  (18)

∑_{n≥0} T_{n}(x, q)t^{n} = 1 + (1 + qx) t + (1 + qx)([2] + [3](1 + qx)) t^{3} + …
= \frac{1}{1 − \frac{[1][x, 1]_{q} t}{1 − \frac{[2][x, 2]_{q} t}{1 − \frac{[3][x, 3]_{q} t}{1 − \frac{[4][x, 4]_{q} t}{...}}}}} .  (19)

A leurs tours, en définissant les q-nombres sécants E_{2n}(q) = S_{n}(1, q) et les q-nombres tangents E_{2n+1}(q) = T_{n}(1, q) (n ≥ 0), on obtient les qanalogues de (2) et (3) comme suit :

∑_{n≥0} E_{2n}(q)t^{n} = 1 + t + (2 + 2q + q^{2})t^{2} + (5 + 12q + 16q^{2} + 14q^{3}
+9q^{4} + 4q^{5} + q^{6})t^{3} + …
= \frac{1}{1 − \frac{[1]^{2} t}{1 − \frac{[2]^{2} t}{1 − \frac{[3]^{2} t}{1 − \frac{[4]^{2} t}{...}}}}} ,  (20)

∑_{n≥0} E_{2n+1}(q)t^{n} = 1 + (1 + q) t + 2(2 + q + q^{2})(1 + q)^{2} t^{2} + (5 + 6q
+9q^{2} + 6q^{3} + 5q^{4} + 2q^{5} + q^{6})(1 + q)^{3} t^{3} …
= \frac{1}{1 − \frac{[1][2] t}{1 − \frac{[2][3] t}{1 − \frac{[3][4] t}{1 − \frac{[4][5] t}{...}}}}} .  (21)

Le résultat suivant est comparable avec ceux obtenus par Andrews, Foata et Gessel [2, 3, 10] pour les nombres q-secants et q-tangents classiques.

Proposition 2 Pour n ≥ 0, on a E_{2n}(q) ≡ 1 mod (1 + q)^{2} et E_{2n+1}(q) = (1 + q)^{n}Q_{n}(q), où Q_{n}(q) est un polynôme à coefficients entiers positifs de q tel que Q_{n}(−1) = (−1)^{n}n!.

Démonstration: Comme dans [9, 14], on obtient de (20) que

∑_{n≥0} E_{2n}(q)t^{n} ≡ \frac{1}{1 − t} (mod (1 + q)^{2}).

D’où E_{2n}(q) ≡ 1 mod (1 + q)^{2}. Posons E_{2n+1}(q) = (1 + q)^{n}Q_{n}(q). Comme [2n]_{q}/(1 + q) = [n]_{q^{2}}, il vient de (21) que

∑_{n≥0} Q_{n}(q)t^{n} = \frac{1}{1 − \frac{[1][1]_{q^{2}} t}{1 − \frac{[1]_{q^{2}}[3] t}{1 − \frac{[3][2]_{q^{2}} t}{1 − \frac{[2]_{q^{2}}[5] t}{...}}}}} .  (22)

Donc Q_{n}(q) est un polynôme de q à coefficients entiers positifs. Comme [2n + 1]_{−1} = 1 et [n]_{1} = n, en posant q = −1 dans (22), on obtient

∑_{n≥0} Q_{n}(−1)t^{n} = \frac{1}{1 + \frac{1 t}{1 + \frac{1 t}{1 + \frac{2 t}{1 + \frac{2 t}{1 + \frac{3 t}{1 + \frac{3 t}{...}}}}}}} .  (23)

D’où Q_{n}(−1) = (−1)^{n}n!.

Posons maintenant

L_{n}^{(k,r)}(x, q) = (q^{k−r}[2r]_{q})^{−n}P_{n}^{(k,k+r,2r,k−r)}(x, q).  (24)

Comme [2nr]/[2r] = [n]_{q^{2r}}, on déduit du théorème 1 que

∑_{n≥0} L_{n}^{(k,r)}(x, q)t^{n} = 1 + [x, k] t + [x, k]([x, k] + q^{r}[x, k + r]) t^{2} + …
= \frac{1}{1 − \frac{[x, k]_{q} t}{1 − \frac{q^{r}[x, k + r]_{q} t}{1 − \frac{[2]_{q^{2r}}[x, k + 2r]_{q} t}{1 − \frac{q^{r}[2]_{q^{2r}}[x, k + 3r]_{q} t}{1 − \frac{[3]_{q^{2r}}[x, k + 4r]_{q} t}{...}}}}}} .  (25)

En vertu des relations (7) et (8), on appelle L_{n}^{(k,r)}(x, q) les q-polynômes d’Euler médians généraux. En définissant les deux types de q-nombres d’Euler médians L_{n}(q) = L_{n}^{(0,2)}(1, q) et R_{n}(q) = L_{n}^{(2,2)}(1, q), on obtient

∑_{n≥0} L_{n}(q)t^{n} = 1 + t + [4] t^{2} + (1 + 3q^{2} + 4q^{3} + 6q^{4} + 5q^{5} + 7q^{6}
+6q^{7} + 5q^{8} + 3q^{9} + 3q^{10} + 2q^{11} + q^{12})t^{3} + …
= \frac{1}{1 − \frac{[1] t}{1 − \frac{q^{2}[3] t}{1 − \frac{[2]_{q^{4}}[5] t}{1 − \frac{q^{2}[2]_{q^{4}}[7] t}{...}}}}} ,  (26)

∑_{n≥0} R_{n}(q)t^{n} = 1 + [3] t + [3](q^{2} + [7]) t^{2} + [3](1 + 2q + 6q^{2} + 8q^{3}
+11q^{4} + 12q^{5} + 15q^{6}[3] + 12q^{9} + 11q^{10}
+9q^{11} + 7q^{12} + 4q^{13} + 3q^{14} + 2q^{15} + q^{16})t^{3} + …
= \frac{1}{1 − \frac{[3] t}{1 − \frac{q^{2}[5] t}{1 − \frac{[2]_{q^{4}}[7] t}{1 − \frac{q^{2}[2]_{q^{4}}[9] t}{...}}}}} .  (27)

De même, en définissant les q-analogues des nombres l_{n} et r_{n} respectivement par l_{n}(q) = L_{n}^{(0,1)}(1, q) et r_{n}(q) = L_{n}^{(1,1)}(1, q), on a

∑_{n≥0} l_{n}(q)t^{n} = 1 + t + [3] t^{2} + [3](1 + 2q + 2q^{2} + q^{3} + q^{4})) t^{3} + …
= \frac{1}{1 − \frac{[1] t}{1 − \frac{q[2] t}{1 − \frac{[2]_{q^{2}}[3] t}{1 − \frac{q[2]_{q^{2}}[4] t}{...}}}}} ,  (28)

∑_{n≥0} r_{n}(q)t^{n} = 1 + (1 + q) t + [2](1 + 2q + q^{2} + q^{3}) t^{2} + …

= \frac{1}{1 − \frac{[2] t}{1 − \frac{q[3] t}{1 − \frac{[2]_{q^{2}}[4] t}{1 − \frac{q[2]_{q^{2}}[5] t}{...}}}}} .  (29)

Remarque: On peut exprimer les fonctions génératrices de toutes les suites ci-dessus en séries de faculté en spécialisant (14). Par contre le calcul de fonctions génératrices exponentielles des suites ci-dessus est un problème ouvert.

3 Construction de la bijection Θ_{n}

Soit σ = x_{1}x_{2} ⋯ x_{rn+k} une (k, r)-MP de [1..n]. Il est clair que σ peut s’écrire de façon unique comme suit :

σ = 0^{m_{1}} w_{1} 0^{m_{2}} w_{2} ⋯ 0^{m_{l}} w_{l} 0^{m_{l+1}},  (30)

où chaque m_{i} est un entier strictement positif, sauf peut-être m_{1} et m_{l+1} qui peuvent être nuls, et chaque w_{j} est un sous-mot maximal non vide de σ formé de lettres non nulles. Notons que si une lettre x apparaît dans le sous-mot w_{j} (1 ≤ j ≤ l), alors toutes les r lettres x’s s’y trouvent. Il s’ensuit que w_{j} est de longueur multiple de r.

Lemme 1 Soit w_{j} = x_{f}x_{f+1} ⋯ x_{f+rh−1} avec h > 0 un sous mot maximal de σ ne contenant pas de lettre 0 et ŵ_{j} = x_{f}x_{f+r} … x_{f+r(h−1)} le mot obtenu en supprimant toutes les lettres x_{i} dans w_{j} telles que i ≢ f mod r. Alors les lettres dans ŵ_{j} sont toutes distinctes.

Démonstration: En effet, supposons que i et i′ (i < i′) sont deux plus petits entiers tels que x_{f+ri} = x_{f+ri′}. Alors les lettres entre x_{f+ri} et x_{f+ri′} dans w_{j} sont plus grandes que x_{f+ri} et par suite toutes les lettres qui leur sont identiques s’y trouvent aussi. Donc le nombre de ces lettres, i.e., r(i′ −i)−1, doit être multiple de r, ce qui est absurde.

Il s’ensuit que si l’on substitue dans (30) chaque w_{j} par ŵ_{j}, on obtient la k-permutation associée à σ:

σ̂ = 0^{m_{1}} ŵ_{1} 0^{m_{2}} ŵ_{2} ⋯ 0^{m_{l}} ŵ_{l} 0^{m_{l+1}}.  (31)

Pour chaque i ∈ [1..n], on numérote les r lettres i’s dans σ de gauche à droite. Si la s-ième i est retenue dans ŵ_{j}, on pose

ϵ(σ, i) = s − 1,  δ(σ, i) = m_{j+1} + ⋯ + m_{l+1}.  (32)

Définition 2 La m-ième lettre x_{m} de σ est un élément saillant inférieur gauche de σ si x_{m} ≠ 0 et si toute lettre à gauche de x_{m} est plus grande que x_{m}. On note sig(σ) le nombre d’éléments saillants inférieurs gauches de σ. Supposons de plus que x_{m} est dans le sous-mot ŵ_{j} (resp. dans w_{j}), on dit que x_{m} est un élément localement saillant inférieur gauche de σ̂ (resp. σ) si toute lettre à gauche de x_{m} dans ŵ_{j} (resp. dans w_{j}) est plus grande que x_{m}.

Lemme 2 Si x_{m} est un élément localement saillant inférieur gauche de σ̂, alors ϵ(σ, x_{m}) = 0.

Démonstration: Supposons que x_{m} est dans w_{j} = x_{f}x_{f+1} ⋯ x_{f+rh−1} (h > 0) et m = f +ri. Si ϵ(σ, x_{f+ri}) ≠ 0, on a i > 0. Soit s le plus petit entier ≥ f tel que x_{s} = x_{f+ri}. Il existe un unique entier h ∈ [0..i − 1] tel que f + rh < s < f + r(h + 1). Comme les lettres distinctes x_{f}, x_{f+r}, …, x_{f+rh} sont plus grandes que x_{s}, toutes les lettres qui leur sont identiques se trouvent à gauche de x_{s}. Il y a donc au moins r(h+1)−1 lettres entre x_{f} et x_{s}; ce qui contredit l’inégalité s < f + r(h + 1).

Définition 3 Soit σ̂ une k-permutation de [1..n] et ϵ = (ϵ_{1}, …, ϵ_{n}) une suite d’entiers de [0..r − 1]. On dit que ϵ est r-compatible avec σ̂ si ϵ_{i} = 0 pour tout i localement saillant inférieur gauche de σ̂.

Lemme 3 Etant données une k-permutation σ̂ de [1..n] et une suite rcompatible (ϵ_{1}, .., ϵ_{n}) avec σ̂, il existe une seule (k, r)- MP σ de [1..n] associée à σ̂ telle que ϵ(σ, i) = ϵ_{i} pour tout i ∈ [1..n].

Démonstration: On procède par récurrence sur n. Pour n = 1, soit σ̂ = 0^{m_{1}}1 0^{m_{2}} où m_{1} + m_{2} = k et ϵ_{1} = 0. Alors σ = 0^{m_{1}}1^{r}0^{m_{2}} est la seule (k, r)- MP de [1..n] associée à σ̂. Supposons le lemme vrai à l’ordre n. Soit σ̂ une k-permutation de [1..n + 1] et (ϵ_{1}, …, ϵ_{n+1}) une suite r-compatible. Il est évident que (ϵ_{1}, …, ϵ_{n}) est une suite r-compatible avec la restriction σ̂′ de σ̂ sur [1..n]. D’après l’hypothèse de récurrence, il existe une seule (k, r)-MP σ′ de [1..n] associée à σ̂′ telle que ϵ(σ′, i) = ϵ_{i} pour tout i ∈ [1..n]. S’il y a s lettres non nulles et t lettres nulles avant la lettre n + 1 dans σ̂, on construit le mot σ en insérant le mot (n + 1)^{r} après la (rs + t − ϵ_{n+1})-ième lettre de σ′. On voit que ϵ(σ, n + 1) = ϵ_{n+1} et que l’unicité de σ′ implique celle de σ.

Nous aurons encore besoin de quelques notions supplémentaires. Toute k-permutation σ̂ peut se décomposer en blocs tels que chaque bloc soit un sous-mot maximal de σ̂ constitué soit de lettres toutes nulles (bloc nul), soit de lettres non nulles formant une suite croissante. La première et la dernière lettre d’un bloc non nul qui ne se réduit pas à un singleton sont appelées respectivement creux et pic de σ̂; les autres lettres d’un tel bloc sont appelées doubles montées de σ̂. Une lettre non nulle formant un bloc singleton est appelée double descente.

Comme dans [5], on dit qu’une lettre i de σ̂ est embrassée à gauche (resp. à droite) par un bloc si i est encadré par la première et la dernière lettre de ce bloc qui se trouve à gauche (resp. à droite) de i. On note res(σ̂, i) (resp. les(σ̂, i)) le nombre de blocs de σ̂ embrassant i et se trouvant à sa droite (resp. à sa gauche).

Exemple: Soit σ = 3 4 6 6 6 4 4 3 3 0 0 1 5 5 5 1 7 7 7 1 0 2 2 2 0. Alors σ est une (4, 3)- MP sur [1..7] et σ̂ = 3 6 − 4 − 0 0 − 1 5 7 − 0 − 2 − 0, où les blocs sont séparés par un trait −. Il en résulte que σ̂ a deux creux 1, 3; deux pics 6, 7; une double montée 5; deux doubles descentes 2, 4. Les statistiques définies ci-dessus de σ sont consignées dans le tableau suivant:

\begin{matrix}i & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ ϵ(σ, i) & 0 & 0 & 0 & 2 & 2 & 1 & 1 \\ δ(σ, i) & 2 & 1 & 4 & 4 & 2 & 4 & 2 \\ res(σ̂, i) & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ les(σ̂, i) & 0 & 1 & 0 & 1 & 1 & 0 & 0 \end{matrix}

Définition 4 Soit σ ∈ S_{n}^{(k,r)}. Pour tout i ∈ [1..n], on définit

RES(σ, i) = r · res(σ̂, i) + ϵ(σ, i) + ϵ_{i}δ(σ, i)

où ϵ_{i} = 1 si i est un creux ou une double descente de σ̂ et ϵ_{i} = 0 si i est un pic ou une double montée de σ̂; et

RES^{∗}(σ, i) = \{ \begin{matrix}2r · RES(σ, i) + r & si i est un pic impair de σ̂; \\ 2r · RES(σ, i) & si i est un pic pair de σ̂; \\ RES(σ, i) & si i n’est pas un pic de σ̂. \end{matrix}

On pose

RES(σ) = ∑_{1≤i≤n} RES(σ, i), RES^{∗}(σ) = ∑_{1≤i≤n} RES^{∗}(σ, i).

On rappelle [8] qu’un chemin de Motzkin est un chemin π = (p_{0}, …, p_{n}) dans le plan N × N qui va de l’origine p_{0} = (0, 0) au point p_{n} = (n, 0) sur l’axe horizontal en n’utilisant que des pas élémentaires Est (i.e., des pas horizontaux ou paliers), Nord-Est et Sud-Est. Si l’on code un pas Nord-Est par NE, un pas Sud-Est par SE et un pas horizontal Est par P, on obtient alors un mot de Motzkin c = c_{1} … c_{n} sur l’alphabet {NE, SE, P } qui est le codage au sens précédent d’un chemin de Motzkin.

Soit h_{1} = 0 et h_{i} = |c_{1} … c_{i−1}|_{NE} − |c_{1} … c_{i−1}|_{SE} pour 2 ≤ i ≤ n, où |w|_{a} représente le nombre d’occurrences de la lettre a dans le mot w. On appelle h_{i} le niveau du i-ième pas c_{i}. Un chemin de Motzkin sans pas Est est appelé chemin de Dyck et le codage correspondant est appelé mot de Dyck.

Pour la commodité de la description de la bijection Θ_{n}, on code dans la suite chaque pas Est d’un chemin de Motzkin par EB (pour Est bleu) ou ER (pour Est rouge).

Définition 5 Une histoire d’Euler d’ordre (k, r) sur [1..n] est un couple (c, p) où c = c_{1}c_{2} ⋯ c_{n} est un mot de Motzkin et p = p_{1}p_{2} ⋯ p_{n} une suite d’entiers positifs telle que

0 ≤ p_{i} ≤ \{ \begin{matrix}rh_{i} + k & si c_{i} =NE ou EB; \\ rh_{i} − 1 & si c_{i} =SE ou ER. \end{matrix}  (33)

On note M_{n}^{(k,r)} l’ensemble des histoires d’Euler d’ordre (k, r) sur [1..n].

Théorème 2 Soit σ une (k, r)- MP sur [1..n] et σ̂ sa k-permutation associée. Pour i = 1, …, n, on pose p_{i} = RES(σ, i) et

c_{i} = \{ \begin{matrix}NE & si i est un creux de σ̂; \\ SE & si i est un pic de σ̂; \\ EB & si i est une double descente de σ̂; \\ ER & si i est une double montée de σ̂. \end{matrix}  (34)

Alors (c, p) = (c_{1} … c_{n}, p_{1} … p_{n}) est une histoire d’Euler d’ordre (k, r) sur [1..n]. De plus, l’application Θ_{n} : S_{n}^{(k,r)} ⟶ M_{n}^{(k,r)} définie par Θ_{n}(σ) = (c, p) est une bijection.

Démonstration: Montrons d’abord que l’application Θ_{n} est bien définie.

1) Si i est un pic ou une double montée de σ̂, alors le niveau h_{i} du c_{i} satisfait l’équation:

h_{i} = res(σ̂, i) + les(σ̂, i) + 1.  (35)

Comme res(σ̂, i) ≤ h_{i} − 1 et ϵ(σ, i) < r, on a donc p_{i} = RES(σ, i) ≤ rh_{i} − 1.

2) Si i est un creux ou une double descente de σ̂, alors le niveau h_{i} du c_{i} satisfait l’équation:

h_{i} = res(σ̂, i) + les(σ̂, i).  (36)

Si ϵ(σ, i) = 0, on a p_{i} = RES(σ, i) ≤ rh_{i} + k. Supposons que ϵ(σ, i) ≠ 0. Soit w = x_{m}x_{m+1} ⋯ x_{m+rq−1} le sous-mot maximal de σ contenant i et ne contenant aucune lettre nulle. Il existe un entier p ∈ [1..q − 1] tel que i = x_{m+rp}. Le lemme 2 implique que p > 0 et qu’il existe un entier u < p tel que x_{m+ru} < x_{m+rp}. D’autre part, comme i est un creux ou une double descente de σ̂, alors x_{m+r(p−1)} > x_{m+rp}. Soit donc s le plus grand des entiers u < p tel que x_{m+ru} < x_{m+rp}. Alors s < p − 1 (ce qui implique que p > 1) et, par suite, le bloc de σ̂ contenant x_{m+rs} embrasse i

Alors s < p − 1 (ce qui implique que p > 1) et, par suite, le bloc de σ̂ contenant x_{m+rs} embrasse i et se trouve à sa gauche. Il en résulte que les(σ̂, i) ≠ 0 et res(σ̂, i) ≤ res(σ̂, i) + les(σ̂, i) − 1 = h_{i} − 1. Il s’ensuit que

RES(σ, i) ≤ r(h_{i} − 1) + ϵ(σ, i) + k ≤ rh_{i} + k − 1.  (37)

Montrons ensuite que l’application Θ_{n} est bijective. Pour ce faire, partant d’une histoire (c, p) vérifiant la relation (33), nous allons trouver de façon algorithmique une unique σ dans S_{n}^{(k,r)} telle que Θ_{n}(σ) = (c, p).

Nous allons d’abord construire la k-permutation σ̂ par n étapes : partant du mot σ̂_{0} = 0^{k} et insérant i à la i-ième étape pour i = 1, …, n.

À l’étape 1, comme ϵ(σ, 1) = res(σ̂, 1) = 0, on a donc δ(σ, 1) = p_{1} et

σ̂_{1} = 0^{k−p_{1}} 1 0^{p_{1}}.

De plus, si c_{1} = NE, on insère une lettre ∗ juste après 1.

Supposons que l’on est à la i-ième étape avec i ≥ 2. Soit y_{1}y_{2} … y_{i−1} le réarrangement de 1, 2, …, i − 1 selon leur disposition. Si s : = h_{i} > 0, soit y_{j_{1}}, y_{j_{2}}, …, y_{j_{s}} les lettres suivies d’une ∗ dans σ̂_{i−1}. Posons, pour simplifier, z_{l} = y_{j_{l}} (1 ≤ l ≤ s).

Notons tout d’abord que :

– chaque fois qu’on insère un creux, on insère une ∗ après lui; – on n’insère avant une ∗ qu’une lettre qui soit une double montée de σ̂

mais on ne peut pas insérer une lettre juste après une lettre non nulle non suivie d’une ∗;

– insérer un pic, c’est remplacer une ∗ par ce pic.

1. Si c_{i} = ER ou SE, alors s > 0 et les relations

p_{i} = r · res(σ̂, i) + ϵ(σ, i) et ϵ(σ, i) < r

impliquent que res(σ̂, i) et ϵ(σ, i) sont respectivement le quotient et le reste de la division de p_{i} par r. Par conséquent,

– si c_{i} = ER, on insère la lettre i juste après z_{s−res(σ̂,i)};

– si c_{i} = SE, on remplace par la lettre i l’∗ qui suit z_{s−res(σ̂,i)}.

2. Si c_{i} = NE, on distingue deux cas suivant que s = 0 ou s > 0. \underline{s = 0}. On a nécessairement res(σ̂, i) = 0. De plus, ϵ(σ, i) = 0 d’après le lemme 2. δ(σ, i) = p_{i}:

– Si p_{i} = k, on place le mot i∗ en première position;

– Si p_{i} < k, on insère le mot i∗ juste après la (k − p_{i})-ième lettre 0.

\underline{s > 0}. On distingue 4 cas :

– 1-er cas : p_{i} < δ(σ, z_{s}). La lettre i ne doit pas être placée avant z_{s}, ni juste après l’∗ qui suit z_{s}. Donc res(σ̂, i) = 0, ϵ(σ, i) = 0 et, par suite, δ(σ, i) = p_{i}. On insère ainsi la lettre i après la (k − p_{i})-ième lettre 0, puis une ∗ après i.

– 2-ième cas : δ(σ, z_{s}) ≤ p_{i} < δ(σ, z_{s}) + r.

Dans ce cas, on doit insérer i après l’∗ qui suit z_{s}, suivi d’une ∗. Nécessairement, res(σ̂, i) = 0, δ(σ, i) = δ(σ, z_{s}) et ϵ(σ, i) = p_{i} − δ(σ, z_{s}).

– 3-ième cas : δ(σ, z_{l}) + r(s − l + 1) ≤ p_{i} < δ(σ, z_{l−1}) + r(s − l + 2) (1 ≤ l ≤ s). Dans ce cas, la lettre i doit être placée entre z_{l−1} et z_{l}. Donc, res(σ̂, i) = s − l + 1. Posons d_{i} = p_{i} − r(s − l + 1).

– Si d_{i} < δ(σ, z_{l−1}), alors δ(σ, i) = p_{i} et ϵ(σ, i) = 0. On insère i après la (k − d_{i})-ième lettre 0, puis une ∗ après i.

– Si d_{i} ≥ δ(σ, z_{l−1}), alors δ(σ, i) = δ(σ, z_{l−1}) et ϵ(σ, i) = d_{i} − δ(σ, z_{l−1}). On insère i après l’∗ qui suit z_{l−1}, puis une ∗ après i.

– 4-ième cas : p_{i} ≥ δ(σ, z_{1}) + rs. La lettre i doit être placée avant z_{1}. On a res(σ̂, i) = s, ϵ(σ, i) = 0 et, par suite, δ(σ, i) = p_{i} − rs. On insère donc i juste après la (k − p_{i} + rs)-ième lettre 0, puis une ∗ après i (i est placé en première position si k − p_{i} + rs = 0).

3. Si c_{i} = EB, même chose que le cas où c_{i} = NE, mais on n’insère pas une ∗ après i.

À la fin de la n-ième étape, il n’y a plus d’∗ car le nombre de NE est égal au nombre de SE dans c.

Cet algorithme nous permet donc de déterminer de façon unique une k-permutation σ̂ et une suite r-compatible (ϵ_{1}, …, ϵ_{n}). D’après le lemme 3, σ est entièrement déterminée.

Exemple: Considérons l’histoire (c, p) de M_{9}^{(5,3)} où c = (EB, NE, NE, SE, ER, NE, EB, SE, SE) et p = (3, 0, 8, 2, 2, 4, 9, 5, 0). Soit σ son antécédent et σ̂ la k-permutation associée à σ.

1) Construction de σ̂.

étape i  nature de i  RES(σ, i) δ(σ, i) ϵ(σ, i)  σ̂_{i}
1  double descente  0  3  0  0^{2}10^{3}
2  creux  0  0  0  0^{2}10^{3}2∗
3  creux  1  5  0  3 ∗ 0^{2}10^{3}2∗
4  pic  0  –  2  3 ∗ 0^{2}10^{3}24
5  double montée  0  –  2  35 ∗ 0^{2}10^{3}24
6  creux  0  4  0  35 ∗ 06 ∗ 010^{3}24
7  double descente  1  5  1  35 ∗ 706 ∗ 010^{3}24
8  pic  1  –  2  358706 ∗ 010^{3}24
9  pic  0  –  0  3587069010^{3}24

On a σ̂ = σ̂_{9} = 3 5 8 7 0 6 9 0 1 0^{3} 2 4.

2) Construction de σ. Notons σ_{j} la restriction de σ à S_{j}^{(5,3)} (1 ≤ j ≤ 9). Cette restriction a pour k-permutation associée σ̂_{j} sans ‘∗’. Comme σ_{j} se déduit de σ_{j−1} (2 ≤ j ≤ 9) en insérant j^{3} après la (3s + t − ϵ(σ, j))-ième lettre de σ_{j−1}, où s (resp.t) est le nombre de lettres non nulles (resp. lettres nulles) à gauche de j dans σ̂_{j}, on a successivement:

σ_{1} = 0^{2}1^{3}0^{3};
σ_{2} = 0^{2} 1^{3} 0^{3} 2^{3};

σ_{3} = 3^{3} 0^{2} 1^{3} 0^{3} 2^{3};
σ_{4} = 3^{3} 0^{2} 1^{3} 0^{3} 2 4^{3} 2^{2};
σ_{5} = 3 5^{3} 3^{2} 0^{2} 1^{3} 0^{3} 2 4^{3} 2^{2};
σ_{6} = 3 5^{3} 3^{2} 0 6^{3} 0 1^{3} 0^{3} 2 4^{3} 2^{2};
σ_{7} = 3 5^{3} 3 7^{3} 3 0 6^{3} 0 1^{3} 0^{3} 2 4^{3} 2^{2};
σ_{8} = 3 5^{3} 8^{3} 3 7^{3} 3 0 6^{3} 0 1^{3} 0^{3} 2 4^{3} 2^{2};
σ_{9} = 3 5^{3} 8^{3} 3 7^{3} 3 0 6^{3} 9^{3} 0 1^{3} 0^{3} 2 4^{3} 2^{2}.

C’est-à-dire σ = σ_{9} = 3 5^{3} 8^{3} 3 7^{3} 3 0 6^{3} 9^{3} 0 1^{3} 0^{3} 2 4^{3} 2^{2}.

4 Interprétations combinatoires

Soit D_{2n} l’ensemble des mots de Dyck de longueur 2n. Soient (a_{k})_{k≥0} et (b_{k})_{k≥1} deux suites d’éléments d’un anneau commutatif K. A chaque mot c = c_{1} … c_{2n} de Dyck de longueur 2n on associe le poids :

v(w) = ∏_{i=1}^{2n} v(c_{i}) avec v(c_{i}) = \{ \begin{matrix}a_{k} & si c_{i} = NE et h_{i} = k; \\ b_{k} & si c_{i} = SE et h_{i} = k. \end{matrix}

Alors la fonction génératrice de D_{2n} a le développement en fraction continue suivant (voir [8]) :

1 + ∑_{n≥1} ∑_{w∈D_{2n}} v(w)t^{n} \frac{1}{1 − \frac{a_{0}b_{1} t}{1 − \frac{a_{1}b_{2} t}{1 − \frac{a_{2}b_{3} t}{1 − \frac{a_{3}b_{4} t}{...}}}}} .  (38)

Définition 6 Soit σ une (k, r)-MP sur [1..n] et σ̂ sa k-permutation associée. On dit que σ̂ est alternante si elle n’a ni double montée ni double descente. Dans ce cas, on dit que σ est une (k, r)-MP alternante. On notera Γ_{n}^{(k,r)} l’ensemble des (k, r)-MP alternantes sur [1..2n].

Théorème 3 On a l’interprétation combinatoire suivante:

E_{n}^{(k,r)}(x, q) = ∑_{σ∈Γ_{n}^{(k−1,r)}} x^{sig(σ)}q^{RES(σ)},  (39)

où sig(σ) et RES(σ) sont définis respectivement dans la définition 2 et dans la définition 4.

Démonstration: D’après (38), l’équation (16) équivaut à

E_{n}^{(k,r)}(x, q) = ∑_{c∈D_{2n}} ∏_{c_{i}=SE}[rh_{i}] ∏_{c_{i}=NE}([rh_{i} + k − 1] + xq^{rh_{i}+k−1}).

D’autre part, pour tout σ ∈ Γ_{n}^{(k−1,r)}, on a sig(σ) = sig(σ̂). Soit (c, p) = Θ_{2n}(σ). Comme sig(σ̂) est égal au nombre de creux x de σ̂ telles que les(σ̂, x) = 0 et δ(σ̂, x) = k − 1, la bijection Θ_{2n} implique que sig(σ) est égal au nombre de c_{i} = NE telles que p_{i} = rh_{i−1} + k − 1. D’où (39).

En particulier, pour r = q = 1, on retrouve un résultat connu sur les nombres d’Euler d’ordre k (voir [6, 8]).

Corollaire 1 Le nombre de (k − 1, 1)-MP alternantes de [1..2n] est E_{2n}^{(k)}.

Comme RES se réduit à res sur Γ_{n}^{(0,1)}, on déduit de (17) le résultat suivant.

Corollaire 2 Les q-polynômes sécants et les q-polynômes tangents ont pour interprétations respectives:

S_{n}(x, q) = ∑_{σ∈Γ_{n}^{(0,1)}} x^{sig(σ)}q^{res(σ)};  (40)
T_{n}(x, q) = ∑_{σ∈Γ_{n}^{(1,1)}} x^{sig(σ)}q^{RES(σ)}.  (41)

En particulier, on obtient un q-analogue d’un résultat d’André [1] :

E_{2n}(q) = ∑_{σ∈Γ_{n}^{(0,1)}} q^{res(σ)}, E_{2n+1}(q) = ∑_{σ∈Γ_{n}^{(1,1)}} q^{RES(σ)}.  (42)

Il est à noter que pour q = 1 on retrouve la même interprétation d’André pour E_{2n} et mais une nouvelle interprétation pour E_{2n+1}. Par exemple, on a Γ_{1}^{(0,1)} = {12, 21}, Γ_{1}^{(1,1)} = {012, 120}, Γ_{2}^{(0,1)} = {1324, 1423, 2314, 2413, 3412} et Γ_{2}^{(1,1)} = {01324, 01423, 13024, 14023, 02413, 02314, 24013, 23014, 03412, 34012, 13240, 14230, 24130, 23140, 34120, 12034}.

Définition 7 On note γ_{n}^{(k,r)} l’ensemble des (k, r)-MP alternantes σ de [1..2n] telles que RES(σ, i) ≤ ⌈(res(σ̂, i) + les(σ̂, i) + 1)/2⌉ − 1 pour tout pic i de σ̂.

Théorème 4 On a

L_{n}^{(k,r)}(x, q) = ∑_{σ∈γ_{n}^{(k,r)}} x^{sig(σ)}q^{RES^{∗}(σ)}.

En particulier,

l_{n}(q) = ∑_{σ∈γ_{n}^{(0,1)}} q^{RES^{∗}(σ)}, r_{n}(q) = ∑_{σ∈γ_{n}^{(1,1)}} q^{RES^{∗}(σ)},  (43)
L_{n}(q) = ∑_{σ∈γ_{n}^{(0,2)}} q^{RES^{∗}(σ)}, R_{n}(q) = ∑_{σ∈γ_{n}^{(2,2)}} q^{RES^{∗}(σ)}.  (44)

Démonstration: La démonstration est analogue à celle du théorème 3. La bijection Θ_{2n} implique que

∑_{σ∈γ_{n}^{(k,r)}} x^{sig(σ)}q^{RES^{∗}(σ)} = ∑_{c∈D_{2n}} ∏_{{c_{i}=SE \atop i pair}}[(h_{i} + 1)/2]_{q^{2r}} ∏_{{c_{i}=SE \atop i impair}} q^{r}[h_{i}/2]_{q^{2r}}

∏_{c_{i}=NE}([rh_{i} + k] + xq^{rh_{i}+k}).

Comme [2nr] = [2r][n]_{q^{2r}}, l’équation (25) montre que cette dernière somme est aussi égale à L_{n}^{(k,r)}(x, q).

En prenant q = 1, on obtient les interprétations suivantes pour les nombres correspondants.

– L_{n} représente le nombre de 2-MP alternantes σ de [1..2n] telles que 2 RES(σ, i) ≤ res(σ̂, i) + les(σ̂, i) pour tout pic i de σ̂;

– R_{n} représente le nombre de (2,2)-MP alternantes σ de [1..2n] telles que 2 RES(σ, i) ≤ res(σ̂, i) + les(σ̂, i) pour tout pic i de σ̂;

– l_{n} représente le nombre de permutations alternantes σ de [1..2n] telles que res(σ, i) ≤ les(σ, i) pour tout pic i de σ;

– r_{n} représente le nombre de (1,1)-MP alternantes σ de [1..2n] telles que res(σ, i) ≤ les(σ, i) pour tout pic i de σ.

Par exemple, pour n = 2 on a l_{2} = #{1423, 2413, 3412} = 3, r_{2} = #{12034, 01423, 14023, 14230, 02413, 24013, 24130, 03412, 34012, 34120} = 10, L_{2} = #{11442233, 12442133, 22441133, 33441122} = 4 et R_{2} = #{0112203344, 1122003344, 1122033440, 0033441122, 0334401122, 0334411220, 3344001122, 3344011220, 3344112200, 0011442233, 0012442133, 0114402233, 0114422330, 0124421330, 1144002233, 1144022330, 1144223300, 1244213300, 0022441133, 0224401133, 0224411330, 2244001133, 2244011330, 2244113300} = 24.

5 Liens avec les nombres de Genocchi

On rappelle que les nombres de Genocchi sont définis par

∑_{n≥1} G_{2n} \frac{t^{2n}}{(2n)!} = t tan(t/2).

Posons

G_{n}^{(r)}(x, q) = P_{n}^{(0,r,r,0)}(x, q).  (45)

Il vient du Théorème 1 que

∑_{n≥0} G_{n}^{(r)}(x, q)t^{n} = 1 + [r]x t + [r]^{2}x(x + [x, r]) t^{2} + …
= \frac{1}{1 − \frac{[r]x t}{1 − \frac{[r][x, r]_{q} t}{1 − \frac{[2r][x, r]_{q} t}{1 − \frac{[2r][x, 2r]_{q} t}{1 − \frac{[3r][x, 2r]_{q} t}{1 − \frac{[3r][x, 3r]_{q} t}{...}}}}}}} . (46)

On en déduit alors de la formule de S-fraction continue pour les nombres de Genocchi [19] que

G_{n}^{(1)}(1, 1) = G_{2n+2}.

D’autre part, par (3) on voit que

G_{n}^{(2)}(1, 1) = E_{2n+1}.

Rappelons que, si k = 0, une (k, r)-MP se réduit à une r-MP. Soit Γ_{n}^{r} l’ensemble des r-MP alternantes σ de [1..2n] telles que

– res(σ, i) ≤ les(σ, i) pour tout pic i de σ;

– res(σ, i) ≤ les(σ, i) + (−1)^{χ(ϵ(σ,i)≠0)} pour tout creux i de σ.

Définition 8 Une histoire de Genocchi d’ordre r sur [1..2n] est un couple (c, p) où c est un mot de Dyck de longueur 2n et p = p_{1}p_{2} ⋯ p_{2n} une suite de 2n entiers telle que 0 ≤ p_{i} ≤ r⌈h_{i−1}/2⌉ si c_{i} est un NE de c et 0 ≤ p_{i} ≤ r⌈h_{i−1}/2⌉ − 1 si c_{i} est un SE de c. On note H_{n}^{(r)} l’ensemble des histoires de Genocchi d’ordre r sur [1..2n].

Remarque: Pour r = 1, on retrouve la même notion de [16]. Théorème 5 On a l’interprétation combinatoire suivante :

G_{n}^{(r)}(x, q) = ∑_{σ∈Γ_{n}^{r}} x^{EQUI(σ̂)}q^{RES(σ)}.  (47)

où EQUI(σ̂) est le nombre de creux i de σ̂ tels que res(σ̂, i) = les(σ̂, i) ou res(σ̂, i) = les(σ̂, i) + 1. Démonstration: La restriction de Θ_{2n} sur Γ_{n}^{r} envoie bijectivement Γ_{n}^{r} sur l’ensemble H_{n}^{(r)}. On note que EQUI(σ̂) correspond au nombre de NE dans c telles que p_{i} = r⌈h_{i}/2⌉. On a donc l’identité suivante:

∑_{σ∈Γ_{n}^{r}} x^{EQUI(σ̂)}q^{RES(σ)} = ∑_{c∈D_{2n}} ∏_{c_{i}=NE}([r ⌈h_{i−1}/2⌉] + xq^{r⌈h_{i−1}/2⌉})

× ∏_{c_{i}=SE}[r⌈h_{i−1}/2⌉],

ce qui est exactement la formule obtenue pour G_{n}^{(r)}(x, q) en appliquant (38) à (46).

Il en résulte que G_{2n+2} est égal au nombre de permutations alternantes σ de [1..2n] telles que

– res(σ, i) ≤ les(σ, i) pour tout pic i de σ;

– res(σ, i) ≤ les(σ, i) + 1 pour tout creux i de σ. Par exemple, on a G_{6} = #{1423, 2413, 3412} = 3. Remerciements Nous remercions les deux arbitres anonymes pour leurs lectures attentives, qui ont permis d’améliorer la présentation de cet article.

Références

[1] André (D.). Sur les permutations alternées, J. de Math. Pures et Appliquées, 7 (1881), Séries 3, 167-184.

[2] Andrews (G.) et Foata (D.). Congruences for the q-secant numbers, European J. Combin., 1 (1980), no. 4, 283-287.

[3] Andrews (G.) et Gessel (I.). Divisibility properties of the q-tangent numbers, Proc. Amer. Math. Soc., 68 (1978), no. 3, 380-384.

[4] Arnold (V. I.). Bernoulli-Euler updown numbers associated with function singularities, their combinatorics and arithmetics, Duke Math. J., 63 (1974), 537-555.

[5] Clarke (R.), Steingrimsson (E.) et Zeng (J.). New Euler-Mahonian Statistics on Permutations and Words, Adv. Appl. Math., 18 (1997), 237-270.

[6] Carlitz (L.) et Scoville (R.). Tangent numbers and operators, Duke. Math. J., 39 (1972), 413-429.

[7] Dumont (D.). Further triangles of Seidel-Arnold type and continues fractions related to Euler and Springer numbers, Adv. Appl. Math., 16 (1995), 275-296.

[8] Flajolet (P.). Combinatorial aspects of continued fractions, Disc. Math., 32 (1980), 125-161.

[9] Flajolet (P.). On congruences and continued fractions for some classical combinatorial quantities, Disc. Math., 41 (1982), 145-153.

[10] Foata (D.). Further divisibility properties of the q-tangent numbers, Proc. Amer. Math. Soc., 81 (1981), no. 1, 143-148.

[11] Gessel (I.) et Stanley (R.). Stirling polynomials, J. Combin. Theory, Ser. A 24 (1978), 24-33.

[12] Graham (R.), Knuth (D.) et Patashnik (O.). Concrete mathematics, second edition, Addison-Wesley, 1994.

[13] Han (G.N.) et Zeng (J.). q-Polynômes de Gandhi et statistique de Denert, to appear in Disc. Math., 1999.

[14] Han (G.N.) et Zeng (J.). On a q-sequence that generalizes the median Genocchi numbers , to appear in Ann. Sci. Math. Québec, 1999

[15] Park (S.). The r-multipermutations, J. Combin. Theory, Ser. A 67 (1994), 44-71.

[16] Randrianarivony (A.). Fractions continues, q-nombres de Catalan et qpolynômes de Genocchi, European J. Combin., 18(1997), 75-92.

[17] Randrianarivony (A.) et Zeng (J.). Sur une extension des nombres d’Euler et les records des permutations alternantes, J. Combin. Theory Ser. A, 68 (1994), 86-99.

[18] Randrianarivony (A.) et Zeng (J.). Une famille de polynômes qui interpole plusieurs suites classiques de nombres, Adv. Appl. Math., 17 (1996), 1-26.

[19] Viennot (G.). Une théorie combinatoire des nombres d’Euler et Genocchi, Séminaire de Théorie des nombres de l’Université Bordeaux, Exposé no. 11, 1980–1981, Publications de l’Université Bordeaux I.

[20] Wall (H.S.). Continued fractions and totally monotone sequences, Trans. Amer. Math. Soc. 48 (1940), 165-184.