Séminaire Lotharingien de Combinatoire, B05c (1981)

MATRICES D’EULER-SEIDEL

PAR

Dominique DUMONT

1. Introduction. — Cet article est un recueil de tables de calculs aux différences finies. Ce que nous nommons matrice d’Euler-Seidel, c’est ce que des mathématiciens d’autrefois comme Leibniz, Euler ou Seidel, construisaient lorsque partant d’une suite de nombres, ils considéraient la suite des différences entre termes consécutifs, notant Δ l’opération effectuée et itéraient le processus [18].

Nous exposons d’abord les deux théorèmes d’Euler et de Seidel, un peu oubliés quoique très élémentaires, puis les appliquons aux exemples qui nous ont paru les plus intéressants. Les exemples intéressants sont ceux où la matrice d’Euler-Seidel permet un calcul rapide (extrêmement facile à programmer sur ordinateur) de la suite d’entiers initiale, qui par ailleurs a une interprétation combinatoire. Pour chaque exemple nous donnons la table des premières valeurs, selon un principe cher aux praticiens des dénombrements.

2. Définition et propriétés élémentaires.

Définition. — Soit a_{0}, a_{1}, a_{2}, …, a_{n}, … une suite d’éléments d’un anneau commutatif A (en fait ici des nombres, des polynômes ou des fractions rationnelles). On appelle matrice d’Euler-Seidel associée à (a_{n}) la suite double (a_{n}^{k}) (n ≥ 0, k ≥ 0) donnée par la récurrence

(1)  \begin{aligned}a_{n}^{0} & = a_{n}  (n ≥ 0), \\ a_{n}^{k} & = a_{n}^{k−1} + a_{n+1}^{k−1} (k ≥ 1, n ≥ 0). \end{aligned}

La suite (a_{n}^{0}) première ligne de la matrice, est la suite initiale. La suite (a_{0}^{n}), première colonne de la matrice, est la suite finale. Il résulte immédiatement de (1) l’identité

(2)  a_{n}^{k} = ∑_{i=0}^{k} ( \begin{matrix}k \\ i \end{matrix} ) a_{n+i}^{0}

D. DUMONT

En particulier, on passe de la suite initiale à la suite finale et inversement par

(3)  a_{0}^{n} = ∑_{i=0}^{n} \binom{n}{i}a_{i}^{0},

(4)  a_{n}^{0} = ∑_{i=0}^{n}(−1)^{i}\binom{n}{i}a_{0}^{i}.

Proposition 1 (Euler [11]). — Soit a(t) = Σa_{n}^{0}t^{n} la fonction génératrice ordinaire de la suite initiale. Alors la fonction génératrice ordinaire \overline{a}(t) de la suite finale est donnée par

(5)  \overline{a}(t) = ∑_{n≥0} a_{0}^{n}t^{n} = \frac{1}{1 − t}a(\frac{1}{1 − t}).

En effet, on sait que

(6)  \frac{1}{(1 − t)^{n+1}} = ∑_{k≥0} ( \begin{matrix}n + k \\ n \end{matrix} ) t^{k}.

Par suite,

\frac{1}{1 − t}a(\frac{t}{1 − t}) = ∑_{n≥0} a_{n}^{0} \frac{t^{n}}{(1 − t)^{n+1}}

= ∑_{n,k≥0} ( \begin{matrix}n + k \\ n \end{matrix} ) a_{n}^{0}t^{n+k}

= ∑_{m≥0} t^{m}( ∑_{n+k=m} ( \begin{matrix}m \\ n \end{matrix} ) a_{n}^{0})

= ∑_{m≥0} a_{0}^{m}t^{m}

= \overline{a}(t).

Proposition 2 (Seidel [28]). — Soit A(t) = ∑_{n≥0} a_{n}^{0}t^{n}/n! la fonction génératrice exponentielle de la suite initiale. Alors la fonction génératrice exponentielle de la suite finale est donnée par

(7)  \overline{A}(t) = ∑_{n≥0} a_{0}^{n} \frac{t^{n}}{n!} = e^{t}A(t).

MATRICES D’EULER-SEIDEL

En effet, d’après (3),

