Atti del Convegno Internazionale di Studi Leonardo Fibonacci : il tempo, le opere, l’eredità scientifica, Pisa, 23–25 marzo 1994. a cura di Marcello Morelli e Marco Tangheroni. Pacini Editore, p. 179-208, 1994.

NOMBRES DE FIBONACCI ET POLYNÔMES ORTHOGONAUX

PAR

Dominique FOATA (^{∗}) ET Guo-Niu HAN (^{∗})

En hommage à Leonard Carlitz, pour sa maîtrise du Calcul.

R^{}ÉSUM^{}É. — Le calcul des séries de produits de nombres de Fibonacci et des polynômes de Tchebicheff des deux espèces est obtenu ici à l’aide de deux méthodes combinatoires.

ABSTRACT. — Series of products of Fibonacci numbers and of Tchebicheff of the two kinds are calculated by means of two combinatorial methods.

Quand la présente rencontre en l’honneur de Leonardo Fibonacci fut annoncée, il a fallu chercher dans les mathématiques d’aujourd’hui quelles étaient les références directes à Fibonacci. Tout mathématicien (ou informaticien, cf. [Kn68, p. 78 et suivantes]) connaît le nom de ce personnage important du tournant du treizième siècle à travers la suite des fameux nombres F_{n} (n ≥ 0), qui portent son nom. Nous rappellerons leur définition plus loin. Il est tout à fait remarquable, qu’encore aujourd’hui, une revue mathématique, à savoir le Fibonacci Quarterly, soit consacrée à l’étude (arithmétique, algébrique, géométrique) de cette suite de nombres et des nombres qui leur sont reliés. On peut même dire que sur de nombreux auteurs de cette revue, ces nombres exercent une véritable mystique. Il est aussi tout à fait inattendu, si l’on en croit les collègues mathématiciens de Pise, de savoir que ladite revue ne figure pas dans la bibliothèque de mathématique de leur Université !

DOMINIQUE FOATA ET GUO-NIU HAN

Notre première idée de contribution fut de parler des travaux de Leonard Carlitz, qui publia dans le Fibonacci Quarterly plusieurs articles très originaux. Le professeur John Brillhart (University of Arizona) est en train de réaliser une édition des travaux de Leonard Carlitz et nous avait aimablement fourni la liste des contributions de ce dernier. Nous citons simplement, en référence, trois de ses travaux ([Ca66], [Ca75], [Ca78]), concernant l’étude des nombres de Fibonacci en relation avec certains polynômes orthogonaux, ou certains polynômes importants, comme les polynômes Eulériens. Nous avons préféré ne pas donner suite à ce projet dans le présent cadre (l’article eût été trop long !). Signalons que le professeur Carlitz, âgé aujourd’hui de quatre-vingt-six ans, s’est retiré dans la ville de Durham, North Carolina, près de l’Université Duke, où il a fait la presque totalité de sa carrière.

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

L’objet du présent article est de reprendre le calcul des fonctions génératrices des produits de nombres de Fibonacci et aussi des produits de polynômes de Tchebicheff des deux espèces, utilisant des techniques essentiellement combinatoires. Nous présentons deux méthodes. La première repose simplement sur la formule banale

(0.1)  \frac{1}{1 − ∑_{x} x} = ∑_{w} w,

où x parcourt un alphabet 𝔛. Le développement du membre de droite est la somme formelle de tous les mots w = x_{i_{1}} … x_{i_{m}} en l’alphabet 𝔛. Il s’agira chaque fois de trouver le bon alphabet 𝔛, puis l’homomorphisme approprié, qui, appliqué aux deux membres de (0.1), fournira la fonction génératrice cherchée.

La seconde consiste à trouver un nombre suffisant d’équations linéaires que doit satisfaire la fonction génératrice, à écrire ce système d’équations, à le résoudre (éventuellement à l’aide de logiciels de calcul formel !) pour en tirer l’expression de la fonction génératrice cherchée.

La récurrence bien connue des nombres de Fibonacci s’écrit

(0.2)  F_{0} = 1,  F_{1} = 1,  F_{n+2} = F_{n+1} + F_{n} (n ≥ 0),

d’où F_{0} = F_{1} = 1, F_{2} = 2, F_{3} = 3, F_{4} = 5, …

Les récurrences des polynômes de Tchebicheff de première espèce (T_{n}(x)) et de seconde espèce (U_{n}(x)) (n ≥ 0) sont les mêmes et s’écrivent

(0.3)  T_{n+1}(x) = 2xT_{n}(x) − T_{n−1}(x); (n ≥ 1),

(même relation en remplaçant les T par des U), mais les conditions initiales sont différentes : T_{0}(x) = U_{0}(x) = 1, T_{1}(x) = x, U_{1}(x) = 2x.

NOMBRES DE FIBONACCI ET POLYNÔMES ORTHOGONAUX

Les deux relations de récurrence ci-dessus étant linéaires, les fonctions génératrices des F_{n}, des T_{n}(x) et des U_{n}(x) sont des fractions rationnelles, comme il est bien connu (cf., par exemple, l’excellent article par Cerlienco, Mignotte et Piras [CeMi87]). Comme aussi indiqué dans cet article, la fonction génératrice des produits d’Hadamard de ces suites est aussi une fraction rationnelle, comme par exemple, les séries ∑ F_{n}^{2} u^{n}, ∑ F_{n}T_{n}(x)u^{n}, ou bien encore ∑ F_{n}T_{n}(x)U_{n}(y)u^{n}, … Il n’y a donc pas lieu de s’éterniser sur ce résultat, mais plutôt de fournir des méthodes pour le calcul effectif de ces fractions rationnelles. Récemment, Supper [Su92] a développé une technique analytique lui permettant de sommer une grande classe de séries de produits de polynômes orthogonaux. Sa méthode lui permet naturellement de sommer aussi les séries de produits de polynômes de Tchebicheff et de nombres de Fibonacci.

Comme dit plus haut, nous présentons ici deux méthodes combinatoires de sommation. La première reprend simplement celle développée par Shapiro [Sh81] et illustre bien le fait que les polynômes de Tchebicheff ne sont que des fonctions génératrices sur des objets combinatoires, appelés plus loin rubans (de Fibonacci), par un certain poids (cf. sections 1–8). Lorsque le poids est réduit à l’unité, le polynôme est simplement le nombre de Fibonacci.

La seconde méthode consiste à regarder la géométrie de ces rubans et à traduire les propriétés géométriques en équations algébriques. Lorsque le nombre de ces équations est suffisamment grand, on résout le système obtenu, pour en tirer la fonction génératrice désirée (cf. section 9 et 10). Nous terminons l’article par une table des séries génératrices effectivement calculées.

1. Une identité banale. — Reprenons l’identité (0.1) en supposant que l’alphabet 𝔛 se compose de deux symboles, un monomino et un domino . Chaque mot w en ces deux symboles peut être vu comme un ruban fait de monominos (notons |w|_{1} leur nombre) et de dominos (notons |w|_{2} le second nombre). Appelons longueur ou degré de w le nombre

deg(w) = |w|_{1} + 2|w|_{2}

et pour chaque n ≥ 0 désignons par 𝔉_{n} l’ensemble des rubans w de degré deg(w) = n. Chaque mot w ∈ 𝔉_{n} (n ≥ 2) peut être obtenu de deux façons différentes : on peut soit ajouter à un mot de 𝔉_{n−2}, soit à un mot de 𝔉_{n−1}. On a donc

𝔉_{0} = {∅}, 𝔉_{1} = { }, 𝔉_{n} = 𝔉_{n−1} + 𝔉_{n−2} (n ≥ 2). En comparant avec (0.2), on a donc

F_{n} = #𝔉_{n} (cardinal de 𝔉_{n}) (n ≥ 0).

(Voir la liste des premiers 𝔉_{n} en fin de section.)

L’identité (0.1) peut se récrire :

(1.1)  (1 − ( +  ))^{−1}= ∑_{n≥0} ∑_{w∈𝔉_{n}} w.

Pour chaque mot w définissons

(1.2)  φ(w) = u^{deg(w)}.

