POLYNÔMES DE DUMONT-FOATA GÉNÉRALISÉS

par

Arthur RANDRIANARIVONY (^{∗})

Abstract. — We study a sequence of polynomials with six variables which is an extension of Dumont-Foata polynomials. In particular we prove the three recent Dumont conjectures on the ternary symmetries related to Genocchi numbers [D].

1 Introduction

Les nombres de Genocchi (G_{2n})_{n≥1} peuvent être définis par la fonction génératrice exponentielle :

G(t) = \frac{2t}{e^{t} + 1} = t + ∑_{n≥1}(−1)^{n}G_{2n} \frac{t^{2n}}{(2n)!}·

DUMONT et FOATA ont donné un raffinement de ces nombres [DF]. Ils ont introduit les polynômes F_{n}(x, y, z) dits de Dumont-Foata et définis par la récurrence :

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

et en ont donné une interprétation combinatoire en termes d’escaliers.

Rappelons qu’un escalier F de taille n est le graphe d’une application surjective f de {1, 2, …, 2n} sur {2, 4, …, 2n} et excédante, i.e, f(k) ≥ k pour tout k. Un point (k, f(k)) de F est dit maximal si f(k) = 2n, fixe (resp. surfixe, saillant) s’il n’est maximal et si f(k) = k (resp. f(k) = k + 1, pour tout j < i, f(j) < f(i)). On note max(F) le nombre de points maximaux de F à l’exception des points (2n − 1, 2n) et (2n, 2n), fix(F) (resp. sur(F), sai(F)) le nombre de ses points fixes (resp. surfixes, saillants).

TH^{}ÉOR^{}ÈME 1 (Dumont-Foata). — On a, pour tout n ≥ 1, l’identité :

F_{n}(x, y, z) = ∑_{F} x^{max(F)}y^{fix(F)}z^{sai(F)}

où la sommation est étendue à tous les escaliers F de taille n.

De plus, F_{n}(x, y, z) est symétrique en les variables x, y, z et que F_{n}(1, 1, 1) = G_{2n+2}.

Récemment HAN Guo Niu [H] a trouvé plusieurs interprétations de ces polynômes. On lui doit d’avoir établi le théorème suivant.

(^{∗}) Avec le concours du programme des Communautés Européennes en Combinatoire Algébrique, 1994-95.

TH^{}ÉOR^{}ÈME 2. — On a :

F_{n}(x, y, z) = ∑_{F} x^{max(F)}y^{fix(F)}z^{sur(F)}

où la sommation est étendue à tous les escaliers F de taille n.

Dans ce travail, nous allons étudier une suite de polynômes Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) qui raffinent les F_{n}(x, y, z).

Étant donné un escalier F de taille n, un point (k, f(k)) de F est dit doublé s’il existe j ≠ k tel que f(j) = f(k). On note respectivement mi(F) et mp(F)) le nombre de ses points maximaux d’abscisses impaires et maximaux d’abscisses paires à l’exception des points (2n − 1, 2n) et (2n, 2n), fd(F) et fnd(F) le nombre de ses points fixes doublés et fixes non doublés, sd(F) et snd(F) le nombre de ses points surfixes doublés et surfixes non doublés. On doit à DUMONT [D] d’avoir défini combinatoirement les polynômes Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) par

Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) = ∑ x^{mi(F)}y^{fd(F)}z^{snd(F)}\overline{x}^{mp(F)}\overline{y}^{fnd(F)}\overline{z}^{sd(F)}

où la sommation est étendue à tous les escaliers F de taille n.

Considérons à présent la fraction continue formelle suivante :

Γ(x, y, z, \overline{x}, \overline{y}, \overline{z}; t) = \frac{t}{1 − (x\overline{y} + y\overline{z} + z\overline{x})t − \frac{(\overline{x} + y)(\overline{y} + z)(\overline{z} + x)t^{2}}{...}}

dont le cœfficient situé sous le (n + 1)-ième trait de fraction est

1 − [(x + n)(\overline{y} + n) + (y + n)(\overline{z} + n) + (z + n)(\overline{x} + n) − n(n + 1)]t

−\frac{(n + 1)(\overline{x} + y + n)(\overline{y} + z + n)(\overline{z} + x + n)t^{2}}{...} ·

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