\overline{A}(t) = ∑_{n≥0}(∑_{i=0}^{n} \binom{n}{i}a_{i}^{0})\frac{t^{n}}{n!}

= ∑_{i,j≥0} \frac{a_{i}^{0}}{i! j!}t^{i+j} = e^{t}A(t).

.

1) On passe d’une proposition à l’autre par transformation de Laplace formelle.

2) On montre aisément [8] que la fonction génératrice exponentielle double de la matrice vaut

∑_{n,k≥0} a_{n}^{k} \frac{t^{n}}{n!} \frac{u^{k}}{k!} = e^{u}A(t + u).

3. Matrices d’Euler-Seidel de nombres (exemples). — Nous commencerons par traiter trois exemples où les nombres sont fractionnaires, puis nous aborderons les exemples avec des entiers qui ont des interprétations combinatoires.

3.1. — Prenons a_{n}^{0} = \frac{(−1)^{n}}{n + 1} (n ≥ 0). Alors a(t) = \frac{1}{t} Log(1 + t),

\overline{a}(t) = −\frac{1}{t} Log(1 − t), A(t) = \frac{1 − e^{−t}}{t}, \overline{A}(t) = \frac{e^{t} − 1}{t}, a_{n}^{0} = \frac{1}{n + 1} et plus

généralement, a_{n}^{k} = \frac{(−1)^{n}}{(n + k + 1)\binom{n+k}{k}}. D’où la matrice

(ES1)  1  −\frac{1}{2}  +\frac{1}{3}  −\frac{1}{4}  +\frac{1}{5}  …; \frac{1}{2}  −\frac{1}{6}  +\frac{1}{12}  −\frac{1}{20} ; \frac{1}{3}  −\frac{1}{12}  +\frac{1}{30} ; \frac{1}{4}  −\frac{1}{20} ; \frac{1}{5}

Cette matrice est en général attribuée à Leibniz [6].

3.2. — Cet exemple est dû à Euler [11]. a_{n}^{0} = \frac{(−1)^{n}}{2n + 1} (n ≥ 0).

On constate rapidement que a_{n}^{k} = \frac{(−1)^{n}2.4 … (2k)}{(2n + 1)(2n + 3) … (2n + 2k + 1)}. En

particulier a_{0}^{n} = \frac{2.4 … (2n)}{1.3.5 … (2n + 1)}.

(ES2)  1  −\frac{1}{3}  +\frac{1}{5}  −\frac{1}{7}  …; \frac{2}{1.3}  −\frac{2}{3.5}  \frac{2}{5} ; \frac{2.4}{1.3.5}  \frac{−2.4}{3.5.7} ; \frac{2.4.6}{1.3.5.7}

Ainsi a(t) = 1 − \frac{t}{3} + \frac{t^{2}}{5} − \frac{t^{3}}{7} + ⋯ = t^{−1/2} Arctg(t^{1/2}). D’où, d’après la

proposition 1, \overline{a}(t) = [t(1 − t)]^{−1/2} Arctg(\frac{t}{1 − t})^{1/2}. En posant t = x^{2}, et

en observant que Arctg \frac{x}{\sqrt{1 − x^{2}}} = Arcsin x, Euler déduit

\frac{Arcsin x}{\sqrt{1 − x^{2}}} = x + \frac{2}{3}x^{3} + \frac{2.4}{1.3.5}x^{5} + \frac{2.4.6}{1.3.5.7}x^{7} + ⋯

3.3. — Prenons a_{0}^{0} = 1, a_{2n}^{0} = \frac{1.3.5 … (2n − 1)}{2.4.6 … 2n} et a_{2n−1}^{0} = 0 (n ≥ 1).

1  0  \frac{1}{2}  0  \frac{1.3}{2.4}  …
1  \frac{1}{2}  \frac{1}{2}  \frac{1.3}{2.4}
\frac{1.3}{1.2}  1  \frac{7}{8}
\frac{1.3.5}{1.2.3}  \frac{15}{8}

\frac{1.3.5.7}{1.2.3.4}

Alors a_{0}^{n} = \frac{1.3.5 … (2n − 1)}{n!}. En effet a(t) = \frac{1}{\sqrt{1 − t^{2}}} , d’où \overline{a}(t) = \frac{1}{\sqrt{1−2t}}.