Quand l’homomorphisme (continu) φ est appliqué aux deux membres de l’identité (1.1), on obtient l’identité suivante dans l’algèbre des séries formelles en une variable u :

(1.3)  \frac{1}{1 − u − u^{2}} = ∑_{n≥0} φ(𝔉_{n}) = ∑_{n≥0} u^{n} F_{n}.

Liste des premiers 𝔉_{n} :

\begin{matrix}𝔉_{1} : \\ 𝔉_{2} : \\ 𝔉_{3} : \\ 𝔉_{4} : \end{matrix}

2. Autres homomorphismes. — Nous pouvons également définir l’application ψ_{x} qui envoie tout ruban w sur x^{|w|_{1}}X^{|w|_{2}}, où x et X sont deux variables commutatives, puis définir φ_{x}(w) = u^{deg(w)}ψ_{x}(w). En particulier, ψ_{x}( ) = x et ψ_{x}( ) = X. L’image de (1.1) par φ_{x} donne

(2.1)  (1 − ux − u^{2}X)^{−1} = ∑_{n≥0} ∑_{w∈𝔉_{n}} φ_{x}(w) = ∑_{n≥0} u^{n} ψ_{x}(𝔉_{n}),

avec ψ_{x}(𝔉_{n}) = ∑_{w} ψ_{x}(w) (w ∈ 𝔉_{n}).

Dans (2.1) faisons les substitutions x ← 2x et X ← −1. Le membre de gauche devient (1 − 2xu + u^{2})^{−1}, qui est l’expression bien connue de la fonction génératrice des polynômes de Tchebicheff de seconde espèce U_{n}(x) (cf., par exemple, [Ra60, p. 301–302]). Par conséquent,

(2.2)  U_{n}(x) = ψ_{x}(𝔉_{n})  (avec x ← 2x, X ← −1).

Nous pouvons faire une discrimination plus fine sur les rubans : pour chaque n ≥ 1 soit G_{n} (resp. H_{n}) l’ensemble des rubans w ∈ 𝔉_{n} dont la composante la plus à gauche est un monomino (resp. domino). Il est clair que les fonctions génératrices de ces deux familles sont données par :

(2.3)  (1 − ( +  ))^{−1} = ∑_{n≥1} ∑_{w∈G_{n}} w;
(2.4)  (1 − ( +  ))^{−1} = ∑_{n≥1} ∑_{w∈H_{n}} w.

L’image par φ_{x} de ces deux identités donne :

(2.5)  ux(1 − ux − u^{2}X)^{−1} = ∑_{n≥1} u^{n} ψ_{x}(G_{n});
(2.6)  u^{2}X(1 − ux − u^{2}X)^{−1} = ∑_{n≥1} u^{n} ψ_{x}(H_{n}).

Nous pouvons alors calculer la fonction génératrice des combinaisons linéaires aψ_{x}(G_{n}) + bψ_{x}(H_{n}) (n ≥ 1), où a et b sont deux constantes et obtenir :

(2.7) \frac{1 + u(a − 1)x + u^{2}(b − 1)X}{1 − ux − u^{2}X} = 1 + ∑_{n≥1} u^{n} (a ψ_{x}(G_{n}) + b ψ_{x}(H_{n})).

La formule (2.7) a trois spécialisations importantes :

(i) x = X = a = b = 1 et on retrouve la fonction génératrice (1.3) des nombres de Fibonacci ;

(ii) les substitutions x ← 2x, X ← −1, a ← 1, b ← 1 redonnent la fonction génératrice des polynômes de Tchebicheff de seconde espèce U_{n}(x) déjà mentionnée ;

(iii) les substitutions x ← 2x, X ← −1, a ← \frac{1}{2}, b ← 1 fournissent la fonction génératrice des polynômes de Tchebicheff de première espèce T_{n}(x) [Ra60, p. 301–302] :

(2.8) \frac{1 − ux}{1 − 2xu + u^{2}} = ∑_{n≥0} u^{n} T_{n}(x),

de sorte que

(2.9)  T_{n}(x) = \frac{1}{2}ψ_{x}(G_{n}) + ψ_{x}(H_{n})  (n ≥ 1).

3. Extension au cas des multi-rubans. — La méthode précédente peut être aussi utilisée pour le calcul des séries de produits de polynômes classiques. Pour chaque n ≥ 1, considérons les produits cartésiens 𝔉_{n}^{(m)} = (𝔉_{n})^{m} (m ≥ 2) de rubans d’ordre m, qu’on peut représenter comme m rubans remplis de monominos et de dominos, de même longueur n, placés l’un au-dessus de l’autre. On dira qu’un tel m-ruban est aussi de longueur n.

Notons 𝔉^{(m)} l’ensemble de tous les rubans d’ordre m [en abrégé : des mrubans]. Ils se présentent comme des mots dans un certain alphabet 𝔛^{(m)}, composé de m-rubans que l’on ne peut plus décomposer en m-rubans plus courts. Appelons irréductibles ces m-rubans. Pour chaque n ≥ 1 notons 𝔛_{n}^{(m)} le sous-ensemble de 𝔉_{n}^{(m)} formé par les m-rubans irréductibles.

Par exemple, pour m = 2 et n = 1, 2, 3, la liste de tous les rubans d’ordre 2 est la suivante

𝔉_{1}^{(2)} : ;
𝔉_{2}^{(2)} :  ^{,  ,  ,  ;}
𝔉_{3}^{(2)} :  ^{,  ,  ,  ,  ,  ,}
,  ,  ;

tandis que pour m = 2 et n = 1, 2, 3, 4 les 2-rubans irréductibles sont les suivants :

𝔛_{1}^{(2)} : ; 𝔛_{2}^{(2)} :  ,  ,  ; 𝔛_{3}^{(2)} :  ,  ;
𝔛_{4}^{(2)} :  ,  .

L’identité (0.1) peut se récrire

(1 − ∑_{f∈𝔛^{(m)}} f)^{−1} = ∑_{f∈𝔉^{(m)}} f,

ou simplement

(1 − ∑_{n≥1} 𝔛_{n}^{(m)})^{−1} = ∑_{n≥0} 𝔉_{n}^{(m)},

ou encore (3.1) (1 − 𝔛^{(m)})^{−1} = 𝔉^{(m)},

si l’on identifie chaque ensemble de mots avec la somme formelle de ses éléments.

Pour m = 2 l’identité précédente prend la forme :

(3.2) (1 − ( +  +  +  +  +  + ⋯))^{−1}
= 1 + +  +  +  +  +  +  +  + ⋯

Notre première tâche est de calculer 𝔛^{(m)} à partir de 𝔛^{(m−1)} pour chaque m ≥ 2. On obtient un m-ruban irréductible de 𝔛_{n}^{(m)} de deux façons différentes. La première façon consiste à partir d’un (m − 1)-ruban irréductible dans 𝔛_{n}^{(m−1)} et à placer au-dessous de lui n’importe quel ruban de 𝔉_{n}.

Par exemple, suivant ce procédé, le 2-ruban irréductible suivant donne naissance à trois 3-rubans irréductibles :

↦  ,  ,  .

Notons \binom{𝔛_{n}^{(m−1)}}{𝔉_{n}} l’ensemble des m-rubans irréductibles obtenus de cette façon.

La seconde façon consiste à partir d’un (m − 1)-ruban g, non irréductible ; soit g_{1}g_{2} … g_{r} (r ≥ 2) sa factorisation en (m−1)-rubans irréductibles. En plaçant un ruban sous g, on obtient un m-ruban irréductible, si et seulement si, pour chaque i = 1, 2, …, r − 1 on place un domino ayant un bord commun avec g_{i} et g_{i+1}, les espaces restants étant remplis par n’importe quel ruban de longueur appropriée.

Le diagramme suivant illustre cette propriété :

↦

Un tel placement de dominos est toujours possible lorsque r = 2. Quand r ≥ 3, le placement n’est possible que si les longueurs des facteurs g_{2}, g_{3}, …, g_{r−1} sont tous au moins égaux à 2. Le ruban qui doit être placé sous un tel (m − 1)-ruban est donc de la forme