TH^{}ÉOR^{}ÈME 3. — Les polynômes Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) sont définis par la récurrence :

(2) \{ \begin{matrix}Γ_{1}(x, y, z, \overline{x}, \overline{y}, \overline{z}) & = & 1, \\ Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) & = & (x + \overline{z})(y + \overline{x})Γ_{n−1}(x + 1, y, z, \overline{x} + 1, \overline{y}, \overline{z}) \\ +[x(\overline{y} − y) − \overline{x}(\overline{z} − z) − x\overline{x}]Γ_{n−1}(x, y, z, \overline{x}, \overline{y}, \overline{z}), (n ≥ 2). \end{matrix}

TH^{}ÉOR^{}ÈME 4. — On a la représentation suivante :

Γ(x, y, z, \overline{x}, \overline{y}, \overline{z}; t) =

∑_{n≥1} \frac{(x + \overline{z})_{n−1}(y + \overline{x})_{n−1}t^{n}}{∏_{o≤k≤n−1}[1 − ((x + k)(\overline{y} − y) − (\overline{x} + k)(\overline{z} − z) − (x + k)(\overline{x} + k))t]}

où on note (a)_{o} = 1 et, pour j ≥ 1, (a)_{j} = a(a + 1)(a + 2) ⋯ (a + j − 1).

TH^{}ÉOR^{}ÈME 5 (2-ième conjecture de Dumont). — Le développement selon les puissances croissantes de la fraction continue Γ(x, y, z, \overline{x}, \overline{y}, \overline{z}; t) est la série génératrice ordinaire des polynômes Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}).

Remarque : Par un calcul analogue à celui de Carlitz [C2], on déduit du Théorème 4 la formule explicite suivante :

\begin{matrix}Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) \\ = ∑_{l=1}^{n} \frac{1}{(l − 1)!}(x + 1)_{l−1}(y + 1)_{l−1} ∑_{k=0}^{l−1}(−1)^{k}\binom{l − 1}{k}\frac{(x + y − z + \overline{x} − \overline{y} + \overline{z} + 2k)}{(x + y − z + \overline{x} − \overline{y} + \overline{z} + k)_{l}} _{k}^{n} \end{matrix}

où _{k} = ((x + k)(\overline{y} − y) − (\overline{x} + k)(\overline{z} − z) − (x + k)(\overline{x} + k)).

D’abord, le Théorème 5 nous fournit les propriétés des polynômes Γ_{n} suivantes :

COROLLAIRE 6. — Pour toute permutation circulaire (u, v, w) de (x, y, z), on a les identités :

Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) = Γ_{n}(u, v, w, \overline{u}, \overline{v}, \overline{w}) = Γ_{n}(\overline{u}, \overline{w}, \overline{v}, u, w, v).

On voit que F_{n}(x, y, z) = Γ_{n}(x, y, z, x, y, z) est symétrique en x, y et z. En outre, on tire également du Théorème 5 la 1-ière conjecture de Dumont suivante.

COROLLAIRE 7. — La série génératrice ordinaire des polynômes F_{n}(x, y, z) admet le développement en fraction continue formelle :

∑_{n≥1} F_{n}(x, y, z)t^{n} = \frac{t}{1 − (xy + yz + zx)t − \frac{(x + y)(y + z)(z + x)t^{2}}{...}}

dont le cœfficient situé sous le (n+1)-ième trait de fraction est

1 − [(x + n)(y + n) + (y + n)(z + n) + (z + n)(x + n) − n(n + 1)]t

−\frac{(n + 1)(x + y + n)(y + z + n)(z + x + n)t^{2}}{...} ·

Sa 3-ième conjecture résulte des Théorèmes 4 et 5.

COROLLAIRE 8 (3-ième conjecture). — Soit G_{n}(x, y, z) les polynômes définis combinatoirement par

G_{n}(x, y, z) = ∑ x^{mi(F)}y^{fd(F)}z^{snd(F)}

où la sommation est étendue à tous les escaliers F de taille n.

Alors la série génératrice ordinaire de ces polynômes admet la représentation suivante :