En outre A(t) = I_{0}(t), fonction modifiée de Bessel, et \overline{A}(t) = e^{t}I_{0}(t).

Nous abordons à présent les exemples de matrices à coefficients entiers. Laissons en exercice les nombres de Fibonacci, et commençons par les nombres de Bell :

3.4. — Soit a_{n}^{0} = B_{n}, nombre de partitions d’un ensemble à n éléments. On sait [6] que A(t) = exp(e^{t} − 1). D’où \overline{A}(t) = exp(e^{t} − 1 + t) = A′(t). Par suite a_{n}^{0} = a_{0}^{n−1}, d’où un procédé de calcul simple des nombres de Bell [12, 21].

(ES4) \begin{matrix}1 & 1 & 2 & 5 & 15 & 52 & … \\ 2 & 3 & 7 & 20 \\ 5 & 10 & 27 \\ 15 & 37 \\ 52 \end{matrix}

3.5. — Un exemple voisin est celui où a_{n}^{0} est le nombre de partitions ordonnées d’un ensemble à n éléments (une partition ordonnée est le couple formé d’une partition et d’un ordre total sur les blocs de cette partition). On montre que A(t) = 1/(2 − e^{t}). D’où \overline{A}(t) = 2A(t) − 1, et on a a_{0}^{n} = 2a_{n}^{0}. En outre, dans toute matrice d’Euler-Seidel a_{0}^{n} = a_{n}^{0} + (a_{n−1}^{0} + a_{n−2}^{1} + a_{n−3}^{2} + … + a_{0}^{n−1}). Dans ce cas particulier, on a donc

a_{n}^{0} = a_{n−1}^{0} + a_{n−2}^{1} + … + a_{0}^{n−1},

d’où un calcul rapide de ces nombres, étudiés par maints auteurs [1, 4, 12, 15, 16, 21, 29, 31, 32]

(ES5) \begin{matrix}1 & 1 & 3 & 13 & 75 & … \\ 2 & 4 & 16 \\ 6 & 20 \\ 26 \end{matrix}

3.6. — Considérons à présent le cas où a_{n}^{0} est le nombre d’applications f idempotentes (f ∘ f = f) d’un ensemble à n éléments dans lui-même [6, 17, 25]. Alors

A(t) = e^{te^{t}},  d’où  A′(t) = (1 + t)e^{t}e^{te^{t}} = (1 + t)\overline{A}(t).

Donc a_{n+1}^{0} = a_{0}^{n} + na_{0}^{n−1}, et un rapide calcul de a_{n}^{0} [17].

(ES6) \begin{matrix}1 & 1 & 3 & 10 & 41 & 196 & … \\ 2 & 4 & 13 & 51 \\ 6 & 17 & 64 \\ 23 & 81 \\ 104 \end{matrix}

3.7. — Si a_{n}^{0} est le nombre de permutations sans point fixe, ou dérangements, d’un ensemble à n éléments, alors a_{0}^{n} vaut n!, nombre de toutes les permutations [6, 24].

A(t) = \frac{e^{−t}}{1 − t}, \overline{A}(t) = \frac{1}{1 − t}.

Signalons que cette matrice d’Euler-Seidel est déjà dans Euler [10], mais privée de la ligne initiale ! Pour des aspects combinatoires, voir [19] [35].

(ES7) \begin{matrix}1 & 0 & 1 & 2 & 9 & 44 & … \\ 1 & 1 & 3 & 11 & 53 \\ 2 & 4 & 14 & 64 \\ 6 & 18 & 78 \\ 24 & 96 \\ 120 \end{matrix}

3.8. — Ainsi d’une manière générale, dans les classes de permutations, on passe des “sans point fixe”, avec une fonction génératrice A(t) = e^{f(t)}, où f(0) = f′(0) = 0, aux “avec points fixes” où \overline{A}(t) = e^{f(t)+t}. A ce sujet, voir [13].

Exemple : a_{n}^{0} est le nombre de permutations involutives (p ∘ p = id) sans point fixe d’un ensemble à n éléments, donc a_{n}^{0} = 0 si n impair est a_{n}^{0} = 1.3.5 … (n − 1) si n pair. Alors a_{0}^{n} est le nombre de toutes les permutations involutives.

