Publ. I.R.M.A. Strasbourg, Actes 24e Séminaire Lotharingien, 461/S-24, p.77-85, 1993.

Escaliers évalués et nombres classiques

Guo-Niu Han

I.R.M.A., CNRS et ULP 7, rue René-Descartes F-67084 Strasbourg

Résumé. — Nous établissons une involution sur l’ensemble des couples composés d’un escalier et d’une application sur cet escalier. En utilisant cette involution, on retrouve directement plusieurs d’identités sur les nombres classiques et leurs variations.

1. Introduction

Dans la théorie combinatoire des nombres de Genocchi, Dumont [Dum] a introduit la notion d’application surjective excédante ^{1}. Pour étudier les propriétés de symétrie trivariée des polynômes de Dumont-Foata, nous avons prolongé dans [Han] cette notion en étudiant les propriétés géométriques des escaliers évalués (ou escaliers gauches évalués). Il est remarquable de voir que si on choisit d’autres évaluations que celles qui étaient imposées par l’étude de ces polynômes, on retrouve un cadre géométrique commun pour l’étude de plusieurs familles de polynômes récemment introduits par Dumont, Foata, Randrianarivony et Zeng(cf. [DuFo], [DuRa], [RaZe]). En particulier, les propriétés pourtant très classiques des nombres de Stirling de seconde espèce trouvent une nouvelle jouvence dans ce contexte des escaliers évalués.

Le but de ce mémoire est de présenter une étude générale de ces objets et de donner toutes les évaluations utiles permettant de retrouver les résultats sur les différents polynômes dérivés des nombres classiques, Genocchi, Stirling, …

Soient n ≥ k ≥ 0 deux entiers ; un escalier de hauteur k et de longueur n est défini comme une suite d’entiers croissante

E = (E_{1} = 1, E_{2}, …, E_{n} = k)

telle que E_{i+1} − E_{i} = 0 ou 1 pour tout i. L’ensemble des escaliers de hauteur k et de longueur n est noté 𝔼(n, k). Un escalier peut être représenté par le diagramme de Ferrers justifié à droite (voir l’exemple ci-dessous) en posant

Diag(E) = {(i, j) | 1 ≤ i ≤ n, 1 ≤ j ≤ E_{i}} .

Une application ^{2} f : [n] → [k] est dite dans E si 1 ≤ f(i) ≤ E_{i} pour tout i ∈ [n]. Autrement dit, le diagramme {(i, f(i)) | i ∈ [n]} de f est un sous-ensemble de Diag(E) tel que toute verticale contient exactement un point du diagramme. Une application f est dite surjective sur E si f[n] = [k].

1 appelé plus tard pistoles dans [DuVi]. 2 Ce sont les tableaux 0-1 dans [DeLe], mais on ne fait pas la même chose.

2 Guo-Niu HAN

Par exemple, l’escalier E = (1, 1, 2, 2, 2, 2, 3, 4, 4) est de hauteur k = 4 et de longueur n = 9. Le diagramme suivant présente cet escalier et une application surjective f dans cet escalier :

Les escaliers précédemment définis sont aussi appelés 1-escaliers. Pour δ = 1, 2, 3, … à partir d’un 1-escalier E^{1} ∈ 𝔼^{1}(n, k), on construit, d’une façon bijective, un δ-escalier E^{δ} ∈ 𝔼^{δ}(n, k) par

E^{δ} = (E_{1}, E_{1}, …, E_{1}, E_{2}, E_{2}, …, E_{2}, …, …, E_{n}, E_{n}, …, E_{n})

où chaque E_{i} est répété δ fois. Ce δ-escalier est encore dit de hauteur k et de longueur n.

Fixons maintenant l’entier δ. Par abus de langage, on ne reproduira pas cette lettre δ, bien que désormais on étudiera toujours des δ-escaliers.

On remarque qu’il y a exactement un seul élément dans 𝔼(n, k), appelé escalier ordinaire et noté EO_{n}, dont la hauteur est égale à la longueur. Dans [Han] (Lemme 3.2), on a donné une involution dans le cas où δ = 2. Celle-ci peut être facilement généralisée dans le cas général comme suit :