h_{1}  h_{2}  h_{3} … h_{r−1}  h_{r},

avec deg(h_{1}) = deg(g_{1}) − 1 ≥ 0, deg(h_{2}) = deg(g_{2}) − 2 ≥ 0, deg(h_{3}) = deg(g_{3}) − 2 ≥ 0, …, deg(h_{r−1}) = deg(g_{r−1}) − 2 ≥ 0, deg(h_{r}) = deg(g_{r}) − 1 ≥ 0.

Réciproquement, si g_{1}, g_{2}, …, g_{r} sont r (m − 1)-rubans irréductibles et si h_{1}, h_{2}, …, h_{r} sont r rubans, dont les degrés respectifs satisfont les relations précédentes, le placement de h_{1} h_{2} h_{3} … h_{r−1} h_{r} sous le produit g_{1}g_{2} … g_{r} fournira un m-ruban f irréductible.

Nous dirons que le produit \binom{g_{1}}{h_{1}}\binom{g_{2}}{h_{2}} … \binom{g_{r}}{h_{r}} est la factorisation du

m-ruban irréductible f en composants décalés.

La somme formelle de tous les composants décalés de la forme \binom{g_{1}}{h_{1}}

(resp. \binom{g_{r}}{h_{r}}) est égal à ∑_{n≥1} \binom{𝔛_{n}^{(m−1)}}{𝔉_{n−1}}, tandis que la somme des com-

posants décalés des facteurs intérieurs \binom{g_{i}}{h_{i}} (2 ≤ i ≤ r − 1) est égale à

∑_{n≥2} \binom{𝔛_{n}^{(m−1)}}{𝔉_{n−2}}.

Par conséquent, la somme formelle de tous les m-rubans irréductibles est donnée par :

(3.3) 𝔛^{(m)} = ∑_{n≥1} \binom{𝔛_{n}^{(m−1)}}{𝔉_{n}}

+ ∑_{n≥1} \binom{𝔛_{n}^{(m−1)}}{𝔉_{n−1}} \frac{1}{1 − ∑_{n≥2} \binom{𝔛_{n}^{(m−1)}}{𝔉_{n−2}}} ∑_{n≥1} \binom{𝔛_{n}^{(m−1)}}{𝔉_{n−1}}.

Pour m = 2 l’identité (3.3) prend la forme :

(3.4) 𝔛^{(2)} = + +

+ ( +  )\frac{1}{1 −}  (  +  ).

4. Autres identités formelles. — Pour le calcul de la fonction génératrice des polynômes de Tchebicheff de première espèce une discrimination supplémentaire a été introduite. Notons G = ⋃ G_{n} et H = ⋃ H_{n} l’ensemble des rubans débutant par un monomino et un domino, respectivement.

Pour m = 2, on distingue quatre sortes de 2-rubans. On note 𝔉^{GG} (resp. 𝔉^{GH}, resp. 𝔉^{HG}, resp. 𝔉^{HH}) l’ensemble des 2-rubans dont l’extrémité

gauche est (resp.  , resp.  , resp.  ). Si w est l’un des quatre

mots GG, GH, HG, HH, on pose 𝔛^{w} = 𝔉^{w} ∩ 𝔛^{(2)}. Les deux ensembles

𝔛^{GG} et 𝔛^{HH} sont les singletons { } et { }, respectivement. En

revanche, on a

(4.1)  𝔛^{GH} =  \frac{1}{1 −}  ( +  ).

et une identité analogue pour 𝔛^{HG}.

De même pour m = 3, on peut distinguer huit sortes de 3-rubans, suivant l’extrémité gauche de ceux-ci. Utilisant les mêmes notations que ci-dessus, en particulier en prenant pour w un mot de trois lettres en l’alphabet {G, H}, on définit de même les ensembles 𝔉^{w} et 𝔛^{w}. Les ensembles 𝔛^{GGG} et 𝔛^{HHH} sont des singletons, mais pour chaque autre ensemble 𝔛^{w}, on peut obtenir une équation génératrice comme

(4.2)  𝔛^{GGH} = \frac{1}{1 − ∑_{n≥2} \binom{𝔛_{n}^{(2)}}{𝔉_{n−2}}} ∑_{n≥1} \binom{𝔛_{n}^{(2)}}{𝔉_{n−1}},

pour l’ensemble des 3-rubans irréductibles débutant par .

5. Homomorphismes. — Soient u, x_{1}, x_{2}, …, X_{1}, X_{2}, … des variables commutatives et m ≥ 2. Si f est un m-ruban formé des rubans f_{1}, …, f_{m} (de haut en bas), de longueur n, on définit :

ψ_{i}(f_{i}) = x_{i}^{|f_{i}|_{1}}X_{i}^{|f_{i}|_{2}} (i = 1, …, m) ;
Ψ(f) = ψ_{1}(f_{1}) … ψ_{m}(f_{m}) ; Φ(f) = Ψ(f)u^{n}.

En particulier, si g est le (m−1)-ruban g = (f_{1}, …, f_{m−1}), on peut écrire : Φ(f) = Ψ(g)u^{n}ψ_{m}(f_{m}).

L’image de l’identité (3.3) par Φ donne alors :

\begin{aligned}Φ(𝔛^{(m)}) & =∑_{n≥1}Ψ(𝔛_{n}^{(m−1)})u^{n}ψ_{m}(𝔉_{n})+X_{m}(∑_{n≥1}Ψ(𝔛_{n}^{(m−1)})u^{n}ψ_{m}(𝔉_{n−1}))^{2} \\ & × (1 − X_{m} ∑_{n≥2} Ψ(𝔛_{n}^{(m−1)})u^{n}ψ_{m}(𝔉_{n−2}))^{−1} \end{aligned}

On est ainsi amené à introduire une variable auxiliaire v, à définir Φ(f; v) = Φ(f)v^{n} = Ψ(f)u^{n}v^{n}, si f est de longueur n, et à introduire une opération de décalage δ_{m} de la façon suivante :

δ_{m}Φ(𝔛^{(m−1)}; v) = ∑_{n≥1}Ψ(𝔛_{n}^{(m−1)})u^{n}v^{n−1}.

On en déduit

∑_{n≥1} Ψ(𝔛_{n}^{(m−1)})u^{n}ψ_{m}(𝔉_{n−1}) = δ_{m} Φ(𝔛^{(m−1)}; ψ_{m}(𝔉)),

et

∑_{n≥2}Φ(𝔛_{n}^{(m−1)})u^{n} ψ_{m}(𝔉_{n−2}) = δ_{m}^{2} Φ(𝔛^{(m−1)}; ψ_{m}(𝔉)),

utilisant la notation ombrale : (ψ_{m}(𝔉))^{n} = ψ_{m}(𝔉_{n}). Notons que le décalage δ_{m} doit être appliqué avant de faire la substitution v ← ψ_{m}(𝔉).

On a donc l’identité :

(5.1) Φ(𝔛^{(m)}) = Φ(𝔛^{(m−1)}; ψ_{m}(𝔉)) + X_{m}(δ_{m}Φ(𝔛^{(m−1)}; ψ_{m}(𝔉)))^{2}

× (1 − X_{m} δ_{m}^{2} Φ(𝔛^{(m−1)}; ψ_{m}(𝔉)))^{−1}.

6. Le cas binaire. — Utilisons les variables x, y, X, Y, au lieu des variables x_{1}, x_{2}, X_{1}, X_{2}. On a :

Φ(𝔛^{(1)}) = ux + u^{2}X,
Φ(𝔛^{(1)}; v) = uxv + u^{2}Xv^{2},

d’où

δ_{2}Φ(𝔛^{(1)}; v) = ux + u^{2}Xv,
δ_{2}^{2}Φ(𝔛^{(1)}; v) = u^{2}X.

Par conséquent,

Φ(𝔛^{(1)}; ψ_{2}(𝔉)) = uxψ_{2}(𝔉) + u^{2}X(ψ_{2}(𝔉))^{2}
= uxψ_{2}(𝔉_{1}) + u^{2}Xψ_{2}(𝔉_{2})
= uxy + u^{2}X(y^{2} + Y),