A(t) = e^{t^{2}/2}, \overline{A}(t) = e^{t+t^{2}/2}.

(ES8) \begin{matrix}1 & 0 & 1 & 0 & 3 & 0 & 15 & … \\ 1 & 1 & 1 & 3 & 3 \\ 2 & 2 & 4 & 6 \\ 4 & 6 & 10 \\ 10 & 16 \\ 26 \end{matrix}

3.9. — Si a_{n}^{0} = n!, a_{0}^{n} est le nombre “d’arrangements” sur un ensemble à n éléments. A(t) = 1/(1 − t), A(t) = e^{t}/(1 − t).

(ES9) \begin{matrix}1 & 1 & 2 & 6 & 24 & … \\ 2 & 3 & 8 & 30 \\ 5 & 11 & 38 \\ 16 & 49 \\ 65 \end{matrix}

3.10.. — Nous abordons à présent les exemples dûs à Seidel [28], qui ont pour caractéristique de concerner des suites d’entiers alternées. Si

D. DUMONT

a_{0}^{0} = 1, a_{2n}^{0} = 0(n ≥ 1), et a_{2n−1}^{0} = (−1)^{n}T_{2n−1}, nombre tangent, alors a_{0}^{2n} = (−1)^{n}E_{2n}, nombre sécant.

(ES10) \begin{matrix}1 & −1 & 0 & 2 & 0 & −16 & 0 \\ 0 & −1 & 2 & 2 & −16 & −16 \\ −1 & 1 & 4 & −14 & −32 \\ 0 & 5 & −10 & −46 \\ 5 & −5 & −56 \\ 0 & −61 \\ −61 \end{matrix}

A(t) = 1 − th t = \frac{2}{e^{2t} + 1}, \overline{A}(t) = \frac{1}{ch t}.

Si l’on repart des nombres sécants comme suite initiale, on réobtient les nombres tangents, car si A(t) = \frac{1}{ch t}, \overline{A}(t) = 1 + th t.

(ES10′) \begin{matrix}1 & 0 & −1 & 0 & 5 & 0 & −61 \\ 1 & −1 & −1 & 5 & 5 & −61 \\ 0 & −2 & 4 & 10 & −56 \\ −2 & 2 & 14 & −46 \\ 0 & 16 & −32 \\ 16 & −16 \\ 0 \end{matrix}

En fait, c’est en un certain sens la “même” matrice. Sous la deuxième forme elle est caractérisée par les deux conditions suivantes :

(E1) A(x) est une fonction paire et A(0) = 1.

(E2) Ā(x) − 1 est une fonction impaire. En supprimant les signes et en décrivant la matrice en diagonale, Seidel obtient le triangle suivant :

1

→  1  1
2  2  1  ←
→  2  4  5  5
16  16  14  10  5  ←

triangle qui permet un calcul rapide de nombres tangents et sécants, et dont Entringer a donné l’interprétation combinatoire [9].

3.11. — Soit A(t) = \frac{2t}{1 + e^{t}}. Alors a_{0}^{0} = 0, a_{1}^{0} = 1, a_{2n+1}^{0} = 0 (n ≥ 1),

a_{2n}^{0} = (−1)^{n}G_{2n}, où G_{2n} s’appelle nombre de Genocchi. D’où \overline{A}(t) = −A(t) + 2t.

(ES11) \begin{matrix}0 & 1 & −1 & 0 & 1 & 0 & −3 & 0 & 17 \\ 1 & 0 & −1 & 1 & 1 & −3 & −3 & 17 \\ 1 & −1 & 0 & 2 & −2 & −6 & 14 \\ 0 & −1 & 2 & 0 & −8 & 8 \\ −1 & 1 & 2 & −8 & 0 \\ 0 & 3 & −6 & −8 \\ 3 & −3 & −14 \\ 0 & −17 \\ −17 \end{matrix}

On montre que les diagonales sont alternativement symétriques et antisymétriques. En particulier a_{n}^{n} = 0, et Seidel en déduit le triangle suivant

1

→  1  1
2  1  ←
→  2  3  3
8  6  3  ←
→  8  14  17  17