G(x, y, z; t) = ∑_{n≥1} \frac{(x + 1)_{n−1}(y + 1)_{n−1}t^{n}}{∏_{0≤k≤n−1}[1 + ((x + k)(y + k) − (k + 1)(z − 1))t]}·

Comme autre cas particulier, en remplaçant y, z, \overline{y}, \overline{z} par 1 puis \overline{x} par y dans le Théorème 3, nous retrouvons les polynômes de Dumont à deux variables B_{n}(x, y) étudiés dans [DR2]. En outre, grce aux propriétés de la fraction continue formelle Γ(x, y, z, \overline{x}, \overline{y}, \overline{z}; t) et compte-tenu du Théorème 5, on a les identités suivantes :

\begin{aligned}B_{n}(x, y) & = Γ_{n}(x, 1, 1, y, 1, 1) = Γ_{n}(1, x, 1, 1, y, 1) \\ & = Γ_{n}(1, 1, x, 1, 1, y) = Γ_{n}(x, y, 1, 1, 1, 1) = Γ_{n}(1, 1, 1, x, y, 1). \end{aligned}

Ce qui nous donne le résultat suivant.

COROLLAIRE 9. — On a, pour tout n ≥ 1, les identités :

B_{n}(x, y) = ∑ x^{mi(F)}y^{mp(F)} = ∑ x^{fd(F)}y^{fnd(F)} = ∑ x^{sd(F)}y^{snd(F)}
= ∑ x^{mi(F)}y^{fd(F)} = ∑ x^{mp(F)}y^{fnd(F)}

où les sommations sont étendues à tous les escaliers F de taille n.

Remarque : La 1-ière égalité a été déjà établie dans [DR2].

D’autres interprétations combinatoires pour les nombres de Genocchi G_{2n} et les nombres de Genocchi médians H_{2n+1} s’en déduisent. Rappelons tout d’abord que les nombres de Genocchi médians H_{2n+1} sont définis comme suit : Soit (g_{k,n}) la matrice de Seidel associée aux nombres de Genocchi G_{2n} , i.e, les g_{k,n} sont définis par la récurrence :

\{ \begin{matrix}g_{0,0} & = & 0, g_{0,1} = 1, g_{0,2n} = (−1)^{n}G_{2n}, g_{0,2n+1} = 0,  (n ≥ 1) \\ g_{k,n} & = & g_{k−1,n} + g_{k−1,n+1},  (k ≥ 1). \end{matrix}

On définit les nombres de Genocchi médians par H_{2n+1} = (−1)^{n}g_{n,n+1} [B].

Considérons alors les polynômes de Gandhi Q_{n}(x) et de Dumont H_{n}(x) définis par

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

\{ \begin{matrix}H_{1}(x) & = & x, \\ H_{n}(x) & = & x(x + 1)[H_{n−1}(x + 1) − H_{n−1}(x)],  (n ≥ 2). \end{matrix}

En comparant avec la récurrence définissant les B_{n}(x, y), on a :

Q_{n−1}(x) = B_{n}(x − 1, x − 1) et H_{n+1}(x) = x(x + 1)B_{n}(x, x + 1) (n ≥ 1).

GANDHI a conjecturé que Q_{n}(1) = G_{2n+2} et cette conjecture a été démontrée par CARLITZ [C1], et par RIORDAN et STEIN [RS]. D’autre part, nous avons démontré dans [DR1] que H_{n}(1) = H_{2n+1}. En appliquant ainsi le corollaire 9 et en remarquant que 2B_{n}(1, 2) = B_{n+1}(0, 1), on obtient les interprétations suivantes.

COROLLAIRE 10

(i) G_{2n} est égal au nombre d’escaliers de taille n sans point fixe (resp. surfixe).

(ii) H_{2n+1} est égal au nombre d’escaliers de taille n dont tous les points fixes (resp. surfixes)sont non doublés.

(iii) H_{2n+1} est égal au nombre d’escaliers de taille n dont tous les points maximaux, à l’exception du point (2n − 1, 2n) (resp. (2n, 2n)) sont d’abscisses paires (resp. impaires).

Nous démontrons les théorèmes 3, 4 et 5 respectivement aux paragraphes 2, 3 et 4.

2. Caractérisation des polynômes Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}).

