SUR UNE EXTENSION DES NOMBRES D’EULER ET LES RECORDS DES PERMUTATIONS ALTERNANTES

Arthur RANDRIANARIVONY et Jiang ZENG

Abstract

We study the sequence of polynomials C_{n}(x, y) defined through the recurrence C_{0}(x, y) = 1, C_{n}(x, y) = x(y + 1)C_{n−1}(x + 2, y + 2) − xyC_{n−1}(x, y), which turns out to be an extension of Euler numbers. We give a combinatorial interpretation of these numbers in terms of down-up permutations with respect to the numbers of even and odd upper records, and a continued fraction expansion for their ordinary generating function.

1 Introduction

Dans [5], Dumont et Randrianarivony ont trouvé une extension polynomiale des nombres de Genocchi et de Genocchi médians. Dans cet article, on se propose d’étudier une extension analogue pour les nombres d’Euler. Soit (C_{n}(x, y))_{n≥0} la suite de polynômes définie par la récurrence suivante :

\{ \begin{matrix}C_{0}(x, y) & = & 1, \\ C_{n}(x, y) & = & x(y + 1)C_{n−1}(x + 2, y + 2) − xyC_{n−1}(x, y) (n ≥ 1). \end{matrix} (1)

Les premières valeurs de ces polynômes sont :

C_{1}(x, y) = x,
C_{2}(x, y) = x^{2} + 2xy + 2x,
C_{3}(x, y) = x^{3} + 10x^{2}y + 4xy^{2} + 10x^{2} + 20xy + 16x.

Posons C(x, y; t) = ∑_{n≥0} C_{n}(x, y)t^{n}. La relation de récurrence (1) implique alors que

(1 + xyt)C(x, y; t) = 1 + x(y + 1)tC(x + 2, y + 2; t).  (2)

D’où

C(x, y; t) = \frac{1}{1 + xyt} + \frac{x(y + 1)t}{1 + xyt}C(x + 2, y + 2; t),

et par itération on obtient le résultat suivant.

Proposition 1 On a

∑_{n≥0} C_{n}(x, y)t^{n} = \frac{1}{1 + xyt} + \frac{x(y + 1)t}{(1 + xyt)(1 + (x + 2)(y + 2)t)} + ⋯

= ∑_{n≥0} \frac{2^{2n}(\frac{x}{2})_{n}(\frac{y+1}{2})_{n}t^{n}}{∏_{k=0}^{n}[1 + (x + 2k)(y + 2k)t]},

où (x)_{0} = 1 et (x)_{n} = x(x + 1) ⋯ (x + n − 1) pour n ≥ 1.

L’objet principal de cet article est de démontrer les trois théorèmes suivants.

Théorème 1 On a la fraction continue formelle :

∑_{n≥0} C_{n}(x, y)t^{n} = \frac{1}{1 − \frac{1xt}{1 − \frac{2(y + 1)t}{1 − \frac{3(x + 2)t}{1 − \frac{4(y + 3)t}{...}}}}} ·

Nous disons qu’une permutation σ de [n] := {1, 2, …, n} est alternante, si

σ(1) > σ(2), σ(2) < σ(3), σ(3) > σ(4), · · · .  (3)

Un élément x ∈ [n] est dit record de σ si pour un certain i ∈ [n], on a

x = σ(i) = max{σ(1), σ(2), …, σ(i)}.

On note respectivement recp(σ) et reci(σ) le nombre de records pairs et le nombre de records impairs de σ. Soit S_{n} (resp. A_{n}) l’ensemble des permutations (resp. permutations alternantes) de [n]. Posons f_{0}(x, y) = 1 et

f_{n}(x, y) = ∑_{σ∈A_{n}} x^{recp(σ)}y^{reci(σ)},  n ≥ 1.  (4)

Théorème 2 On a

∑_{n≥0} f_{2n}(x, y)t^{2n} = \frac{1}{1 − \frac{1xt^{2}}{1 − \frac{2(y + 1)t^{2}}{1 − \frac{3(x + 2)t^{2}}{1 − \frac{4(y + 3)t^{2}}{...}}}}} ,  (i)

∑_{n≥0} f_{2n+1}(x, y)t^{2n+1} = \frac{yt}{1 − \frac{1(x + 1)t^{2}}{1 − \frac{2(y + 2)t^{2}}{1 − \frac{3(x + 3)t^{2}}{1 − \frac{4(y + 4)t^{2}}{...}}}}} ·  (ii)

Le résultat suivant est une conséquence immédiate des théorèmes 1 et 2. Théorème 3 Pour tout n ≥ 1, les polynômes C_{n}(x, y) ont l’interprétation combinatoire suivante :

C_{n}(x, y) = f_{2n}(x, y) = ∑_{σ∈A_{2n}} x^{recp(σ)}y^{reci(σ)},
yC_{n−1}(x + 1, y + 1) = f_{2n−1}(x, y) = ∑_{σ∈A_{2n−1}} x^{recp(σ)}y^{reci(σ)}.

Rappelons que les nombres d’Euler E_{n} sont classiquement définis par :

∑_{n≥0} E_{n} \frac{x^{n}}{n!} = sec x + tg x.

Il est bien connu [1, 7] que E_{n} = f_{n}(1, 1), on déduit donc du théorème 3 le Corollaire 1 On a :

E_{2n} = C_{n}(1, 1),
E_{2n+1} = C_{n}(2, 2) = \frac{∂}{∂x}C_{n+1}(x, y)|_{x=y=0}.

Pour avoir la dernière égalité, il suffit de dériver par rapport à x les deux membres de (1) puis on remplace x et y par 0. Par conséquent, dans la proposition 1, si l’on remplace t par t^{2} et x, y par 1 puis par 2, on trouve successivement les identités :

∑_{n≥0} E_{2n}t^{2n} = \frac{1}{1 + 1^{2}t^{2}} + \frac{2!t^{2}}{(1 + 1^{2}t^{2})(1 + 3^{2}t^{2})}

+\frac{4!t^{4}}{(1 + 1^{2}t^{2})(1 + 3^{2}t^{2})(1 + 5^{2}t^{2})} + ⋯,

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

+\frac{5!t^{5}}{(1 + 2^{2}t^{2})(1 + 4^{2}t^{2})(1 + 6^{2}t^{2})} + · · · .

Remarque. Ces deux formules sont différentes de celles obtenues par l’application directe de la transformation de Laplace à sec x et tg x, voir [14].

En combinant ces deux identités, nous obtenons le développement en série de fractions rationnelles de la série génératrice ordinaire des nombres d’Euler.

Corollaire 2 On a

∑_{n≥0} E_{n}t^{n} = ∑_{n≥0} \frac{n!t^{n}}{∏_{0≤k≤[ \frac{n+1}{2} ]}(1 + (n − 2k + 1)^{2}t^{2})}·

où [x] désigne le plus grand entier ≤ x.

Le théorème 2 implique également le

Corollaire 3 On a

f_{2n+1}(x, y) = yf_{2n}(x + 1, y + 1).

On remarque que lorsque x = y, ce résultat a été établi par Carlitz et Scoville [3] par la méthode classique. En effet, ils ont trouvé les fonctions génératrices exponentielles suivantes :

∑_{n≥0} f_{2n}(x, x)\frac{t^{2n}}{(2n)!} = (sec t)^{x},
∑_{n≥0} f_{2n+1}(x, x)\frac{t^{2n+1}}{(2n + 1)!} = x ∫_{0}^{t} (sec u)^{x+1}du.

Enfin, dans le théorème 2 (i), si l’on prend x = y on retrouve alors un résultat classique de Stieltjes [9] et Flajolet [6] l’a déjà démontré combinatoirement en supposant que x est un entier.

Au paragraphe 2 nous allons donner deux démonstrations différentes du théorème 1. La première est analogue à celle utilisée dans [5], la deuxième utilise un résultat de Wall [13]. Au paragraphe 3 nous appliquons la théorie combinatoire des fractions continues de Flajolet [6] et la bijection de Françon-Viennot [8] pour démontrer le théorème 2. Nous terminons cet article avec quelques résultats et remarques supplémentaires au paragraphe 4.

2 Deux démonstrations du théorème 1

1ère preuve : Pour i ≥ 1, soit

c_{i} = \{ \begin{matrix}i(x + i − 1) & si i est impair, \\ i(y + i − 1) & si i est pair. \end{matrix}

Considérons le tableau de Stieltjes [9] des s_{n,k}(x, y) défini par la récurrence suivante :

\{ \begin{matrix}s_{0,0}(x, y) & = & 1, s_{n,k}(x, y) = 0 si k ∉ [0, n], \\ s_{n,k}(x, y) & = & s_{n−1,k}(x, y) + c_{n−k+1}s_{n,k−1}(x, y). \end{matrix}

Pour toute fonction f(x, y), on pose Δf(x, y) = f(x + 2, y + 2) − f(x, y).

Lemme 1 On a l’identité :

Δs_{n,k}(x, y) = (n − k + 1)(n − k + 2)s_{n+1,k−1}(x, y).  (5)

Démonstration. On procède par récurrence sur la somme n + k = m. Il est clair que le lemme est vrai pour m = 1. Supposons que (5) est vrai pour m − 1. Par définition, on a :

Δs_{n,k}(x, y) = Δs_{n−1,k}(x, y) + Δ(c_{n−k+1}(x, y)s_{n,k−1}(x, y))
= Δs_{n−1,k}(x, y) + c_{n−k+1}(x + 2, y + 2)Δs_{n,k−1}(x, y)
+s_{n,k−1}(x, y)Δc_{n−k+1}(x, y)
= Δs_{n−1,k}(x, y) + (n − k + 1)((z + 2 + n − k)Δs_{n,k−1}(x, y)
+2s_{n,k−1}(x, y)).

où z = x ou y suivant que m est pair ou impair.

D’autre part, par hypothèse de récurrence,

Δs_{n−1,k}(x, y) = (n − k)(n − k + 1)s_{n,k−1}(x, y),
Δs_{n,k−1}(x, y) = (n − k + 2)(n − k + 3)s_{n+1,k−2}(x, y).

En reportant ces expressions dans l’identité plus haut, on retrouve, après simplification, la relation (5) pour n + k = m . En appliquant ce lemme,

on a :

x(y + 1)s_{n−1,n−1}(x + 2, y + 2) − xys_{n−1,n−1}(x, y)
= x(y + 1)[s_{n−1,n−1}(x, y) + 2s_{n,n−2}(x, y)] − xys_{n−1,n−1}(x, y)
= x[s_{n−1,n−1}(x, y) + 2(y + 1)s_{n,n−2}(x, y)]
= xs_{n,n−1}(x, y) = s_{n,n}(x, y).

Ainsi s_{n,n}(x, y) vérifie la récurrence (1). Par conséquent s_{n,n}(x, y) = C_{n}(x, y). Posons f_{i}(x, y; t) = ∑_{k≥0} s_{i+k,k}(x, y)t^{k}, alors f_{0}(x, y; t) = ∑_{n≥0} C_{n}(x, y)t^{n}.

D’autre part, on a f_{0}(x, y; t) = 1 + c_{1}f_{1}(x, y; t) et

f_{i}(x, y; t) = f_{i−1}(x, y; t) + c_{i+1}tf_{i+1}(x, y; t),

d’où

f_{0}(x, y; t) = \frac{1}{1 − c_{1}t\frac{f_{1}(x, y; t)}{f_{0}(x, y; t)}} , \frac{f_{i}(x, y; t)}{f_{i−1}(x, y; t)} = \frac{1}{1 − c_{i+1}t\frac{f_{i+1}(x, y; t)}{f_{i}(x, y; t)}} .

et par itération, on obtient le théorème 2.

2ième preuve : Nous avons besoin du lemme suivant dû à Wall [13] :

Lemme 2 On a :

\frac{1 + t}{1 − \frac{(g_{1} − 1)t}{1 − \frac{(g_{2} − 1)g_{1}t}{1 − \frac{(g_{3} − 1)g_{2}t}{...}}}} = 1 + \frac{g_{1}t}{1 − \frac{(g_{1} − 1)g_{2}t}{1 − \frac{(g_{2} − 1)g_{3}t}{1 − \frac{(g_{3} − 1)g_{4}t}{...}}}} ·

Posons

C(x, y; t) = \frac{1}{1 − \frac{xy(g_{1} − 1)t}{1 − \frac{xy(g_{2} − 1)g_{1}t}{1 − \frac{xy(g_{3} − 1)g_{2}t}{...}}}} .  (6)

Soit g′_{i} = g_{i}(x + 2, y + 2). En substituant (6) dans (2) et en remplaçant xyt par t, nous avons :

\frac{1 + t}{1 − \frac{(g_{1} − 1)t}{1 − \frac{(g_{2} − 1)g_{1}t}{1 − \frac{(g_{3} − 1)g_{2}t}{...}}}} = 1 + \frac{(1 + \frac{1}{y})t}{1 − \frac{(1 + \frac{2}{x})(1 + \frac{2}{y})(g′_{1} − 1)t}{1 − \frac{(1 + \frac{2}{x})(1 + \frac{2}{y})(g′_{2} − 1)g′_{1}t}{1 − \frac{(1 + \frac{2}{x})(1 + \frac{2}{y})(g′_{3} − 1)g′_{2}t}{...}}}} ·

En appliquant le lemme de Wall, on trouve successivement :

g_{1} = 1 + \frac{1}{y},
g_{2} = (1 + \frac{2}{x})(1 + \frac{2}{y})\frac{g′_{1} − 1}{g_{1} − 1} = 1 + \frac{2}{x},
g_{3} = (1 + \frac{2}{x})(1 + \frac{2}{y})\frac{g′_{2} − 1}{g_{2} − 1}g′_{1} = 1 + \frac{3}{y},

et plus généralement, pour n ≥ 1, on a

g_{2n−1} = 1 + \frac{2n − 1}{y}, g_{2n} = 1 + \frac{2n}{x}·

En portant ces valeurs dans (6), nous avons le résultat.

3 Énumérations des nombres de records pairs et impairs

On appelle chemin de n pas une suite γ = (γ(0), γ(1), …, γ(n)) d’entiers de {0, 1, …, n} telle que γ(0) = γ(n) = 0 et pour tout k ∈ {1, …, n}, on a |γ(k) − γ(k − 1)| ≤ 1, autrement dit les pas (γ(k − 1), γ(k)) sont, soit des montées de +1, soit des paliers, soit des descentes de −1. On appelle γ(k−1) le niveau et k la position du pas (γ(k − 1), γ(k)), qui est donc le kième pas du chemin γ. A un palier situé au niveau k on associe la lettre b_{k}, à une descente du niveau k + 1 vers le niveau k est associée la lettre c_{k+1} et à une montée du niveau k vers le niveau k + 1 est associée la lettre a_{k}. La valuation d’un chemin γ, notée w(γ), est le produit des lettres commutatives associées à ses pas. On note Γ(n) l’ensemble des chemins de n pas.

Proposition 2 (Flajolet [6]) La série génératrice ordinaire des valuations des chemins de n pas admet le développement en fraction continue suivant :

1 + ∑_{n≥1} ( ∑_{γ∈Γ(n)} w(γ)) t^{n} = \frac{1}{1 − b_{0} t − \frac{a_{0}c_{1} t^{2}}{1 − b_{1} t \frac{a_{1}c_{2} t^{2}}{... \overline{1 − b_{k} t − \frac{a_{k}c_{k+1} t^{2}}{...}}}}} ·

On appelle chemin marqué de n pas tout couple (γ, s_{1}s_{2} … s_{n}), où γ est un chemin de n pas et (s_{1}, s_{2}, …, s_{n}) une suite d’entiers.

Théorème 4 (Françon et Viennot [8]) Soit Π_{n} (resp. Π′_{n}) l’ensemble des chemins marqués (γ, s) de n pas tels que 0 ≤ s_{k} ≤ γ(k − 1) si le kième pas de γ est une montée, 0 ≤ s_{k} ≤ γ(k − 1) (resp. 0 ≤ s_{k} ≤ γ(k − 1) − 1) si le kième pas de γ est une descente et 0 ≤ s_{k} ≤ 2γ(k − 1) + 1 (resp. 0 ≤ s_{k} ≤ 2γ(k − 1)) si le kième pas de γ est un palier.

(i) Il existe une bijection φ de l’ensemble Π_{n} sur l’ensemble des permutations S_{n+1}. (ii) Il existe une bijection φ′ de l’ensemble Π′_{n} sur l’ensemble des permutations σ ∈ S_{n+1} telles que σ(n + 1) = n + 1.

On identifie chaque permutation σ ∈ S_{n} au mot σ(1)σ(2) ⋯ σ(n). Rappelons qu’une valeur x = σ(i) est un pic (resp. un creux, une double montée, une double descente) de σ, si σ(i − 1) < σ(i) > σ(i + 1) (resp. σ(i − 1) > σ(i) < σ(i + 1), σ(i − 1) < σ(i) < σ(i + 1), σ(i − 1) > σ(i) > σ(i + 1)), où σ(0) = σ(n + 1) = 0.

Proposition 3 ([8, 12]) Soit (γ, s_{1}s_{2} … s_{n}) un chemin marqué et σ ∈ S_{n+1} sa permutation correspondante par la bijection φ ou φ′. Alors

(i) les creux (resp. pics, doubles montées et doubles descentes) de σ correspondent aux montées (resp. descentes, paliers) de (γ, s).

(ii) Un entier k ∈ [n] est un record de σ ssi le kième pas de γ est une descente ou un palier et s_{k} = 0.

Comme une permutation alternante de [2n+1] n’a pas de double montée ni de double descente, le chemin correspondant n’a donc pas de palier, i.e., c’est un chemin de Dyck. Notons que dans un chemin de Dyck γ = (γ(0), γ(1), …, γ(n)), le niveau γ(k−1) et la position k du pas (γ(k−1), γ(k)) sont toujours de parités opposées. On en déduit donc la

Proposition 4 Soit (γ, s_{1}s_{2} … s_{2n}) un chemin marqué et σ ∈ A_{2n+1} sa permutation correspondante par la bijection φ ou φ′. L’entier k ∈ [2n] est un record pair (resp. impair) de σ ssi le kième pas de γ est une descente de niveau impair (resp. pair) et s_{k} = 0.

On est maintenant en mesure de démontrer le théorème 2. Soit (γ, s) un chemin marqué, on associe à chaque pas marqué ((γ(k − 1), γ(k)), s_{k}) la valuation 1 si (γ(k − 1), γ(k)) est une montée ou une descente et s_{k} > 0 ; x (resp. y) si (γ(k − 1), γ(k)) est une descente de niveau impair (resp. pair) et s_{k} = 0, et 0 si (γ(k − 1), γ(k)) est un palier. On définit la valuation du chemin marqué (γ, s_{1}s_{2} … s_{n}) par le produit des valuations de tous ses pas marqués ((γ(k − 1), γ(k)), s_{k}), 1 ≤ k ≤ n. On constate que la somme des valuations ci-dessus des chemins marqués de Π_{n} est égale à celle des chemins de n pas avec les paramètres suivants :

a_{k−1} = k, b_{k−1} = 0, c_{2k−1} = x + 2k − 1 et c_{2k} = y + 2k, (k ≥ 1);

et que celle des chemins marqués de Π′_{n} est égale à celle des chemins de n pas avec les paramètres :

a_{k−1} = k, b_{k} = 0, c_{2k−1} = x + 2k − 2 et c_{2k} = y + 2k − 1, (k ≥ 1).

Par ailleurs, comme 2n+1 est toujours un record impair de σ ∈ A_{2n+1} et que les permutations σ ∈ S_{2n} peuvent être considérées comme des permutations de S_{2n+1} avec σ(2n + 1) = 2n + 1, compte tenu des propositions 3 et 4, les valuations des chemins marqués de Π_{2n} et Π′_{2n} correspondent respectivement aux polynômes

∑_{σ∈A_{2n+1}} x^{recp σ}y^{reci σ−1} et  ∑_{σ∈A_{2n}} x^{recp σ}y^{reci σ}.

Par application de la proposition 2, on obtient d’après (4) que

∑_{n≥0} y^{−1}f_{2n+1}(x, y)t^{2n} = \frac{1}{1 − \frac{1(x + 1)t^{2}}{1 − \frac{2(y + 2)t^{2}}{1 − \frac{3(x + 3)t^{2}}{1 − \frac{4(y + 4)t^{2}}{...}}}}} ,

et

∑_{n≥0} f_{2n}(x, y)t^{2n} = \frac{1}{1 − \frac{1xt^{2}}{1 − \frac{2(y + 1)t^{2}}{1 − \frac{3(x + 2)t^{2}}{1 − \frac{4(y + 3)t^{2}}{...}}}}} ·

Ceci achève la démonstration du théorème 2.

4 Quelques remarques pour conclure

(I) On se propose d’abord de trouver une formule explicite pour C_{n}(x, y).

Proposition 5 On a

C_{n}(x, y) = ∑_{j=0}^{n} ∑_{k=0}^{j}(−1)^{n−k} \frac{(\frac{x+y}{2} + 2k)(\frac{x}{2})_{j}(\frac{y+1}{2})_{j}}{k!(j − k)!(\frac{x+y}{2} + k)_{j+1}} (x + 2k)^{n}(y + 2k)^{n}.

Démonstration. Pour tout j ≥ 0, posons

\frac{2^{2j}t^{j}}{∏_{l=0}^{j}[1 + (x + 2l)(y + 2l)t]} = ∑_{k=0}^{j} \frac{α_{k}(j)}{1 + (x + 2k)(y + 2k)t}·

On voit facilement que

α_{k}(j) = \frac{(−1)^{k}(\frac{x+y}{2} + 2k)}{k!(j − k)!(\frac{x+y}{2} + k)_{j+1}} , 0 ≤ k ≤ j.

Or, d’après la Proposition 1, le polynôme C_{n}(x, y) est le cœfficient de t^{n} dans le développement de

∑_{j=0}^{n} \frac{2^{2j}(\frac{x}{2})_{j}(\frac{y+1}{2})_{j}t^{j}}{∏_{l=0}^{j}[1 + (x + 2l)(y + 2l)t]} = ∑_{j=0}^{n} ∑_{k=0}^{j} \frac{α_{k}(j)(\frac{x}{2})_{j}(\frac{y+1}{2})_{j}}{1 + (x + 2k)(y + 2k)t}·

D’où le résultat.

(II) Il est facile de voir que le degré de C_{n}(x, y) est égal à n. Soit M_{n}(x, y) la somme des monômes de plus haut degré dans C_{n}(x, y). Rappelons que, si σ ∈ S_{n}, σ(i) est un pic de cycle de σ si i < σ(i) > σ^{2}(i). Notons p(σ) (resp. i(σ)) le nombre de pics de cycle pairs (resp. impairs) de σ et Inv(2n) l’ensemble des involutions sans point fixe de [2n].

Proposition 6 On a, pour tout n ≥ 1,

M_{n}(x, y) = ∑_{σ} x^{p(σ)}y^{i(σ)} (σ ∈ Inv(2n)).

Démonstration. A chaque permutation σ ∈ A_{2n} on associe l’involution σ′ de Inv(2n) définie par

σ′(σ(2i − 1)) = σ(2i),  σ′(σ(2i)) = σ(2i − 1),  (i ∈ [n]).

Si σ a n records, le nombre de ses records pairs (resp. impairs) est égal au nombre de pics de cycle pairs (resp. impairs) de σ′. De plus l’application σ → σ′ est une bijection de l’ensemble des permutations alternantes de [2n] ayant n records sur l’ensemble Inv(2n). On en déduit alors le résultat.

Pour tout polynôme p(x, y) en les variables x, y on définit l’opérateur D :

D(p(x, y)) = la somme des monômes de degré plus haut de p(x, y).

On a donc

M_{n}(x, y) = D(C_{n}(x, y)).  (7)

On remarque d’autre part que

D [(x + 2)^{l}(y + 2)^{m} − x^{l}y^{m}] = 2(lx^{l−1}y^{m} + mx^{l}y^{m−1})
= 2(\frac{∂}{∂x} + \frac{∂}{∂y})x^{l}y^{m}.

où l, m sont deux entiers positifs. D’où et par la linéarité de D,

D [C_{n}(x + 2, y + 2) − C_{n}(x, y)] = 2(\frac{∂}{∂x} + \frac{∂}{∂y})M_{n}(x, y).

De même on a

D [xC_{n−1}(x + 2, y + 2)] = xM_{n−1}(x, y).

On déduit donc de (1) la relation de récurrence pour M_{n}(x, y) suivante, due à Dumont [4].

Corollaire 4 Les polynômes M_{n}(x, y) satisfont la relation de récurrence :

\{ \begin{matrix}M_{1}(x, y) & = & x, \\ M_{n}(x, y) & = & 2xy(\frac{∂}{∂x} + \frac{∂}{∂y})M_{n−1}(x, y) + xM_{n−1}(x, y). \end{matrix}  (8)

Du théorème 1 on déduit immédiatement d’après (7) un autre résultat de Dumont [4].

Corollaire 5 La série génératrice ordinaire des polynômes M_{n}(x, y) admet le développement en fraction continue formelle suivant :

∑_{n≥0} M_{n}(x, y)t^{n} = \frac{x}{1 − \frac{1xt}{1 − \frac{2yt}{1 − \frac{3xt}{1 − \frac{4yt}{...}}}}} ·

(III) Les permutations alternantes considérées plus haut sont parfois appelées permutations “down-up”. On peut aussi envisager des extensions analogues pour les permutations “up-down”, i.e., les permutations σ ∈ S_{n} satisfaisant

σ(1) < σ(2), σ(2) > σ(3), σ(3) < σ(4), · · · .

Soit B_{n} l’ensemble des permutations “up-down” sur [n]. On pose

E_{2n+1}(x) = ∑_{σ∈B_{2n+1}} x^{rec σ}.

Carlitz et Scoville [3] ont déja montré par la méthode classique que

∑_{n≥0} E_{2n+1}(x)\frac{t^{2n+1}}{(2n + 1)!} = (sec t)^{x} ∫_{0}^{t}(sec u)^{−x}du.

Par la même méthode et en utilisant une astuce due à Strehl [10], on obtient

∑_{n≥1} E_{2n+1}(x)\frac{t^{2n}}{(2n)!} = x ∑_{n≥1} \frac{(x/2)_{n}}{(2n − 1)!!}(1 − cos 2t)^{n},  (9)

où (2n − 1)!! = 1 · 3 ⋯ (2n − 1). D’autre part, si l’on pose

\{ \begin{matrix}F_{1}(x) & = & 1, \\ F_{n+1}(x) & = & (x + 1)^{2}F_{n}(x + 1) − x^{2}F_{n}(x),  n ≥ 1, \end{matrix}  (10)

alors Carlitz [2] a déja démontré que

∑_{n≥1}(−1)^{n}F_{n}(x)\frac{t^{2n}}{(2n)!} = \frac{1}{x} ∑_{n≥1}(−1)^{n} \frac{(x)_{n}n!}{(2n)!}(e^{t/2} − e^{−t/2})^{2n}.  (11)

On déduit donc de (9) et (11) que

E_{2n+1}(x) = 2^{2n−1}x^{2}F_{n}(x/2),  n ≥ 1.  (12)

Remarque. Viennot [11] a obtenu cette dernière identité d’une façon combinatoire en s’appuyant sur un résultat de Strehl [10]. Comme E_{1}(x) = x, les identités (10) et (12) impliquent que

\{ \begin{matrix}E_{1}(x) & = & x, \\ E_{2n+1}(x) & = & x^{2}E_{2n−1}(x + 2) − x^{2}E_{2n−1}(x),  (n ≥ 1). \end{matrix}  (13)

D’où et en appliquant le lemme 2 on obtient la proposition suivante.

Proposition 7 On a

∑_{n≥0} E_{2n+1}(x)t^{2n+1} = \frac{xt}{1 − \frac{2xt^{2}}{1 − \frac{2(x + 2)t^{2}}{1 − \frac{4(x + 2)t^{2}}{1 − \frac{4(x + 4)t^{2}}{...}}}}} ·

(IV) On peut aussi considérer le problème analogue pour toutes les permutations de [n]. Posons g_{n}(x, y) = ∑_{σ∈S_{n}} x^{recp σ}y^{reci σ}.

Proposition 8 Les polynômes g_{n}(x, y) ont l’expression explicite suivante :

g_{2n}(x, y) = x(y + 1) ⋯ (x + 2n − 2)(y + 2n − 1),
g_{2n+1}(x, y) = y(x + 1) ⋯ (y + 2n − 2)(x + 2n − 1)(y + 2n).

Démonstration. Il suffit en effet de montrer que g_{n+1}(x, y) = (y +n)g_{n}(y, x). Pour ce faire, on va exhiber une bijection entre [n + 1] × S_{n} et S_{n+1}. Étant donné (k, σ) ∈ [n + 1] × S_{n}, on construit la permutation σ′ de S_{n+1} de la façon suivante :

σ′(i) = \{ \begin{matrix}σ(i) + 1 & si 1 ≤ i ≤ k − 1, \\ 1 & si i = k, \\ σ(i − 1) + 1 & si k + 1 ≤ i ≤ n + 1. \end{matrix}

Il est facile de voir que si k = 1, alors recp(σ′) = reci(σ) et reci(σ′) = recp(σ) + 1 ; sinon recp(σ′) = reci(σ) et reci(σ′) = recp(σ). Ceci explique la relation de récurrence g_{n+1}(x, y) = (y + n)g_{n}(y, x).

Références

[1] André (D.), Développements de sec x et tg x, C. R. Acad. Sci. Paris, 88 (1879), 965-967.

[2] Carlitz (L.), Explicit formulas for the Dumont-Foata polynomials, Disc. Math., 30 (1980), 211-225.

[3] Carlitz (L.) et Scoville (R.), Enumeration of up-down permutations by upper records, Monats. für Math., 79 (1975), 3-12.

[4] Dumont (D.), Pics de cycle et dérivées partielles, Actes du séminaire lotharingien de Combinatoire, 13ième session, 1985, Publication IRMA, Strasbourg.

[5] Dumont (D.) et Randrianarivony (A.), Sur une extension des nombres de Genocchi, Europ. J. Combinatorics, 16 (1994), 147-151.

[6] Flajolet (P.), Combinatorial aspects of continued fractions, Disc. Math., 41 (1982), 145-153.

[7] Foata (D.) et Schützenberger (M. P.), Théorie géométrique des polynômes euleriens, Lecture Notes in Math., Vol. 138, Springer Verlag, Berlin, 1970.

[8] Françon (J.) et Viennot (G.), Permutations selon les pics, creux, doubles montées, doubles descentes, nombres d’Euler, nombres de Genocchi, Disc. Math. 28 (1979), 21-35.

[9] Stieltjes (T. J.), Sur la réduction en fraction continue d’une série procédant suivant les puissances décroissantes d’une variable, Ann. Fac. Sc. Toulouse, 3 (1889), 1-17.

[10] Strehl (V.), Alternating permutations and modified Ghandi-polynomials, Disc. Math., 28( 1979), 89-100.

[11] Viennot (G.), Interprétations combinatoires des nombres d’Euler et de Genocchi, Séminaire de Théorie des nombres, 1980/1981, exposé n^{∘} 11, Publication de l’Univ. Bordeaux I.

[12] Viennot (G.), Une théorie combinatoire des polynômes orthogonaux généraux, Note de conférence à l’Université du Québec à Montréal, 1983.

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

[14] Zeng (J.), Énumération de permutations et J-fractions continues, Europ. J. Combinatorics, 14 (1993), 373-382.

Département de Mathématiques Université Louis-Pasteur 7, rue René Descartes 67084 Strasbourg Cedex, France