qui permet un calcul rapide des nombre de Genocchi ainsi que des nombres |a_{n}^{n−1}| q’uon peut appeler nombres de Genocchi de deuxième espèce [3]. On trouvera par ailleurs des interprétations combinatoire de la matrice (ES 11) en [8] et [35].

3.12. — Soit A(t) = \frac{t}{e^{t} − 1}, alors \overline{A}(t) = A(t) + t, a_{0}^{n} = a_{n}^{0} (n ≥ 2).

Suites initiale et finale sont formées des nombres de Bernouilli. Mais la matrice de Seidel ne donne pas de méthode de calcul de ces nombres.

(ES12) \begin{matrix}1 & −\frac{1}{2} & \frac{1}{6} & 0 & −\frac{1}{30} & … \\ \frac{1}{2} & −\frac{1}{3} & \frac{1}{6} & −\frac{1}{30} \\ \frac{1}{6} & −\frac{1}{6} & \frac{2}{15} \\ 0 & −\frac{1}{30} \\ −\frac{1}{30} \end{matrix}

3.13. — Voici encore un exemple lié à (ES10) et (ES11), qui consiste à prendre pour suite initiale a_{1}^{0} = 1, a_{2n}^{0} = (−1)^{n}2nT_{2n−1} = (−1)^{n}2^{2n−1}G_{2n} (n ≥ 1), a_{2n+1}^{0} = 0 (n ≥ 1).

(ES13) \begin{matrix}0 & 1 & −2 & 0 & 8 & 0 & −96 \\ 1 & −1 & −2 & 8 & 8 \\ 0 & −3 & 6 & 16 \\ −3 & 3 & 22 \\ 0 & 25 \\ 25 \end{matrix}

Donc A(t) = \frac{2t}{e^{2t} + 1} = t−t th t, \overline{A}(t) = \frac{t}{ch t} et a_{0}^{2n+1} = (−1)^{n}(2n+1)E_{2n}.

4. Quelques extensions polynomiales. — Nous nous limiterons aux extensions les plus classiques en Combinatoire, et nous contenterons dans les tables de donner les premières valeurs des suites initiale et finale. En effet, les matrices de polynômes ne fournissent en général pas d’algorithme pour calculer la suite initiale.

4.1. Polynômes d’Appell. — A une suite initiale (a_{n}^{0}), de fonctions génératrices a(t) et A(t), nous associons la suite des polynômes (a_{n}(x)) (n ≥ 0) définis par

a_{n}(x) = ∑_{i=0}^{n} \binom{n}{i}a_{i}^{0}x^{n−i}.

Ce sont les polynômes d’Appell associés à (a_{n}^{0}) [2]. On montre comme plus haut que

(8)  ∑ a_{n}(x)t^{n} = \frac{1}{1 − tx}a(\frac{t}{1 − tx}),
(9)  ∑ a_{n}(x)\frac{t^{n}}{n!} = e^{tx}A(t).

Les polynômes a_{n}(x) sont une ‘interpolation”, puisque

a_{n}(0) = a_{n}^{0}, a_{n}(1) = a_{0}^{n}.

En outre, on a a′_{n}(x) = na_{n−1}(x), et ce sont des polynômes de type binomial [27]

a_{n}(x + y) = ∑_{i=0}^{n} ( \begin{matrix}n \\ i \end{matrix} ) a_{i}(x)a_{n−i}(y).

Si l’on prend comme suite initiale d’une matrice de Seidel une suite de polynômes d’Appell (a_{n}(x)), la suite finale sera (a_{n}(x + 1)).

Comme exemples, citons d’abord les polynômes de Bernoulli, associés aux nombres de Bernoulli. On peut de même introduire des “polynômes de Genocchi” (à coefficient près ce sont ceux qu’on appelle polynômes d’Euler dans la littérature [6, 18]), d’autres “polynômes d’Euler” à partir de (ES10) ou (ES10’). Introduits à partir de (ES7), on voit que les polynômes énumérateurs du nombre de points fixes sur les permutations ont pour fonction génératrice exp((x − 1)t)/(1 − t), d’après (9).

De même, à partir de (ES8), e^{xt+t^{2}/2!} est fonction génératrice des polynômes d’Hermite, qui énumèrent les points fixes sur les permutations involutives.