Théorème 1. — Il existe une involution Φ : (E, f) ↦ (E′, f′) sur l’ensemble

𝔽_{n} = {(E, f) | E : un escalier de longueur n; f : une application dans E}

ayant les propriétés :

(C1) si E = EO_{n} et f est surjective, alors Φ(E, f) = (E, f) ; (C2) sinon, alors | hauteur(E) − hauteur(E′)| = 1.

En faisant intervenir les évaluations sur le couple (E, f), on retrouve plusieurs d’identités sur les nombres classiques : les nombres de Stirling, les nombres factoriels centraux, les nombres de Genocchi et d’Euler ; ainsi que leurs variations.

2. Les applications évaluées

On fixe encore l’entier δ comme dans la section précédente. Soit

𝔸 = {a_{1}, a_{2}, …, a_{δ}, b_{1}, b_{2}, …, b_{δ}, x_{1}, x_{2}, …, x_{δ}, y_{1}, y_{2}, …, y_{δ}}

un alphabet ou un ensemble de variables commutatives. On pose a = a_{1}a_{2} … a_{δ}. Un remplissage est un ensemble de mots en l’alphabet 𝔸 de la forme

R = [b_{1}b_{2} … b_{δ}[a_{1}a_{2} … a_{δ}]^{∗}]^{∗}[y_{1}y_{2} … y_{δ}[x_{1}x_{2} … x_{δ}]^{∗}] = [ba^{∗}]^{∗}[yx^{∗}]

qui permet d’associer à chaque case de tout escalier une lettre de 𝔸; plus précisément, à l’aide de R, on remplit toutes les cases d’un escalier E par les lettres de 𝔸 selon les règles suivantes :

Escaliers évalués et nombres classiques 3

(R1) (yxx … x) pour la dernière ligne (celle du bas) ; (R2) (baa … a) pour les autres lignes. Par exemple, pour le 2-escalier (δ = 2) E = (1, 1, 1, 1, 2, 2, 2, 2, 3, 3), le remplissage

R = [b_{1}b_{2}[a_{1}a_{2}]^{∗}]^{∗}[y_{1}y_{2}[x_{1}x_{2}]^{∗}] donne le diagramme suivant :

\begin{matrix}\begin{matrix}^{R = y_{1}} y_{2} x_{1} x_{2} x_{1} x_{2} x_{1} x_{2} x_{1} & x_{2} \\ b_{1} \end{matrix} ; b_{2} ; a_{1} ; a_{2} ; a_{1} ; a_{2} & b_{1} \\ b_{2} \end{matrix}

Pour un remplissage R fixé, on définit l’évaluation ev de tout couple (E, f) ∈ 𝔽_{n} par la formule

(1)  ev(E, f) = (−1)^{n−k} ∏_{i=1}^{n} R_{E}(i, f(i)),

où R_{E} est la restriction du remplissage R à l’escalier E, et k est la hauteur de E. Dans le cas où il n’y a pas de confusion, on écrit aussi ev(f) = ev(E, f).

D’après le théorème 1 et la construction de l’involution Φ, on vérifie facilement que la condition (C2) dans le théorème 1 peut être remplacée par la condition plus forte suivante :

(C2′) sinon, alors ev(E, f) = − ev(E′, f′).

Ceci démontre le résultat suivant :

Théorème 2. — Avec les notations précédentes, on a :

(2)  ∑_{(E,f)∈𝔽_{n}} ev(f) = ∑_{f∈𝕊_{n}} ev(f),

où 𝕊_{n} est l’ensemble des applications surjectives dans EO_{n} .

3. Interprétations algébriques

Notons

(3)  F_{n}(a, b, x, y) = ∑_{(E,f)∈𝔽_{n}} ev(f).

le polynôme générateur de 𝔽_{n}. En faisant une démonstration analogue à celle donnée dans [Han] (lemme 3.1), on a^{3} :

3 Théoriquement, on peut aussi démontrer ce théorème en faisant intervenir le coefficient d’un monôme , en les 4δ variables a_{i}, b_{i}, x_{i}, y_{i}, d’une forme fixée, comme dans [Dum] ou plutôt comme dans [DuFo].