et

δ_{2}Φ(𝔛^{(1)}; ψ_{2}(𝔉)) = ux + u^{2}Xy,
δ_{2}^{2}Φ(𝔛^{(1)}; ψ_{2}(𝔉)) = u^{2}X.

La formule (5.1) pour m = 2 (ou directement la formule (3.4) lorsqu’on lui applique l’homomorphisme Φ) entraîne alors :

Φ(𝔛^{(2)}) = uxy + u^{2}X(y^{2} + Y) + Y (ux + u^{2}Xy)^{2}(1 − u^{2}XY)^{−1}.

On en tire :

(6.1) \begin{matrix}Φ(𝔉^{(2)}) & = (1 − Φ(𝔛^{(2)})^{−1} \\ & = \frac{1 − u^{2}XY}{1 − uxy − u^{2}(2XY + x^{2}Y + y^{2}X)−u^{3}xyXY +u^{4}X^{2}Y^{2}} . \end{matrix}

D’autre part, l’image par Φ de l’identité (4.1) s’écrit :

(6.2)  Φ(𝔛^{GH}) = u^{2}xY (x + uXy)(1 − u^{2}XY)^{−1},

d’où

(6.3)  Φ(𝔛^{HG}) = u^{2}Xy(y + uxY)(1 − u^{2}XY)^{−1}.

Le calcul des fonctions génératrices

∑_{n≥1} u^{n} ψ_{x}(G_{n})ψ_{y}(G_{n}), ∑_{n≥1} u^{n} ψ_{x}(G_{n})ψ_{y}(H_{n}), ∑_{n≥1} u^{n} ψ_{x}(H_{n})ψ_{y}(H_{n}),

se fait alors comme suit. On a d’abord les identités formelles

(1 − 𝔛^{(2)})^{−1} = ∑_{n≥1} G_{n} × G_{n};
𝔛^{GH}(1 − 𝔛^{(2)})^{−1} = ∑_{n≥1} G_{n} × H_{n};
𝔛^{HG}(1 − 𝔛^{(2)})^{−1} = ∑_{n≥1} H_{n} × G_{n};

(1 − 𝔛^{(2)})^{−1} = ∑_{n≥2} H_{n} × H_{n};

qui expriment le fait que chaque 2-ruban de G_{n} × G_{n} (resp. de G_{n} × H_{n}, resp. de H_{n} × G_{n}, resp. de H_{n} × H_{n}) débute par un monomino (resp. un élément de 𝔛^{GH}, resp. un élément de 𝔛^{HG}, resp. un domino). Leur image par Φ donne :

\begin{aligned}uxy(1 − Φ(𝔛^{(2)}))^{−1} & = ∑_{n≥1} u^{n} ψ_{1}(G_{n})ψ_{2}(G_{n}) ; \\ Φ(𝔛^{GH})(1 − Φ(𝔛^{(2)}))^{−1} & = ∑_{n≥2} u^{n} ψ_{1}(G_{n})ψ_{2}(H_{n}) ; \\ Φ(𝔛^{HG})(1 − Φ(𝔛^{(2)}))^{−1} & = ∑_{n≥2} u^{n} ψ_{1}(H_{n})ψ_{2}(G_{n}) ; \\ u^{2}XY (1 − Φ(𝔛^{(2)}))^{−1} & = ∑_{n≥2} u^{n} ψ_{1}(H_{n})ψ_{2}(H_{n}). \end{aligned}

De là

(6.4) 1 + ∑_{n≥1} u^{n} (a ψ_{1}(G_{n}) + b ψ_{1}(H_{n}))(c ψ_{2}(G_{n}) + d ψ_{2}(H_{n}))

\begin{matrix}= 1 + (1 − Φ(𝔛^{(2)}))^{−1} \\ × (u ac xy + ad Φ(𝔛^{GH}) + bc Φ(𝔛^{HG}) + u^{2} bd XY ) \end{matrix}

= \frac{N}{D} ,

avec

N = 1 + uxy(ac − 1)
+ u^{2}(XY (bd − 2) + x^{2}Y (ad − 1) + y^{2}X(bc − 1))
+ u^{3}xyXY (bc + ad − ac − 1) + u^{4}X^{2}Y^{2}(1 − bd) ;
D =1 − uxy − u^{2}(2XY + x^{2}Y + y^{2}X)−u^{3}xyXY +u^{4}X^{2}Y^{2}.

L’identité (6.4) a six spécialisations déjà parues dans la littérature. Les références seront données plus bas.

(1) Avec a = b = c = d = x = y = X = Y = 1, la formule (6.4) est simplement la fonction génératrice des carrés des nombres de Fibonacci :

(6.5)  ∑_{n≥0} F_{n}^{2} u^{n} = \frac{1 − u^{2}}{1 − u − 4u^{2} − u^{3} + u^{4}} = \frac{1 − u}{1 − 2u − 2u^{2} + u^{3}} .

(2) Avec a = b = x = X = 1, c = d = 1, y ← 2x, Y ← −1, on obtient la fonction génératrice des produits des nombres de Fibonacci par les polynômes de Tchebicheff de seconde espèce :

(6.6)  ∑_{n≥0} u^{n} F_{n}U_{n}(x) = \frac{1 + u^{2}}{1 − u 2x + u^{2}(3 − 4x^{2}) + u^{3} 2x + u^{4}} .

(3) Avec a = b = x = X = 1, c = \frac{1}{2}, d = 1, y ← 2x, Y ← −1 on obtient la fonction génératrice des produits des nombres de Fibonacci par les polynômes de Tchebicheff de première espèce :

(6.7)  ∑_{n≥0} u^{2} F_{n}T_{n}(x) = \frac{1 − u x + u^{2}(1 − 2x^{2})}{1 − u 2x + u^{2}(3 − 4x^{2}) + u^{3} 2x + u^{4}} .

(4) La fonction génératrice des produits de polynômes de Tchebicheff de première espèce est égale à (1 − Φ(𝔛^{(2)}))^{−1}, avec les substitutions x ← 2x, X ← −1, y ← 2y, Y ← −1. Elle peut aussi s’obtenir de (6.4), avec ces mêmes substitutions, plus a = b = c = d = 1. On obtient : (6.8)

∑_{n≥0} u^{n} U_{n}(x)U_{n}(y) = \frac{1 − u^{2}}{1 − u 4xy + u^{2}(4x^{2} + 4y^{2} − 2) − u^{3} 4xy + u^{4}} .

(5) Avec les substitutions a = b = 1, x ← 2x, X ← −1, c = \frac{1}{2}, d = 1, y ← 2y, Y ← −1 on obtient la fonction génératrice des produits des polynômes de Tchebicheff des deux espèces : (6.9)

∑_{n≥0} u^{n} U_{n}(x)T_{n}(y) = \frac{1 − u 2xy + u^{2}(2y^{2} − 1)}{1 − u 4xy + u^{2}(4x^{2} + 4y^{2} − 2) − u^{3} 4xy + u^{4}} .

(6) Finalement, la fonction génératrice des produits de polynômes de Tchebicheff de seconde espèce s’obtient par les substitutions : a = \frac{1}{2}, b = 1, x ← 2x, X ← −1, c = \frac{1}{2}, d = 1, y ← 2y, Y ← −1 : (6.10)

∑_{n≥0} u^{n} T_{n}(x)T_{n}(y) = \frac{1 − u 3xy + u^{2}(2x^{2} + 2y^{2} − 1) − u^{3} xy}{1 − u 4xy + u^{2}(4x^{2} + 4y^{2} − 2) − u^{3} 4xy + u^{4}} .

Toutes les formules (6.5)–(6.10) ont été obtenues par Supper [Su92] (voir aussi [Av88] et [AvSu91]) par des méthodes analytiques reposant sur une réinterprétation de la G-fonctionnelle introduite par Avanissian et Gay [AvGa75]. Comme dit plus haut, la méthode utilisée dans ce paragraphe est essentiellement celle de Shapiro [Sh81], qui a obtenu les formules (6.5), (6.8) et (6.10).

7. Le cas ternaire. — D’après la formule (5.1), la série Φ(𝔛^{(3)}) s’exprime à l’aide de Φ(𝔛^{(2)}; v), de δ_{3} Φ(𝔛^{(2)}; v) et de δ_{3}^{2} Φ(𝔛^{(2)}; v), une fois faite la substitution v ← ψ_{3}(𝔉). Or d’après (6.1) on a :

Φ(𝔛^{(2)}; v) = uxyv + u^{2}X(y^{2} + Y)v^{2}
+ Y (uxv + u^{2}Xyv^{2})^{2}(1 − u^{2}XY v^{2})^{−1}

= uxyv + u^{2}XY v^{2} + (\frac{x^{2}}{X} + \frac{y^{2}}{Y} ) ∑_{n≥1}(u\sqrt{XY})^{2n}v^{2n}

+ \frac{2xy}{\sqrt{XY}} ∑_{n≥1}(u\sqrt{XY})^{2n+1}v^{2n+1}.

δ_{3} Φ(𝔛^{(2)}; v) = uxy + u^{2}XY v

+ u\sqrt{XY} (\frac{x^{2}}{X} + \frac{y^{2}}{Y} ) ∑_{n≥1}(u\sqrt{XY})^{2n−1}v^{2n−1}

+ u 2xy ∑_{n≥1}(u\sqrt{XY})^{2n}v^{2n}.

δ_{3}^{2} Φ(𝔛^{(2)}; v) = u^{2} XY + u^{2}(x^{2}Y + y^{2}X) ∑_{n≥0}(u\sqrt{XY})^{2n}v^{2n}

+ u^{2} 2xy\sqrt{XY} ∑_{n≥1}(u\sqrt{XY})^{2n−1}v^{2n−1}.

Désignons par Γ(u, x, X) la fonction génératrice des ψ_{x}(𝔉_{n}) (n ≥ 0) telle qu’elle est définie en (2.1), par Γ_{0}(u, x, X) celle des termes pairs ψ_{x}(𝔉_{2n}) et par Γ_{1}(u, x, X) celle des termes impairs ψ_{x}(𝔉_{2n+1}) (n ≥ 0). On a :

Γ_{0}(u, x, X) = ∑_{n≥0} u^{2n}ψ_{x}(𝔉_{2n}) = \frac{1}{2}(Γ(u, x, X) + Γ(−u, x, X)) = \frac{1 − u^{2}X}{D};

Γ_{1}(u, x, X) = ∑_{n≥0} u^{2n+1}ψ_{x}(𝔉_{2n+1}) = \frac{1}{2}(Γ(u, x, X) − Γ(−u, x, X)) = \frac{ux}{D};

où D = 1 − u^{2}(x^{2} + 2X) + u^{4}X^{2}.

Lorsqu’on fait la substitution v ← ψ_{3}(𝔛) dans les trois expressions précédentes contenant 𝔛^{(2)} et qu’on utilise les variables z et Z à la place de x_{3} et X_{3}, on trouve :

Φ(𝔛^{(2)}; ψ_{3}(𝔛)) = uxyz + u^{2}XY (z^{2} + Z)

+ (\frac{x^{2}}{X} + \frac{y^{2}}{Y} )(Γ_{0}(u\sqrt{XY} , z, Z) − 1)

+ \frac{2xy}{\sqrt{XY}} (Γ_{1}(u\sqrt{XY} , z, Z) − u\sqrt{XY} z).

δ_{3} Φ(𝔛^{(2)}; ψ_{3}(𝔛)) = uxy + u^{2}XY z

+ u\sqrt{XY} (\frac{x^{2}}{X} + \frac{y^{2}}{Y} )Γ_{1}(u\sqrt{XY} , z, Z)

+ u 2xy(Γ_{0}(u\sqrt{XY} , z, Z) − 1);

δ_{3}^{2} Φ(𝔛^{(2)}; ψ_{3}(𝔛)) = u^{2}XY + u^{2}(x^{2}Y + y^{2}X)Γ_{0}(u\sqrt{XY} , z, Z)

+ u^{2} 2xy\sqrt{XY} Γ_{1}(u\sqrt{XY} , z, Z).

Or

Γ_{0}(u\sqrt{XY} , z, Z) = \frac{1 − u^{2}XY Z}{1 − u^{2}XY (z^{2} + 2Z) + u^{4}X^{2}Y^{2}Z^{2}} ;
Γ_{1}(u\sqrt{XY} , z, Z) = \frac{u\sqrt{XY} z}{1 − u^{2}XY (z^{2} + 2Z) + u^{4}X^{2}Y^{2}Z^{2}} .

En utilisant la formule (5.1) pour m = 3, on a donc tous les éléments pour calculer Φ(𝔛^{(3)}). Naturellement, l’utilisation d’un logiciel de calcul formel, comme MAPLE est approprié pour un tel calcul. En particulier,

(7.1) Φ(𝔉^{(3)})= ∑_{n≥0} u^{n}ψ_{1}(𝔉_{n})ψ_{2}(𝔉_{n})ψ_{3}(𝔉_{n}) = (1 − Φ(𝔛^{(3)}))^{−1}= \frac{N}{D} ,

avec (en utilisant les notations habituelles pour les fonctions symétriques)

\begin{aligned}N & = 1 − u^{2}(∑ XY z^{2} + 3XY Z) − 2u^{3}xXyY zZ \\ & + u^{4}(3X^{2}Y^{2}Z^{2} + ∑ x^{2}XY^{2}Z^{2}) − u^{6}X^{3}Y^{3}Z^{3} ; \end{aligned}

D = 1 − uxyz − u^{2}(4XY Z + 2 ∑ XY z^{2} + ∑ x^{2}y^{2}Z)
− u^{3}(∑ x^{3}yY zZ + 5xXyY zZ)

+ u^{4}(∑ X^{2}y^{4}Z^{2} + 6X^{2}Y^{2}Z^{2} + x^{2}Xy^{2}Y z^{2}Z + 4 ∑ X^{2}y^{2}Y Z^{2})

+ u^{5}(∑ xX^{2}yY^{2}z^{3}Z + 5xX^{2}yY^{2}zZ^{2})
− u^{6}(∑ x^{2}X^{2}Y^{3}z^{2}Z^{2} + 2 ∑ x^{2}X^{2}Y^{3}Z^{3} + 4X^{3}Y^{3}Z^{3})
+ u^{7}xX^{3}yY^{3}zZ^{3} + u^{8}X^{4}Y^{4}Z^{4}.

8. Autres identités d’ordre trois. — Pour permettre de calculer la série génératrice

∑_{n≥0} u^{n}ψ_{1}(J_{n})ψ_{2}(K_{n})ψ_{3}(L_{n}),

où J, K et L sont égaux à G ou à H, nous devons évaluer les séries Φ(𝔛^{GGG}), …, Φ(𝔛^{HHH}). D’après (6.2) et (6.3), on a tout d’abord :

Φ(𝔛^{GH}) = \frac{x^{2}}{X} ∑_{n≥1}(u\sqrt{XY})^{2n} + \frac{xy}{\sqrt{XY}} ∑_{n≥1}(u\sqrt{XY})^{2n+1}

d’où

Φ(𝔛^{GH}; ψ_{3}(𝔛)) = \frac{x^{2}}{X} (Γ_{0}(u\sqrt{XY} , z, Z) − 1)

+ \frac{xy}{\sqrt{XY}} (Γ_{1}(u\sqrt{XY} , z, Z) − u\sqrt{XY} z);

δ_{3} Φ(𝔛^{GH}; ψ_{3}(𝔛)) = u\frac{x^{2}}{X} \sqrt{XY} Γ_{1}(u\sqrt{XY} , z, Z)

+ uxy(Γ_{0}(u\sqrt{XY} , z, Z) − 1);

δ_{3}^{2} Φ(𝔛^{GH}; ψ_{3}(𝔛)) = u^{2}x^{2}Y Γ_{0}(u\sqrt{XY} , z, Z)

+ u^{2}xy\sqrt{XY} Γ_{1}(u\sqrt{XY} , z, Z) ;

δ_{3}^{3} Φ(𝔛^{GH}; ψ_{3}(𝔛)) = u^{3}x^{2}Y \sqrt{XY} Γ_{1}(u\sqrt{XY} , z, Z)

+ u^{3}xyXY Γ_{0}(u\sqrt{XY} , z, Z).

On a les mêmes formules pour Φ(𝔛^{HG}; ψ_{3}(𝔛)) et ses décalés par δ_{3} en permutant dans les formules précédentes les rôles de x et y et de X et Y.

On établit alors, sans difficulté, les identités suivantes :

Φ(𝔛^{GGG}) = uxyz;
Φ(𝔛^{GGH}) = uxy(1 − Zδ_{3}^{2} Φ(𝔛^{(2)}; ψ_{3}(𝔛)))^{−1}Zδ_{3} Φ(𝔛^{(2)}; ψ_{3}(𝔛)) ;
Φ(𝔛^{GHG}) = subs({y = z, z = y, Y = Z, Z = Y }, Φ(𝔛^{GGH})) ;
Φ(𝔛^{HGG}) = subs({x = z, z = x, X = Z, Z = X}, Φ(𝔛^{GGH})) ;
Φ(𝔛^{GHH}) = Zδ_{3}^{2} Φ(𝔛^{GH}; ψ_{3}(𝔛)) + Zδ_{3}^{3} Φ(𝔛^{GH}; ψ_{3}(𝔛))

× (1 − Zδ_{3}^{2} Φ(𝔛^{(2)}; ψ_{3}(𝔛)))^{−1} Zδ_{3} Φ(𝔛^{(2)}; ψ_{3}(𝔛)) ;

Φ(𝔛^{HGH}) = subs({x = y, y = x, X = Y, Y = X}, Φ(𝔛^{GHH})) ;
Φ(𝔛^{HHG}) = subs({x = z, z = x, X = Z, Z = X}, Φ(𝔛^{GHH})) ;
Φ(𝔛^{HHH}) = u^{2}XY Z;

où le symbole “subs,” tiré de MAPLE, parle de lui-même : il s’agit de faire les substitutions indiquées dans l’expression qui suit.

On a alors tous les ingrédients pour calculer la fonction génératrice suivante :

(8.1) 1 + ∑_{n≥1}u^{n} (a_{1} ψ_{1}(G_{n}) + b_{1} ψ_{1}(H_{n}))(a_{2} ψ_{2}(G_{n}) + b_{2} ψ_{2}(H_{n}))

× (a_{3} ψ_{2}(G_{n}) + b_{3} ψ_{2}(H_{n}))

= 1 + (a_{1}a_{2}a_{3}Φ(𝔛^{GGG}) + a_{1}a_{2}b_{3}Φ(𝔛^{GGH}) + a_{1}b_{1}a_{3}Φ(𝔛^{GHG})

+ b_{1}a_{2}a_{3}Φ(𝔛^{HGG}) + a_{1}b_{2}b_{3}Φ(𝔛^{GHH}) + b_{1}a_{2}b_{3}Φ(𝔛^{HGH})

+ b_{1}b_{2}a_{3}Φ(𝔛^{HHG}) + b_{1}b_{2}b_{3}Φ(𝔛^{HHH}))Φ(𝔉^{(3)}).

Il y a peu d’intérêt à donner la forme explicite de cette formule : cela prendrait une page entière ! Nous nous contenterons de donner les cas particuliers importants dans l’appendice de cet article.

9. La seconde méthode. — On suppose que les lettres x et X (resp. y et Y) sont non-commutatives. On peut alors munir tout 2-ruban d’un poids non-commutatif, de façon évidente. Par exemple,

est de poids ( \begin{matrix}xXXxXx \\ yY yyY yy \end{matrix} ) .

Il est alors immédiat que tout 2-ruban \binom{f_{1}}{f_{2}} peut être identifié à son poids (non-commutatif), qui est un bimot en les lettres x et X pour le mot du haut et en les lettres y et Y pour le mot du bas. L’image commutative du produit de juxtaposition f_{1}f_{2} est appelée évaluation du 2-ruban et notée ν(f_{1}f_{2}). Par exemple, l’évaluation du 2-ruban ci-dessus vaut x^{3}X^{3}y^{5}Y^{2}.

On appelle 2-ruban gauche tout couple de rubans \binom{f_{1}}{f_{2}} de longueur quelconque (non nécessairement identiques), mais justifiés à droite. Voici quatre types de 2-rubans gauches :

=  ,  =  ,  =  ,  =  .

En particulier, le premier type correspond aux 2-rubans ordinaires. Les relations suivantes sont des identités entre fonctions génératrices. La première, par exemple, exprime le fait que la série formée de tous les 2-rubans, justifiés à gauche, c’est-à-dire, des 2-rubans ordinaires, est la somme du 2-ruban vide et de tous les 2-rubans du second type auxquels on adjoint un monomino en haut à gauche et de tous les 2-rubans du troisième type auxquels on adjoint un domino en haut à gauche :

= 1 + x  + X
= y  + Y
= y  + Y
= x  + X

Ce système se récrit sous forme matricielle :

( \begin{matrix}1 & −x & −X & 0 \\ −y & 1 & 0 & −Y \\ −Y & −y & 1 & 0 \\ −x & −X & 0 & 1 \end{matrix} ) (  ) = ( \begin{matrix}1 \\ 0 \\ 0 \\ 0 \end{matrix} ) .

La résolution de ce système linéaire donne la fonction génératrice des différents types de 2-rubans :

= \frac{1 − XY}{1 − 2 XY − yx − y^{2}X + X^{2}Y^{2} − x^{2}Y − xyXY} ;

= \frac{y + xY}{1 − 2 XY − yx − y^{2}X + X^{2}Y^{2} − x^{2}Y − xyXY} ;

= \frac{y^{2} + Y − XY^{2} + xyY}{1 − 2 XY − yx − y^{2}X + X^{2}Y^{2} − x^{2}Y − xyXY} ;

= \frac{x + yX}{1 − 2 XY − yx − y^{2}X + X^{2}Y^{2} − x^{2}Y − xyXY} .

Pour retrouver l’expression de la fonction génératrice obtenue en (6.4), il suffit d’abord de former la combinaison linéaire

1 + acxy + adxY + bcXy + bdXY ,

qui est une fraction rationnelle et d’y faire ensuite les substitutions x ← ux, X ← u^{2}X.

On notera qu’avec les mêmes substitutions, la fraction rationnelle “ ” du système donne encore l’expression de Φ(𝔉^{(2)}) obtenue en (6.1).

10. Les rubans d’ordre supérieur. — Parmi les 3-rubans gauches (toujours justifiés à droite, mais les rubans qui les composent ne sont pas forcément de même longueur), distinguons ceux dont les rubans ont des longueurs qui diffèrent d’au plus deux unités. On peut donc les transformer en 3-rubans ordinaires, en plaçant sur chaque ligne, soit rien, soit un monomino, soit un domino. Un dénombrement facile montre que ces 3rubans gauches sont de 3^{3} − 2^{3} = 19 types, qu’on peut coder par des mots de trois lettres en l’alphabet {0, 1, 2} :

(codé 000),  (codé 100), (codé 110), …,  (codé 022).

On cherche des relations linéaires entre ces dix-neuf types. Après tâtonnements, on découvre qu’en formant le vecteur d’ordre 12

\begin{aligned}𝔙 & = (V_{1}, V_{2}, V_{3}, V_{4}, V_{5}, V_{6}, V_{7}, V_{8}, V_{9}, V_{10}, V_{11}, V_{12}) \\ & = (000, 100, 200, 110, 120, 210, 220, 001, 010, 011, 101, 201), \end{aligned}

on est conduit au système d’équations linéaires

( \begin{matrix}1 & −x & −X & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & −y & −Y & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & −y & −Y & 0 & 0 & 0 & 0 & 0 \\ −z & 0 & 0 & 1 & 0 & 0 & 0 & −Z & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & −z & −Z & 0 & 0 \\ 0 & −z & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & −Z & 0 \\ −Z & 0 & 0 & −z & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & −x & −X \\ 0 & 0 & 0 & −x & 0 & −X & 0 & 0 & 1 & 0 & 0 & 0 \\ −x & −X & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ −y & 0 & 0 & 0 & 0 & 0 & 0 & 0 & −Y & 0 & 1 & 0 \\ 0 & −y & 0 & −Y & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ) 𝔙 = ( \begin{matrix}1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix} )