Notons E_{n} l’ensemble de tous les escaliers de taille n et considérons l’application restriction r : E_{n} → E_{n−1}, F ↦ G = r(F) telle que, pour tout i ∈ [2n − 2], g(i) = inf(f(i), 2n − 2).

Si i (resp. p) est le nombre de points maximaux d’abscisses impaires (resp. paires) de F, le nombre l (resp. m) de points maximaux d’abscisses impaires (resp. paires) de G est au moins égal à i − 1 (resp. p − 1) et de plus l + m ≥ i + p − 1. D’autre part, le nombre de points fixes (resp. surfixes) de G dépend de la position du point d’abscisse 2n − 2 (resp. 2n − 3) de F (voir Fig. 1, par exemple). 6 cas sont à distinguer.

(1) Si (2n − 3, 2n) et (2n − 2, 2n) sont des points maximaux de F, alors

mi(G) ≥ mi(F) − 1, fd(G) = fd(F), snd(G) = snd(F),
mp(G) ≥ mp(F) − 1, mi(G) + mp(G) ≥ mi(F) + mp(F) − 1,
fnd(G) = fnd(F), sd(G) = sd(F).

(2) Si (2n − 3, 2n − 2) et (2n − 2, 2n − 2) sont respectivement des points surfixe et fixe de F, alors

mi(G) ≥ mi(F), fd(G) = fd(F) − 1, snd(G) = snd(F),
mp(G) ≥ mp(F), fnd(G) = fnd(F), sd(G) = sd(F) − 1.

(3) Si (2n − 3, 2n) est un point maximal de F et (2n − 2, 2n − 2) un point fixe non doublé, alors

mi(G) = mi(F) − 1, fd(G) = fd(F), snd(G) = snd(F),
mp(G) = mp(F), fnd(G) = fnd(F) − 1, sd(G) = sd(F).

(4) Si (2n − 3, 2n) est un point maximal de F et (2n − 2, 2n − 2) un point fixe doublé, alors

mi(G) ≥ mi(F) − 1, fd(G) = fd(F) − 1, snd(G) = snd(F),
mp(G) ≥ mp(F), mi(G) + mp(G) ≥ mi(F) + mp(F),
fnd(G) = fnd(F), sd(G) = sd(F).

(5) Si (2n − 2, 2n) est un point maximal de F et (2n − 3, 2n − 2) un point surfixe non doublé, alors

mi(G) = mi(F), fd(G) = fd(F), snd(G) = snd(F) − 1,
mp(G) = mp(F) − 1, fnd(G) = fnd(F) − 1, sd(G) = sd(F).

(6) Si (2n − 2, 2n) est un point maximal de F et (2n − 3, 2n − 2) un point surfixe doublé, alors

mi(G) ≥ mi(F), fd(G) = fd(F), snd(G) = snd(F),
mp(G) ≥ mp(F) − 1, mi(G) + mp(G) ≥ mi(F) + mp(F),
fnd(G) = fnd(F), sd(G) = sd(F) − 1.

Notons E_{n,i,j,k,p,q,r} le sous-ensemble de E_{n} formé des escaliers F tels que

mi(F) = i − 1, fd(F) = j, snd(F) = k, mp(F) = p − 1, fnd(F) = q, sd(F) = r,

E_{n}^{(l)} l’ensemble des F ∈ E_{n,i,j,k,p,q,r} vérifiant la condition (l) ci-dessus (l = 1, 2, …, 6).

Réciproquement, soit G un escalier de taille n − 1. Un antécédent F de G dans E_{n,i,j,k,p,q,r} par l’ application r est entièrement déterminé par le choix des points maximaux de G qu’on remonte sur la ligne 2n pour qu’ils soient des points maximaux de F (voir par exemple Fig. 2 et 3). D’après ce qui précède,

(i) si G ∈ E_{n−1,l,j,k,m,q,r}(l ≥ i − 1, m ≥ p − 1, l + m ≥ i + p − 1), F ∈ E_{n}^{(1)} et par suite le nombre d’antécédents de G est égal au nombre de façons de choisir i − 2 points parmi ses l − 1 points maximaux d’abscisses impaires ≠ 2n − 3 et p − 2 points parmi ses m − 1 points maximaux d’abscisses paires ≠ 2n − 2, soit \binom{l−1}{i−2}\binom{m−1}{p−2} antécédents. Par suite