Si enfin nous considérons le cas de la suite initiale de (ES3), nous voyons que les polynômes d’Appell associés ont pour fonctions génératrices, d’après (8) et (9)

(10)  ∑ a_{n}(x)t^{n} = \frac{1}{\sqrt{1 − 2xt + (x^{2} − 1)t^{2}}} ,
(11)  ∑ a_{n}(x)\frac{t^{n}}{n!} = e^{xt}I_{0}(t).

L’équation (10) implique

(12)  a_{n}(x) = (x^{2} − 1)^{n/2}P_{n}(\frac{x}{\sqrt{x^{2} − 1}}),

où P_{n} est le polynôme de Legendre. On trouvera une étude combinatoire des polynômes n!a_{n}(x) en [7].

4.2. Autres extensions.

a) a_{n}^{0} = x^{n}/n!. Alors a(t) = e^{xt}, A(t) = I_{0}(2\sqrt{x}t). D’où \overline{a}(t) = (1/(1 − t)) exp(xt/(1 − t)), \overline{A}(t) = e^{t}I_{0}(2\sqrt{x}t). On a a_{0}^{n} = \frac{1}{n!} L_{n}^{(0)}(−x), où L_{n}^{(0)} désigne le polynôme de Laguerre d’indice 0. En outre a_{1}^{n} = \frac{1}{(n+1)!}L_{n+1}^{(−1)}(−x), dont les coefficients sont appelés nombre de Lah [20], et énumèrent les fonctions acycliques f d’un ensemble à (n + 1) éléments dans lui-même (c’est-à-dire telles que f^{n+1} = f^{n}) suivant le nombre de points fixes [13, 24].

(ES14)  1  x  \frac{x^{2}}{2!}  \frac{x^{3}}{3!} …; 1 + x  \frac{2x^{2} + x^{2}}{2!}  \frac{3x^{2} + x^{3}}{3!} ; \frac{2 + 4x + x^{2}}{2!}  \frac{6x + 6x^{2} + x^{3}}{3!} ; \frac{6 + 18x + 9x^{2} + x^{3}}{3!}

b) Les polynômes dits “exponentiels” [6, 23], dont les coefficients sont les nombres de Stirling de deuxième espèce, qui énumèrent les partitions selon le nombre de blocs. C’est donc une extension de (ES4)

A(t) = exp(x(e^{t} − 1)) = 1 + xt + (x + x^{2})\frac{t^{2}}{2!} + (x + 3x^{2} + x^{3})\frac{t^{3}}{3!}

+ (x + 7x^{2} + 6x^{3} + x^{4})\frac{t^{4}}{4!} + ⋯

\overline{A}(t) = \frac{1}{x}A′(t), d’où a_{n+1}^{0} = xa_{0}^{n}.

1  x  x + x^{2}  x + 3x^{2} + x^{3} …
1 + x  2x + x^{2}  2x + 4x^{2} + x^{3}
1 + 3x + x^{2}  4x + 5x^{2} + x^{3}

1 + 7x + 6x^{2} + x^{3}

c) Une extension de (ES9) est donnée par A(t) = e^{−x Log(1−t)}, fonction génératrice des polynômes dont les coefficients sont les nombres de Stirling de première espèce et énumèrent les permutations selon le nombre de cycles.

\begin{aligned}e^{−x Log(1−t)} & = 1 + xt + (x + x^{2})\frac{t^{2}}{2!} + (2x + 3x^{2} + x^{3})\frac{t^{3}}{3!} \\ & + (6x + 11x^{2} + 6x^{3} + x^{4})\frac{t^{4}}{4!} + ⋯ \end{aligned}

Alors \overline{A}(t) = e^{t−Log(1−t)} est la fonction génératrice des polynômes de Charlier [5, 30]

e^{t−x Log(1−t)} = 1 + (1 + x)t + (1 + 3x + x^{2})\frac{t^{2}}{2!} + (1 + 8x + 6x^{2} + x^{3})\frac{t^{3}}{3!} + ⋯

d) Une extension de (ES7) est donnée par les polynômes de Roselle [26] qui énumèrent les permutations sans point fixe selon le nombre de montées de cycle, c’est-à-dire d’entiers i tels que i < p(i).