qui a une solution unique. Le logiciel MAPLE nous fournit une solution explicite pour chaque V_{i}, qui est une fraction rationnelle N_{i}/D (i = 1, 2, …, 12), où, après les substitutions x ← ux, X ← u^{2}X, la fraction N_{1}/D est la fraction obtenue dans la formule (7.1). Nous ne reproduisons donc pas tous ces numérateurs N_{i}, mais indiquons comment, avec cette méthode, on retrouve la fonction génératrice (8.1).

Théorème 10.1. — La combinaison linéaire

1 + a_{1}a_{2}a_{3}xyzV_{1} + a_{1}a_{2}b_{3}xyZV_{8} + a_{1}b_{2}a_{3}xY zV_{9} + a_{1}b_{2}b_{3}xY ZV_{10} + b_{1}a_{2}a_{3}XyzV_{2} + b_{1}a_{2}b_{3}XyZV_{11} + b_{1}b_{2}a_{3}XY zV_{4} + b_{1}b_{2}b_{3}XY ZV_{1},

après y avoir fait les substitutions x ← ux, X ← u^{2}X, est égale à la fonction génératrice (8.1).

11. Appendice. — Nous donnons la liste des dix identités que l’on peut déduire de (8.1) (ou du précédent théorème) en spécialisant les différents paramètres. Rappelons que U_{n}(x) (resp. T_{n}(x)) désigne le polynôme de Tchebicheff de seconde (resp. première) espèce).