|E_{n}^{(1)}| = ∑_{l+m≥i+p−1} \binom{l − 1}{i − 2}\binom{m − 1}{p − 2}|E_{n−1,l,j,k,m,q,r}|.

(ii) si G ∈ E_{n−1,l,j−1,k,m,q,r−1}(l ≥ i, m ≥ p), F ∈ E_{n}^{(2)}. Par conséquent, G admet \binom{l−1}{i−1}\binom{m−1}{p−1} antécédents. D’où

|E_{n}^{(2)}| = ∑_{l,m} \binom{l − 1}{i − 1}\binom{m − 1}{p − 1}|E_{n−1,l,j−1,k,m,q,r−1}|.

(iii) si G ∈ E_{n−1,i−1,j,k,p,q−1,r}, F ∈ E_{n}^{(3)}. Dans ce cas, G n’a qu’un seul antécédent. Par suite

|E_{n}^{(3)}| = |E_{n−1,i−1,j,k,p,q−1,r}|.

(iv) si G ∈ E_{n−1,l,j−1,k,m,q,r}(l ≥ i − 1, m ≥ p, l + m ≥ i + p), alors F ∈ E_{n}^{(4)}. Ainsi G a \binom{l−1}{i−2}\binom{m−1}{p−1} antécédents (Fig 2). Par suite

|E_{n}^{(4)}| = ∑_{l+m≥i+p} \binom{l − 1}{i − 2}\binom{m − 1}{p − 1}|E_{n−1,l,j−1,k,m,q,r}|.

(v) si G ∈ E_{n−1,i,j,k−1,p−1,q,r}, elle n’a qu’un seul antécédent F qui appartient à E_{n}^{(5)}. D’où :

|E_{n}^{(5)}| = |E_{n−1,i,j,k−1,p−1,q,r}|.

(vi) si G ∈ E_{n−1,l,j,k,m,q,r−1}(l ≥ i, m ≥ p − 1, l + m ≥ i + p), F ∈ E_{n}^{(6)} et G admet \binom{l−1}{i−1}\binom{m−1}{p−2} antécédents (Fig 3). On a alors :

|E_{n}^{(6)}| = ∑_{l+m≥i+p} \binom{l − 1}{i − 1}\binom{m − 1}{p − 2}|E_{n−1,l,j,k,m,q,r−1}|.

Puisque |E_{n,i,j,k,p,q,r}| = |E_{n}^{(1)}| + |E_{n}^{(2)}| + ⋯ + |E_{n}^{(6)}|, on a l’identité suivante :

|E_{n,i,j,k,p,q,r}| = ∑_{l,m} \binom{l−1}{i−2}\binom{m−1}{p−2}|E_{n−1,l,j,k,m,q,r}| − |E_{n−1,i−1,j,k,p−1,q,r}|

+ ∑_{l,m} \binom{l−1}{i−1}\binom{m−1}{p−1}|E_{n−1,l,j−1,k,m,q,r−1}| + |E_{n−1,i−1,j,k,p,q−1,r}|

+ ∑_{l,m} \binom{l−1}{i−2}\binom{m−1}{p−1}|E_{n−1,l,j−1,k,m,q,r}| − |E_{n−1,i−1,j−1,k,p,q,r}|

+|E_{n−1,i,j,k−1,p−1,q,r}|

+ ∑_{l,m} \binom{l−1}{i−1}\binom{m−1}{p−2}|E_{n−1,l,j,k,m,q,r−1}| − |E_{n−1,i,j,k,p−1,q,r−1}|.

Comme Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) = ∑ |E_{n,i,j,k,p,q,r}|x^{i−1}y^{j}z^{k}\overline{x}^{p−1}\overline{y}^{q}\overline{z}^{r}, alors nous avons :

Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) = x\overline{x} ∑ |E_{n−1,l,j,k,m,q,r}|(x + 1)^{l−1}y^{j}z^{k}(\overline{x} + 1)^{m−1}\overline{y}^{q}\overline{z}^{r}