Théorème 3. — Les polynômes F_{n}(a, b, x, y) peuvent être caractérisés par la relation de récurrence suivante :

(4) \{ \begin{matrix}F_{1}(a, b, x, y) = 1; \\ F_{n}(a, b, x, y) = (b_{1} + x_{1}) … (b_{δ} + x_{δ})F_{n−1}(a, b, x + a, y) \\ −x_{1}x_{2} … x_{δ}F_{n−1}(a, b, x, y). \end{matrix}

D’autre part, on définit les polynômes (t_{n,k}), qui sont les analogues des nombres de Stirling et des nombres factoriels centraux, par la relation de récurrence suivante :

(5)  \{ \begin{matrix}t_{n,0} = t_{0,k} = 0,  sauf pour t_{0,0} = 1; \\ t_{n,k} = t_{n−1,k−1} + t_{n−1,k} ∏_{i=1}^{δ}(x_{i} + (k − 1)a_{i})  (n, k ≥ 1). \end{matrix}

En examinant les dernières colonnes des escaliers, on vérifie que le polynôme t_{n,k} est le polynôme générateur de l’ensemble

𝔽′_{n} = {(E, f) | E ∈ 𝔼(n − k, k); f : une application dans E},

avec l’évaluation ev′ déduite du remplissage R′ = [[aa^{∗}]^{∗}[xx^{∗}]. On a donc :

t_{n,k} = ∑_{(E,f)∈𝔽′_{n}} | ev′(E, f)|.

ou encore :

(6) t_{n,k} ∏_{i=1}^{δ} y_{i}(x_{i} + b_{i})(x_{i} + b_{i} + a_{i}) … (x_{i} + b_{i} + (k − 2)a_{i}) = ∑ | ev(E, f)|

où la somme est faite pour tous les couples (E, f) ∈ 𝔽_{n} tels que la hauteur de E est k. D’où

Théorème 4. — Avec les notations précédentes, on a :

(7)  \begin{aligned}F_{n}(a, b, x, y) = & ∑_{k=1}^{n}(−1)^{n−k}t_{n,k}\{∏_{j=1}^{δ} y_{i}(x_{i} + b_{i}) \\ & × (x_{i} + b_{i} + a_{i}) … (x_{i} + b_{i} + (k − 2)a_{i})\}. \end{aligned}

4. Les exemples des 1-escaliers

Dans le cas où δ = 1, ces études sont liées aux nombres de Stirling et leurs variations. C’est un cas très particulier où il y a exactement une seule surjection dans EO_{n}. D’après le théorème 2, les polynômes F_{n} sont simplement des monômes (cf. [DeLe] pour les travaux analogues).

4.1. — On prend le remplissage R = [b1^{∗}]^{∗}[b1^{∗}]

\begin{matrix}\begin{matrix}\begin{matrix}^{R = b} 1 1 1 1 1 1 1 & 1 \\ b \end{matrix} ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 & b \\ 1 \end{matrix} ; 1 & b \\ 1 \end{matrix}

D’après (5), le nombre t_{n,k} n’est rien d’autre que le nombre de Stirling S_{n,k}. D’où la formule (7) s’écrit sous une forme bien connue :

b^{n} = ∑_{k=1}^{n}(−1)^{n−k}b(b + 1) … (b + k − 1)S_{n,k} = ∑_{k=1}^{n}(−1)^{n}k!S_{n,k}\binom{b}{k}.

4.2. — On définit un analogue des nombres de Stirling (t_{n,k}) par la relation de récurrence :

\{ \begin{matrix}t_{n,0} = t_{0,k} = 0,  sauf pour t_{0,0} = 1; \\ t_{n,k} = t_{n−1,k−1} + (x + (k − 1)a)t_{n−1,k}  (n, k ≥ 1). \end{matrix}

Le remplissage correspondant est R = [ba^{∗}]^{∗}[bx^{∗}]

\begin{matrix}\begin{matrix}\begin{matrix}^{R = b} x x x x x x x & x \\ b \end{matrix} ; a ; a ; a ; a ; a ; a & b \\ a \end{matrix} ; a & b \\ a \end{matrix}

On a donc d’après (7) :

b^{n} = ∑_{k=1}^{n}(−1)^{n−k}b(b + x)(b + x + a) … (b + x + (k − 2)a)t_{n,k}.

5. Les exemples des 2-escaliers

Dans le cas des 2-escaliers (δ = 2), ces études sont liées aux nombres de Genocchi, aux nombres d’Euler et nombres factoriels centraux, ainsi qu’à leurs variations. Les exemples décrits ci-dessous ont été étudiés originalement par Gandhi, Dumont, Foata, Randrianarivony et Zeng(voir les références correspondantes).

5.1. Polynômes de Gandhi

Ces polynômes (F_{n}(x)) sont définis par la relation de récurrence [Gan] :

\{ \begin{matrix}F_{1}(x) = 1; \\ F_{n}(x) = (x + 1)^{2}F_{n−1}(x + 1) − x^{2}F_{n−1}(x). \end{matrix}

Le remplissage correspondant est R = [11(11)^{∗}]^{∗}[11(xx)^{∗}]

\begin{matrix}\begin{matrix}^{R = 1} 1 x x x x x x x & x \\ 1 \end{matrix} ; 1 ; 1 ; 1 ; 1 ; 1 & 1 \\ 1 \end{matrix}

Les nombres (ou polynômes) (t_{n,k}) sont des analogues des nombres factoriels centraux, définis par la formule de récurrence :

\{ \begin{matrix}t_{n,0} = t_{0,k} = 0,  sauf pour t_{0,0} = 1; \\ t_{n,k} = t_{n−1,k−1} + (x + k − 1)^{2}t_{n−1,k}  (n, k ≥ 1). \end{matrix}

6 Guo-Niu HAN

On a donc d’après (7) :

F_{n}(x) = ∑_{k=1}^{n}(−1)^{n−k}((x + 1)(x + 2) … (x + k − 1))^{2}t_{n,k}.

En posant x = 1, on retrouve la formule suivante :

G_{2n+2} = ∑_{k=1}^{n}(−1)^{n−k}k!^{2}T_{2n,2k},

où G_{2n+2} est le nombre de Genocchi, et T_{2n,2k} est le nombre factoriel central (cf. par exemple [RiSt]).

5.2. Polynômes de Dumont-Foata

Ces polynômes (F_{n}(x, y, z)) sont définis par la relation de récurrence [DuFo] :

\{ \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). \end{matrix}

Le remplissage correspondant est R = [yz(11)^{∗}]^{∗}[11(xx)^{∗}]

\begin{matrix}\begin{matrix}^{R = 1} 1 x x x x x x x & x \\ y \end{matrix} ; z ; 1 ; 1 ; 1 ; 1 & y \\ z \end{matrix}

On retrouve une formule obtenue pour la première fois par Carlitz[Car] :

F_{n}(x, y, z) = ∑_{k=1}^{n}(−1)^{n−k}{(x + y)(x + y + 1) … (x + y + k − 2)

×(x + z)(x + z + 1) … (x + z + k − 2)}t_{n,k},

où les nombres (t_{n,k}) sont ceux définis dans le paragraphe précédent.

En particulier, pour x = 1 et z = y, on a :

F_{n}(1, y, y) = ∑_{k=1}^{n}(−1)^{n−k}((y + 1)(y + 2) … (y + k − 1))^{2}T_{2n,2k}.

5.3. Polynômes de Dumont-Randrianarivony

Ces polynômes (F_{n}(x, y)) sont définis par la relation de récurrence [DuFo] :

\{ \begin{matrix}F_{1}(x, y) = 1; \\ F_{n}(x, y) = (x + 1)(y + 1)F_{n−1}(x + 1, y + 1) − xyF_{n−1}(x, y). \end{matrix}

Le remplissage correspondant est R = [11(11)^{∗}]^{∗}[11(xy)^{∗}]

\begin{matrix}\begin{matrix}^{R = 1} 1 x y x y x y x & y \\ 1 \end{matrix} ; 1 ; 1 ; 1 ; 1 ; 1 & 1 \\ 1 \end{matrix}

Les nombres (t_{n,k}) sont des analogues des nombres factoriels centraux, définis par la formule de récurrence :

\{ \begin{matrix}t_{n,0} = t_{0,k} = 0,  sauf pour t_{0,0} = 1; \\ t_{n,k} = t_{n−1,k−1} + (x + k − 1)(y + k − 1)t_{n−1,k}  (n, k ≥ 1). \end{matrix}

On retrouve :

F_{n}(x, y) = ∑_{k=1}^{n}(−1)^{n−k}{(x + 1)(x + 2) … (x + k − 1)

×(y + 1)(y + 2) … (y + k − 1)}t_{n,k}.

5.4. Polynômes de Randrianarivony-Zeng

Ces polynômes (F_{n}(x, y)) sont définis par la relation de récurrence [RaZe] :

\{ \begin{matrix}F_{1}(x, y) = 1; \\ F_{n}(x, y) = x(y + 1)F_{n−1}(x + 2, y + 2) − xyF_{n−1}(x, y). \end{matrix}

Le remplissage correspondant est R = [01(22)^{∗}]^{∗}[11(xy)^{∗}]

\begin{matrix}\begin{matrix}^{R = 1} 1 x y x y x y x & y \\ 0 \end{matrix} ; 1 ; 2 ; 2 ; 2 ; 2 & 0 \\ 1 \end{matrix}

Les nombres (t_{n,k}) sont des analogues des nombres factoriels centraux, définis par la formule de récurrence :

\{ \begin{matrix}t_{n,0} = t_{0,k} = 0,  sauf pour t_{0,0} = 1; \\ t_{n,k} = t_{n−1,k−1} + (x + 2(k − 1))(y + 2(k − 1))t_{n−1,k}  (n, k ≥ 1). \end{matrix}

On retrouve :

F_{n}(x, y) = ∑_{k=1}^{n}(−1)^{n−k}{x(x + 2) … (x + 2k − 4)

×(y + 1)(y + 3) … (y + 2k − 3)}t_{n,k}.

BIBLIOGRAPHIE

[And] André (D.). — Sur les permutations alternées, J. Math. Pures Appl., t. 7, 1881, p. 167-187.

[Car] Carlitz (L.). — Explicit formulas for the Dumont-Foata polynomial, Discrete. Math., t. 30, 1980, p. 211-225.

[DeLe] DeMédicis (A.) et Leroux(P.). — Généralisations des nombres de Stirling et p, q-analogues, Actes de l’Atelier de Combinatoire franco-québecois, Publication LaCIM n^{∘}10, Édité par J. Labelle et J. -G. Penaud, 1991, p. 87-103.

[Dum] Dumont (D.). — Interprétations combinatoires des nombres de Genocchi, Duke math. J., t. 41(2), 1974, p. 305-318.

[DuFo] Dumont (D.) et Foata (D.). — Une propriété de symétrie des nombres de Genocchi, Bull. Soc. math. France, t. 104, 1976, p. 433-451.

[DuRa] Dumont (D.) et Randrianarivony (A.). — Sur une extension des nombres de Genocchi, à paraître.

[DuVi] Dumont (D.) et Viennot (G.). — A combinatorial interpretation of the Seidel generation of Genocchi numbers, Annals of Discrete Mathematics, t. 6, 1980, p. 77-87.

[Gan] Gandhi (J. M.). — A conjectured representation of Genocchi numbers, Am. Math. Monthly, t. 77(1), 1970, p. 505-506.

[Han] Han (G. -N.). — Symétries trivariées sur les nombres de Genocchi, Actes de l’Atelier de Combinatoire franco-québecois, Publication LaCIM n^{∘}10, Édité par J. Labelle et J. -G. Penaud, 1991, p. 119-133.

[RaZe] Randrianarivony (A.) et Zeng (J.). — Sur une extension des nombres d’Euler, à paraître.

[RiSt] Riordan (J.) et Stein (P.). — Proof of a conjecture on Genocchi numbers, Discrete Math., t. 5, 1973, p. 381-388.