Pour x = 1, X = 1, a_{1} = 1, b_{1} = 1, y = 1, Y = 1, a_{2} = 1, b_{2} = 1, z = 1, Z = 1, a_{3} = 1, b_{3} = 1 on trouve la fonction génératrice des cubes des nombres de Fibonacci :

(11.1)  ∑_{n≥1} u^{n} F_{n}^{3} = \frac{1 − 2u − u^{2}}{(1 + u − u^{2})(1 − 4u − u^{2})}.

Pour x ← 2x, X = −1, a_{1} = 1, b_{1} = 1, y = 1, Y = 1, a_{2} = 1, b_{2} = 1, z = 1, Z = 1, a_{3} = 1, b_{3} = 1, on trouve :

(11.2)  ∑_{n≥0} u^{n} F_{n}^{2} U_{n}(x) = \frac{N_{F F U}}{D_{F F U}} ,

avec

N_{F F U} = u^{4} − 2 u^{3}x + 4 u^{2} − 2 xu + 1,
D_{F F U} = (1 + u^{2} + 2 xu) (u^{4} − 6 u^{3}x + 4 x^{2}u^{2} + 7 u^{2} − 6 xu + 1) .

Pour x ← 2x, X = −1, a_{1} = \frac{1}{2}, b_{1} = 1, y = 1, Y = 1, a_{2} = 1, b_{2} = 1, z = 1, Z = 1, a_{3} = 1, b_{3} = 1, on trouve :