− ∑ |E_{n−1,i−1,j,k,p−1,q,r}|x^{i−1}y^{j}z^{k}\overline{x}^{p−1}\overline{y}^{q}\overline{z}^{r}

+ ∑ |E_{n−1,l,j−1,k,m,q,r−1}|(x + 1)^{l−1}y^{j}z^{k}(\overline{x} + 1)^{m−1}\overline{y}^{q}\overline{z}^{r}
+ ∑ |E_{n−1,i−1,j,k,p,q−1,r}|x^{i−1}y^{j}z^{k}\overline{x}^{p−1}\overline{y}^{q}\overline{z}^{r}
+x ∑ |E_{n−1,l,j−1,k,m,q,r}|(x + 1)^{l−1}y^{j}z^{k}(\overline{x} + 1)^{m−1}\overline{y}^{q}\overline{z}^{r}
− ∑ |E_{n−1,i−1,j−1,k,p,q,r}|x^{i−1}y^{j}z^{k}\overline{x}^{p−1}\overline{y}^{q}\overline{z}^{r}
+ ∑ |E_{n−1,i,j,k−1,p−1,q,r}|x^{i−1}y^{j}z^{k}\overline{x}^{p−1}\overline{y}^{q}\overline{z}^{r}
+\overline{x} ∑ |E_{n−1,l,j,k,m,q,r−1}|(x + 1)^{l−1}y^{j}z^{k}(\overline{x} + 1)^{m−1}\overline{y}^{q}\overline{z}^{r}
− ∑ |E_{n−1,i,j,k,p−1,q,r−1}|x^{i−1}y^{j}z^{k}\overline{x}^{p−1}\overline{y}^{q}\overline{z}^{r},

soit

Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) = (x + \overline{z})(y + \overline{x})Γ_{n−1}(x + 1, y, z, \overline{x} + 1, \overline{y}, \overline{z}) +(x(\overline{y} − y) − \overline{x}(\overline{z} − z) − x\overline{x})Γ_{n−1}(x, y, z, \overline{x}, \overline{y}, \overline{z}).

On obtient ainsi le théorème 3.

3. Démonstration du théorème 4. Soit (a_{n,k}) et (b_{n,k}) deux suites de polynômes définies respectivement par :