\begin{aligned}A(t) & = \frac{exp(−t)}{1 − \frac{exp((x − 1)t)}{x − 1}} = 1 + x\frac{t^{2}}{2!} + (x + x^{2})\frac{t^{3}}{3!} + (x + 7x^{2} + x^{3})\frac{t^{4}}{4!} \\ & + (x + 21x^{2} + 21x^{3} + x^{4})\frac{t^{5}}{5!} + ⋯ \end{aligned}

Alors la suite finale est celle des polynômes eulériens [14, 24] qui énumèrent les permutations selon les montées larges de cycle (i ≤ p(i)).

\begin{aligned}\overline{A}(t) & = \frac{1}{1 − \frac{exp((x − 1)t) − 1}{x − 1}} = 1 + t + (1 + x)\frac{t^{2}}{2!} + (1 + 4x + x^{2})\frac{t^{3}}{3!} \\ & + (1 + 11x + 11x^{2} + x^{3})\frac{t^{4}}{4!} + ⋯ \end{aligned}

Notons que cette matrice-là est aussi une extension de (ES10’), qu’on réobtient en posant x = −1.

e) Si on prend pour suite initiale les polynômes eulériens, on obtient une matrice étendant à la fois (ES9) et (ES10).

A(t) = \frac{exp((x − 1)t)}{1 − \frac{exp((x − 1)t) − 1}{x − 1}}

= 1 + xt + (x + x^{2})\frac{t^{2}}{2!} + (x + 4x^{2} + x^{3})\frac{t^{3}}{3!} + ⋯

\overline{A}(t) = \frac{exp(xt)}{1 − \frac{exp((x − 1)t) − 1}{x − 1}}

= 1 + (1 + x)t + (1 + 3x + x^{2})\frac{t^{2}}{2!} + (1 + 7x + 7x^{2}tx^{3})\frac{t^{3}}{3!}

+ (1 + 15x + 33x^{2} + 15x^{3} + x^{1})\frac{t^{4}}{4!} + ⋯

Les polynômes de la suite finale sont, comme ceux de Roselle, symétriques et redonnant les nombres sécants pour x = −1.

f) Parmi les extensions en fractions rationnelles, signalons la suivante,

de (ES1) : a_{n}^{0} = \frac{(−1)^{n+1}}{x + n}, d’où a_{0}^{n} = \frac{n!}{x(x + 1) … (x + n)} (n ≥ 0).

BIBLIOGRAPHIE

[1] M. Aigner. — Combinatorial Theory. — Springer Verlag, 1979, chap. III et p. 201.

[2] P. Appel. — Sur une classe de polynômes, Ann. Ecole Normale Supérieure, vol. 2, 1880, p. 119-144.

[3] D. Barsky. — Congruences pour les nombres de Genocchi de deuxième espèce, Séminaire du Groupe d’étude d’Analyse ultramétrique, 8ème année (1980/81) 34, 01-013.

[4] J.P. Bauer. — Recherches autour d’une propriété classique de la fonction φ d’Euler, Ann. Sci. Univ. Besançon Math. (3) Fasc. 5 (1972).

[5] C.V.L. Charlier. — Arkiv für Mat. Astron. o. Fysik 2 (1905/06), Nr. 20.

[6] L. Comtet. — Advanced Combinatorics. — D. Reidel Publishing Company (1974).

[7] D. Dumont. — Étude combinatoire d’une suite de polynômes associés aux polynômes ultrasphériques,Publ. Elektr. Fak. Univ. Beograd, Ser. Mat. Fiz., 1979, p. 116-125.

[8] D. Dumont et G. Viennot. — A combinatorial interpretration of the Seidel generation of Genocchi numbers, Ann. Discr. Math, vol. 6, 1980, p. 77-87.

[9] R.C. Entringer. — A combinatorial interpretation of the Euler and Bernoulli numbers, Nieuw. Arch. V. Wiskunde, vol. 14, 1966, p. 241-6.

[10] L. Euler. — De differentis finitis, Opera Omnia, series prima. — vol. X, Teubner, 1913.

[11] L. Euler. — De transformatione serierum, Opera Omnia, series prima. — vol. X, Teubner, 1913.

[12] S. Even. — Algorithmic Combinatorics. — Mac Millan New York (1973), pages 55-65.