(11.3)  ∑_{n≥0} u^{n} F_{n}^{2} T_{n}(x) = \frac{N_{F F T}}{D_{F F T}} ,

avec

N_{F F T} = −2 u^{4}x^{2} + u^{4} − u^{3}x + 4 x^{3}u^{3} − 4 x^{2}u^{2} + 4 u^{2} − 3 xu + 1,
D_{F F T} = D_{F F U} .

Pour x ← 2x, X = −1, a_{1} = 1, b_{1} = 1, y ← 2y, Y = −1, a_{2} = 1, b_{2} = 1, z = 1, Z = 1, a_{3} = 1, b_{3} = 1, on trouve

(11.4)  ∑_{n≥0} u^{n} F_{n} U_{n}(x) U_{n}(y) = \frac{N_{F UU}}{D_{F UU}} ,

avec

N_{F UU} = 1 − 4 u^{4}x^{2} + 4 x^{2}u^{2} − 4 u^{2} + 4 u^{4} + 4 y^{2}u^{2} − u^{6} − 4 u^{4}y^{2} − 8 u^{3}yx,
D_{F UU} = 1 − 16 u^{5}y^{3}x + u^{8} − 16 u^{4}x^{2} + 12 u^{6}x^{2} + 12 x^{2}u^{2} + 16 x^{4}u^{4} − 6 u^{2} − 4 yxu
+ 11 u^{4} + 12 y^{2}u^{2} − 6 u^{6} + 12 u^{6}y^{2} − 16 u^{4}y^{2} + 16 u^{4}y^{4} − 16 u^{4}y^{2}x^{2}
− 24 u^{3}yx + 16 u^{3}y^{3}x + 4 u^{7}yx − 16 u^{6}y^{2}x^{2} + 24 u^{5}xy − 16 x^{2}u^{2}y^{2}
+ 16 x^{3}u^{3}y − 16 x^{3}u^{5}y.

Pour x ← 2x, X = −1, a_{1} = 1, b_{1} = 1, y ← 2y, Y = −1, a_{2} = \frac{1}{2}, b_{2} = 1, z = 1, Z = 1, a_{3} = 1, b_{3} = 1, on trouve :

(11.5)  ∑_{n≥0} u^{n} F_{n} U_{n}(x) T_{n}(y) = \frac{N_{F UT}}{D_{F UT}} ,

avec

N_{F UT} = 1 − 4 u^{4}x^{2} + 4 x^{2}u^{2} − 4 u^{2} − 2 yxu + 4 u^{4} + 8 y^{2}u^{2} − u^{6} + 2 u^{6}y^{2}
− 8 u^{4}y^{2} + 8 u^{4}y^{4} − 8 u^{3}yx + 8 u^{3}y^{3}x + 2 u^{5}xy − 8 x^{2}u^{2}y^{2},
D_{F UT} = D_{F UU} .

Pour x ← 2x, X = −1, a_{1} = \frac{1}{2}, b_{1} = 1, y ← 2y, Y = −1, a_{2} = \frac{1}{2}, b_{2} = 1, z = 1, Z = 1, a_{3} = 1, b_{3} = 1, on trouve :

(11.6)  ∑_{n≥0} u^{n} F_{n} T_{n}(x) T_{n}(y) = \frac{N_{F T T}}{D_{F T T}} ,

avec

N_{F T T} = 1 − 4 u^{5}y^{3}x − 8 u^{4}x^{2} + 2 u^{6}x^{2} + 8 x^{2}u^{2} + 8 x^{4}u^{4} − 4 u^{2} − 3 yxu + 4 u^{4}

+ 8 y^{2}u^{2} − u^{6} + 2 u^{6}y^{2} − 8 u^{4}y^{2} + 8 u^{4}y^{4} − 4 u^{4}y^{2}x^{2} − 11 u^{3}yx + 8 u^{3}y^{3}x − 4 u^{6}y^{2}x^{2} + 5 u^{5}xy − 12 x^{2}u^{2}y^{2} + 8 x^{3}u^{3}y − 4 x^{3}u^{5}y,

D_{F T T} = D_{F UU} .

Pour x ← 2x, X = −1, a_{1} = 1, b_{1} = 1, y ← 2y, Y = −1, a_{2} = 1, b_{2} = 1, z ← 2z, Z = −1, a_{3} = 1, b_{3} = 1 on trouve :

(11.7)  ∑_{n≥0} u^{n} U_{n}(x) U_{n}(y) U_{n}(z) = \frac{N_{UUU}}{D_{UUU}} ,

avec

N_{UUU} = 1 − 4 u^{4}z^{2} − 4 u^{2}z^{2} + 16 u^{3}yzx − 4 u^{4}x^{2} − 4 x^{2}u^{2} + 3 u^{2} + 3 u^{4} − 4 y^{2}u^{2}

+ u^{6} − 4 u^{4}y^{2}