(3)  \{ \begin{matrix}a_{0,k} & = & 1, \\ a_{n,k} & = & [(x + k)(\overline{y} − y) − (\overline{x} + k)(\overline{z} − z) − (x + k)(\overline{x} + k)]a_{n−1,k} \\ & +(x + \overline{z} + k)(y + \overline{x} + k)a_{n−1,k+1}, \end{matrix}

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

LEMME 9. — On a :

(5)  a_{n,k} = ∑_{0≤j≤k} \frac{k!}{(k − j)!}(\overline{y} + z)_{j}b_{n,j}.

Démonstration : Il est évident que le lemme est vrai pour n = 0. Supposons-le vrai pour n = i − 1 et montrons-le pour n = i.

polynômes de Dumont-Foata généralisés 9

L’hypothèse de récurrence et la relation (3) nous permettent d’écrire pour n = i :

a_{i,k} =(x + \overline{z} + k)(y + \overline{x} + k) ∑_{0≤j≤k+1} \frac{(k + 1)!}{(k + 1 − j)!}(\overline{y} + z)_{j}b_{i−1,j}
+[(x + k)(\overline{y} − y) − (\overline{x} + k)(\overline{z} − z) − (x + k)(\overline{x} + k)] ∑_{0≤j≤k} \frac{k!}{(k − j)!}(\overline{y} + z)_{j}b_{i−1,j}
= ∑_{0≤j≤k+1} \frac{k!}{(k + 1 − j)!}(\overline{y} + z)_{j}((k + 1)(x\overline{y} + y\overline{z} + z\overline{x} + k\overline{y} + kz)
− j((x + k)(\overline{y} − y) − (\overline{x} + k)(\overline{z} − z) − (x + k)(\overline{x} + k)))b_{i−1,j}.

Or, d’après la relation (4), le second membre de (5) devient pour n = i :

∑_{0≤j≤k} \frac{k!}{(k − j)!}(\overline{y} + z)_{j}b_{i,j} = ∑_{1≤j≤k} \frac{k!}{(k − j)!}(\overline{y} + z)_{j}b_{i−1,j−1}

+ ∑_{0≤j≤k} \frac{k!}{(k − j)!}(\overline{y} + z)_{j}

((x + j)(\overline{y} + j)

+ (y + j)(\overline{z} + j) + (z + j)(\overline{x} + j) − j(j + 1))b_{i−1,j}

+ ∑_{0≤j≤k} \frac{k!}{(k − j)!}(\overline{y} + z)_{j}(j + 1)(\overline{x} + y + j)(\overline{y} + z + j)(\overline{z} + x + j)b_{i−1,j+1}

= ∑_{0≤j≤k+1} \frac{k!}{(k + 1 − j)!}(\overline{y} + z)_{j}α_{j}b_{i−1,j}

où

\begin{matrix}α_{j} = & (k + 1)(x\overline{y} + y\overline{z} + z\overline{x} + k\overline{y} + kz) \\ − j[(x + k)(\overline{y} − y) − (\overline{x} + k)(\overline{z} − z) − (x + k)(\overline{x} + k)], \end{matrix}

ce qui achève la démonstration du lemme.

Posons maintenant, pour k ≥ 0,

A_{k}(t) = 1 + a_{1,k}t + a_{2,k}t^{2} + ⋯ + a_{n,k}t^{n} + ⋯

et

B_{k}(t) = t^{k} + b_{k+1,k}t^{k+1} + b_{k+2,k}t^{k+2} + ⋯ + b_{n,k}t^{n} + ⋯

D’après le lemme, on a :

(6)  A_{0}(t) = B_{0}(t).

Multiplions, d’autre part, les deux membres de (3) par t^{n} puis sommons sur n. Nous avons :

A_{k}(t) = \frac{1 + (x + \overline{z} + k)(y + \overline{x} + k)tA_{k+1}(t)}{1 − [(x + k)(\overline{y} − y) − (\overline{x} + k)(\overline{z} − z) − (x + k)(\overline{x} + k)]t}·

Par itération, on a :

(7) A_{0}(t) = ∑_{n≥0} \frac{(x + \overline{z})_{n}(y + \overline{x})_{n}t^{n}}{∏_{o≤k≤n}[1 − ((x + k)(\overline{y} − y) − (\overline{x} + k)(\overline{z} − z) − (x + k)(\overline{x} + k))t]}·

De l’autre côté, la récurrence (4) nous donne :

(1 − (x\overline{y} + y\overline{z} + z\overline{x})t)B_{0}(t) = 1 + (\overline{x} + y)(\overline{y} + z)(\overline{z} + x)tB_{1}(t)

et pour j ≥ 1

\begin{matrix}[1 − ((x + j)(\overline{y} + j) & + (y + j)(\overline{z} + j) + (z + j)(\overline{x} + j) − j(j + 1))t]B_{j}(t) = \\ tB_{j−1}(t) + (j + 1)(\overline{x} + y + j)(\overline{y} + z + j)(\overline{z} + x + j)tB_{j+1}(t). \end{matrix}

Par conséquent,

B_{0}(t) = \frac{1}{1 − (x\overline{y} + y\overline{z} + z\overline{x})t − (\overline{x} + y)(\overline{y} + z)(\overline{z} + x)t(B_{1}(t)/B_{0}(t))}

et pour j ≥ 1

\frac{B_{j}(t)}{B_{j−1}(t)} = \frac{t}{1 − β_{j}t − (j + 1)(\overline{x} + y + j)(\overline{y} + z + j)(\overline{z} + x + j)t\frac{B_{j+1}(t)}{B_{j}(t)}}

où β_{j} = (x + j)(\overline{y} + j) + (y + j)(\overline{z} + j) + (z + j)\overline{x} + j) − j(j + 1).

Par itération, on trouve B_{0}(t) = (1/t)Γ(x, y, z, \overline{x}, \overline{y}, \overline{z}; t).

Compte-tenu des relations (6) et (7), nous obtenons le théorème 4.

4. Démonstration du théorème 5

On déduit du théorème 4 la relation