[13] D. Foata. — La série génératrice exponentielle dans les problèmes d’énumération. Presses de l’Université de Montréal, Montréal (1974).

[14] D. Foata et M.P. Schützenberger. — Théorie Géométrique des polynômes eulériens. — Lectures Notes in Math. n^{∘}./38 Springer-Verlag.

[15] I. J. Good. — The number of orderings of n candidates when ties are permitted, Fib. Quart, vol. 13, 1975, p. 11-18.

[16] O. A. Gross. — Preferential arrangements, Amer. Math. Monthly, vol. 69, 1962, p. 4-8.

[17] B. Harris et L. Schoenfeld. — The number of idempotent elements in symmetric semi-groups, Jour. of Comb. Theory, vol. 3, 1967, p. 122-35.

[18] C. Jordan. — Calculus of finite differences. — Chelsea, 1965.

[19] G. Kreweras. — The number of more or less “regular” permutations, Fib. Quart, vol. 18, 1980, p. 226-9.

[20] I. Lah. — Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung in der mathematischen Statistik, Mitteilungsbl. Math. Statist., vol. 7, 1955, p. 203-212.

[21] C.L. Liu. — Introduction to Combinatorial Mathematics. — Mc Graw Hill, 1968.

[22] P. A. Mac Mahon. — Collected papers. — M.I.T. Press (1978). p. 611.

[23] C. Radoux. — Une congruence pour les polynômes P_{n}(x) de fonction génératrice e^{x(e^{z}−1)}, C. R. Acad. Sc. Paris, vol. 284, 1977, p. 637-9.

[24] J. Riordan. — An Introduction to Combinatorial Theory. — Wiley (1958).

[25] J. Riordan. — Forest of labelled trees, Jour. of Comb. Theory, vol. 5, 1968, p. 90-103.

[26] D. Roselle. — Permutations by numbers of rises and successions, Proc. Amer. Math. Soc., vol. 19, 1968, p. 8-16.

[27] G. C. Rota. — Finite operator calculus. — Academic Press, 1975.

[28] L. Seidel. — Über eine einfache Enstehungsweise der Bernoullischen Zahlen und einiger verwandten Reihen, Sitzungsberichte der Münch. Akad. Math. Phys. Classe (1877) 157-187.

[29] L. Sinigallia. — Una estensione dei numeri Bernoulliani, Rendic. di Palermo (1908), 20-35.

[30] G. Szegö. — Orthogonal polynomials. — Amer. Math. Soc. Colloquim Publ., vol. 23 (1939) p. 33.

[31] W. J. Walker. — Algebraic and combinatorial results for ranking competitors in a sequence of races, Discr. Math, vol. 14, 1976, p. 297-304.

[32] Whitworth. — Choice and Chance. — London (1934), p. 87.

Compléments (1996)

Récemment, V.I. Arnold a retrouvé et réinterprété le triangle de Seidel des nombres d’Euler [33], puis introduit des paires de tableaux permettant le calcul des nombres de Springer [34]. On trouvera des paires de matrices de Seidel associées à ces paires de tableaux dans [36], ainsi que d’autres exemples, conduisant notamment à définir des nombres d’Euler “médians” qui sont une sorte d’analogue pour les nombres d’Euler des nombres de Genocchi de deuxième espèce.

[33] V.I. Arnold. — Bernoulli-Euler updown numbers associated with function singularities, their combinatorics and arithmetics, Duke Math. Jour., vol. 63, 1991, p. 1537-1555.

[34] V.I. Arnold. — The calculus of snakes and the combinatorics of Bernoulli, Euler and Springer numbers of Coxeter groups, Russian Math. Surveys, vol. 47/1, 1992, p. 1-51.

[35] D. Dumont, A. Randrianarivony. — Dérangements et nombres de Genocchi, Discrete Math., vol. 132, 1994, p. 37-49.

[36] D. Dumont. — Further triangles of Seidel-Arnold type and Continued Fractions related to Euler and Springer numbers, Advances in Applied Math., vol. 16, 1995, p. 275-296.

Dominique Dumont,

Département de mathématique, Université Louis Pasteur, 7, rue René-Descartes, F-67084 Strasbourg.