D_{UUU} = 1 + 16 u^{6}z^{2}x^{2} + u^{8} − 8 u^{6}z^{2} − 16 u^{4}z^{2} − 8 u^{2}z^{2} − 32 x^{3}u^{5}yz + 40 xu^{5}yz

− 32 u^{5}z^{3}xy − 32 x^{3}u^{3}yz − 8 u^{7}yxz + 16 u^{4}z^{4} − 32 u^{3}y^{3}zx − 32 u^{5}y^{3}zx + 64 u^{4}y^{2}z^{2}x^{2} + 40 u^{3}yzx + 16 u^{2}y^{2}z^{2} + 16 u^{6}y^{2}z^{2} − 16 u^{4}x^{2} − 8 u^{6}x^{2} − 8 x^{2}u^{2} + 16 x^{4}u^{4} + 4 u^{2} + 16 x^{2}u^{2}z^{2} − 32 xu^{3}yz^{3} + 6 u^{4} − 8 y^{2}u^{2} + 4 u^{6} − 8 yzxu − 8 u^{6}y^{2} − 16 u^{4}y^{2} + 16 u^{4}y^{4} + 16 u^{6}y^{2}x^{2} + 16 x^{2}u^{2}y^{2}.

Pour x ← 2x, X = −1, a_{1} = 1, b_{1} = 1, y ← 2y, Y = −1, a_{2} = 1, b_{2} = 1, z ← 2z, Z = −1, a_{3} = \frac{1}{2}, b_{3} = 1 on trouve :

(11.8)  ∑_{n≥0} u^{n} U_{n}(x) U_{n}(y) T_{n}(z) = \frac{N_{UUT}}{D_{UUT}} ,

avec

N_{UUT} = 1 − 2 u^{6}z^{2} − 8 u^{4}z^{2} − 6 u^{2}z^{2} + 4 xu^{5}yz + 8 u^{4}z^{4} + 16 u^{3}yzx + 8 u^{2}y^{2}z^{2}

− 4 u^{4}x^{2} − 4 x^{2}u^{2} + 3 u^{2} + 8 x^{2}u^{2}z^{2} − 16 xu^{3}yz^{3} + 3 u^{4} − 4 y^{2}u^{2} + u^{6} − 4 yzxu − 4 u^{4}y^{2}

D_{UUT} = D_{UUU} .

Pour x ← 2x, X = −1, a_{1} = 1, b_{1} = 1, y ← 2y, Y = −1, a_{2} = \frac{1}{2}, b_{2} = 1, z ← 2z, Z = −1, a_{3} = \frac{1}{2}, b_{3} = 1 on trouve :

(11.9)  ∑_{n≥0} u^{n} U_{n}(x) T_{n}(y) T_{n}(z) = \frac{N_{UT T}}{D_{UT T}} ,

avec

N_{UT T} = 1 − 2 u^{6}z^{2} − 8 u^{4}z^{2} − 6 u^{2}z^{2} + 10 xu^{5}yz − 8 u^{5}z^{3}xy − 8 x^{3}u^{3}yz + 8 u^{4}z^{4}

− 16 u^{3}y^{3}zx − 8 u^{5}y^{3}zx + 16 u^{4}y^{2}z^{2}x^{2} + 20 u^{3}yzx + 12 u^{2}y^{2}z^{2} + 4 u^{6}y^{2}z^{2} − 4 u^{4}x^{2} − 4 x^{2}u^{2} + 3 u^{2} + 8 x^{2}u^{2}z^{2} − 16 xu^{3}yz^{3} + 3 u^{4} − 6 y^{2}u^{2} + u^{6} − 6 yzxu − 2 u^{6}y^{2} − 8 u^{4}y^{2} + 8 u^{4}y^{4} + 8 x^{2}u^{2}y^{2}

D_{UT T} = D_{UUU} .

Pour x ← 2x, X = −1, a_{1} = \frac{1}{2}, b_{1} = 1, y ← 2y, Y = −1, a_{2} = \frac{1}{2}, b_{2} = 1, z ← 2z, Z = −1, a_{3} = \frac{1}{2}, b_{3} = 1 on trouve :

(11.10)  ∑_{n≥0} u^{n} T_{n}(x) T_{n}(y) T_{n}(z) = \frac{N_{T T T}}{D_{T T T}} ,

avec

N_{T T T} = 1 + 4 u^{6}z^{2}x^{2} − 2 u^{6}z^{2} − 8 u^{4}z^{2} − 6 u^{2}z^{2} − 12 x^{3}u^{5}yz + 15 xu^{5}yz − 12 u^{5}z^{3}xy

− 20 x^{3}u^{3}yz − u^{7}yxz + 8 u^{4}z^{4} − 20 u^{3}y^{3}zx − 12 u^{5}y^{3}zx + 32 u^{4}y^{2}z^{2}x^{2} + 25 u^{3}yzx + 12 u^{2}y^{2}z^{2} + 4 u^{6}y^{2}z^{2} − 8 u^{4}x^{2} − 2 u^{6}x^{2} − 6 x^{2}u^{2} + 8 x^{4}u^{4} + 3 u^{2} + 12 x^{2}u^{2}z^{2} − 20 xu^{3}yz^{3} + 3 u^{4} − 6 y^{2}u^{2} + u^{6} − 7 yzxu − 2 u^{6}y^{2} − 8 u^{4}y^{2} + 8 u^{4}y^{4} + 4 u^{6}y^{2}x^{2} + 12 x^{2}u^{2}y^{2}

D_{T T T} = D_{UUU} .

Les formules (11.1), (11.7) et (11.10) ont été données par Supper [Su92]. Il est clair que sa méthode permet aussi d’obtenir toutes les autres.

BIBLIOGRAPHIE

[Av88] Avanissian (Vazgain). — Fonctionnelles analytiques liées aux polynômes ortho-

gonaux classiques, C.R. Acad. Sci. Paris, t. 307, 1988, p. 177–180.

[AvGa75] Avanissian (Vazgain) et Gay (Roger). — Sur une transformation des fonctionnelles analytiques et ses applications aux fonctions entières de plusieurs variables, Bull. Soc. Math. France, t. 103, 1975, p. 341–384.

[AvSu91] Avanissian (Vazgain) et Supper (Raphaële). — Fonctionnelles analytiques et sommes de séries de puissances à coefficients produits de polynômes orthogonaux, C.R. Acad. Sci. Paris, t. 312, 1991, p. 73–76.

[Ca66] Carlitz (Leonard). — Some orthogonal polynomials related to Fibonacci numbers, Fibonacci Quart., t. 4, 1966, p. 43–48.

[Ca75] Carlitz (Leonard). — Fibonacci notes 4. q-Fibonacci polynomials, Fibonacci Quart., t. 13, 1975, p. 97–102.

[Ca78] Carlitz (Leonard). — Some polynomials related to Fibonacci and Eulerian

numbers, Fibonacci Quart., t. 16, 1978, p. 216–226.

[CeMi87] Cerlienco (Luigi), Mignotte (Maurice) et Piras (Francesco). — Suites récurrentes linéaires : Propriétés algébriques et arithmétiques, L’Enseignement Mathématique, t. 33, 1987, p. 67–108.

[Kn68] Knuth (Donald E.). — The Art of Computer Programming, vol. 1 / Fundamental Algorithms. — Reading, Mass., Addison-Wesley, 1968.

[Ra60] Rainville (Earl D.). — Special Functions. — Bronx, N.Y., Chelsea, 1960.

[Sh81] Shapiro (L.W.). — A combinatorial proof of a Chebyshev polynomial identity, Discrete Math., t. 34, 1981, p. 203–206.

[Su92] Supper (Raphaële). — Fonctionnelles analytiques liées aux fonctions spéciales et fonctions arithmétiques au sens d’Abel. Thèse, Université Louis Pasteur, Strasbourg, 1992.

Dominique Foata, Département de mathématique, Université Louis-Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France. email : foata@math.u-strasbg.fr Guo-Niu Han, I.R.M.A. et département de mathématique, Université de Strasbourg, 7, rue René-Descartes, F-67084 Strasbourg, France email : guoniu@math.u-strasbg.fr