\begin{aligned}[1 − (x(\overline{y} − y) − \overline{x}(\overline{z} − z) & − x\overline{x})t]Γ(x, y, z, \overline{x}, \overline{y}, \overline{z}; t) \\ & = t[1 + (x + \overline{z})(y + \overline{x})Γ(x + 1, y, z, \overline{x} + 1, \overline{y}, \overline{z}; t)]. \end{aligned}

En posant Γ(x, y, z, \overline{x}, \overline{y}, \overline{z}; t) = ∑_{n≥1} \overline{Γ}_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z})t^{n}, on a alors :

\begin{aligned}∑_{n≥1} \overline{Γ}_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z})t^{n} & = t + (x + \overline{z})(y + \overline{x}) ∑_{n≥1} \overline{Γ}_{n}(x + 1, y, z, \overline{x} + 1, \overline{y}, \overline{z})t^{n+1} \\ & + [x(\overline{y} − y) − \overline{x}(\overline{z} − z) − x\overline{x}] ∑_{n≥1} \overline{Γ}_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z})t^{n+1} \end{aligned}

En identifiant les cœfficients de t^{n} des deux membres de cette identité, on voit que \overline{Γ}_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) vérifie la même récurrence que Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}). Il s’ensuit que \overline{Γ}_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) = Γ_{n}(x, y, z, \overline{x}, \overline{y}, \overline{z}) pour tout n ≥ 1.

\begin{aligned}× & & & × & × & × & × \\ & & & × \\ & & & × \\ & & × & × \\ & × \\ & & & F ∈ E_{5,3,1,0,2,2,1} \end{aligned} ⟶ \begin{aligned}⊗ & & × & ⊗ & ⊗ \\ & & × \\ × & × \\ & × \\ & & G ∈ E_{4,3,1,0,1,2,1} \end{aligned}

Fig. 1

\begin{aligned}× & & & & & & × & & × & × \\ & & & & × & & & × \\ & & & & & × \\ & & × & × \\ & × \end{aligned} \begin{aligned}& & & & × & & × & & × & × \\ × & & & & & & & × \\ & & & & & × \\ & & × & × \\ & × \end{aligned}

Antécédents de G dans E_{,5,3,2,0,1,2,1}

Fig 2

\begin{aligned}× & & & & & & & × & × & × \\ & & & & × & & × \\ & & & & & × \\ & & × & × \\ & × \end{aligned} \begin{aligned}& & & & × & & & × & × & × \\ × & & & & & & × \\ & & & & & × \\ & & × & × \\ & × \end{aligned}

Antécédents de G dans E_{,5,2,1,0,2,2,2}

Fig 3

BIBLIOGRAPHIE

[B] D. BARSKY. — Congruences pour les nombres de Genocchi de deuxième espèce, Séminaire du groupe d’analyse ultramétrique, Paris, t. 34, 1981, p. 1-13.

[C1] L. CARLITZ. — A conjecture concerning Genocchi numbers, K. Norske Vid. Selsk. Sk., t. 9, 1972, p. 1-4.

[C2] L. CARLITZ. — Explicit formulas for the Dumont-Foata polynomials, Dis. Math., t. 30, 1980, p. 211-225.

[D] D. DUMONT. — Conjectures sur les symétries ternaires liées aux nombres de Genocchi, à paratre dans les Actes du 4-ème colloque de séries formelles et combinatoire algébrique, Publ. de l’UQAM, 1992.

[DF] D. DUMONT , D. FOATA. — Une propriété de symétrie des nombres de Genocchi, Bull. Soc. Math. Fr., t. 104, 1976, p. 433-451.

[DR1] D. DUMONT, A. RANDRIANARIVONY. — Dérangements et nombres de Genocchi, Discrete Math., vol. 132 (1994), pp. 37 − 49.

[DR2] D. Dumont—, A. RANDRIANARIVONY. — Sur une extension des nombres de

Genocchi, à paratre dans Europ. Journ. Combin.

[H] G.N HAN. — Symétries trivariées sur les nombres de Genocchi, Europ. J. Combinatorics, vol. 17 (1996), pp. 397 − 407.

[RS] J. Riordan—, P.R. STEIN. — Proof of a conjecture on Genocchi numbers, Disc. Math., t. 5, 1973, p. 381-388.

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