Séries génératrices#
Nous allons introduire un concept fondamental de la combinatoire qui permet de faire le lien entre énumération combinatoire et calcul formel.
La combinatoire s’intéresse aux suites de nombres qui comptent des ensembles d’objets combinatoires en les groupant par taille. Par exemple, les sous-ensembles d’un ensemble à \(n\) éléments :
Dans ce cas là, on trouve facilement une formule explicite \(2^n\). Mais ce n’est pas toujours le cas. Dans l’exemple des arbres binaires, on a vu des techniques récursives permettant de calculer explicitement le nombre d’arbres de taille \(n\) sans connaître la formule explicite, en se basant sur la description récursive des objets eux-mêmes. C’est ce principe que l’on va généraliser avec les séries génératrices. Voici le début de la suite des nombres de Catalan comptant les arbres binaires
On va transformer cette suite de nombre en un objet algébrique à l’aide d’une variable formelle \(z\) :
Autrement dit :
où \(C_n\) est le nombre d’arbres binaires de taille \(n\). C’est une série formelle : les opérations usuelles (addition, multiplication) fonctionnent comme on en a l’habitude mais \(z\) est une variable formelle, on ne va pas lui affecter une valeur et on ne cherche donc pas à savoir si la série est convergente.
A quoi ça sert ? Dans l’exercice suivant, on va utiliser cette description en série pour démontrer la formule des nombres de Catalan.
Exercice : démonstration de la formule des nombres de Catalan#
Soit \(f(z) = 1 + z + 2z^2\). Calculez \(1 + z f(z)^2\). Que remarquez vous ?
En vous rappelant que \(C_n = \sum_{k=0}^{n-1} C_k C_{n-k-1}\), démontrez que \(C(z) = 1 + z C(z)^2\)
En utilisant les outils classiques de résolution d’équation du second degré par calcul de discriminant, donnez les deux solutions possibles (en fonction de \(z\)) pour \(C\) vérifiant \(C = 1 + z C^2\).
Effectuez (avec Sage) un développement de Taylor en 0 à l’ordre 4 des deux fonctions de \(z\) trouvées à la question précédente. A quelle solution correspond notre série \(C(z)\) ?
On cherche le développement en série de cette fonction de \(z\). En particulier, cela demande de développer \(\sqrt{1-4z}\). Pour cela, on va utiliser la formule du binôme généralisée. La formule du binôme de Newton s’écrit de la façon suivante
où \({n \choose k} = \frac{n!}{k!(n-k)!} = \frac{n (n-1) \dots (n-k+1)}{k!}\). Pour un nombre réel \(r\) quelconque, on définit
Le binôme de Newton généralisé exprime par une série le développement de \((a+b)^r\) où \(r\) est un réel :
En utilisant ce principe, calculez les coefficients jusqu’au degré 3 de \(S(y) = (1+y)^{1/2}\). Vérifiez jusqu’au degré 3 que \(S(y)^2 = 1+y\).
Montrez que les coefficients de \(C(z)\) peuvent s’exprimer par
Trouvez une formule « plus jolie »
Les séries génératrices et Sage#
L’équation fonctionelle \(C(z) = 1 + z C(z)^2\) décrivant la série génératrice des arbres binaires est une traduction directe de la description récursive des arbres.
Un arbre binaire est « une feuille (taille 0), soit un noeud (taille 1) avec deux arbres binaires ».
Soit \(E\) l’ensemble des arbres binaires, \(\epsilon\) l’ensemble contenant l’arbre vide (feuille) comme unique élément, et \(Z\) l’ensemble contenant comme unique élément un noeud. On a l’égalité ensembliste suivante :
Rappelez-vous d’ailleurs que pour l’énumération des arbres binaires, nous avons bien utilisé les règles du produit cartésien. Cette équation se traduit directement en série génératice : l’union devient la somme et le produit cartésien, le produit. L’arbre vide ayant pour taille 0 est envoyé sur \(z^0 = 1\) et le noeud ayant une taille 1 est envoyé sur \(z^1 = z\).
Une fois traduit une description combinatoire en équation fonctionnelle sur la série génératrice, on peut donner l’équation à Sage et ainsi calculer les coefficients.
On commence par créer l’anneau des séries génératrices.
L.<z> = LazyPowerSeriesRing(QQ)
L
On définit notre série \(C(z)\) comme un élément de cet anneau
C = L()
C
On définit l’équation que doit vérifier \(C(z)\)
C.define(1 + z*C*C)
Sage peut maintenant calculer les coefficients
C.compute_coefficients(10); C
C.coefficient(100)
C.coefficient(200)
Quelques exercices#
Mots de Fibonacci#
Les mots de fibonacci sont des mots sur l’alphabet \(\{a, b\}\) ne contenant jamais 2 lettres \(b\) consécutives. Par exemple \(aaababaab\) est un mot de Fibonacci.
On peut décrire les mots de Fibonacci récursivement par : le mot vide, ou la lettre \(b\), ou la lettre \(a\) suivie d’un mot de Fibonacci, ou les lettres \(ba\) suivies d’un mot de Fibonacci.
Définir la série génératice correspondante \(F(z)\) et calculez avec Sage les premiers coefficients.
// Ecrire votre code ici
[F.coefficient(i) for i in range(11)]
oeis([F.coefficient(i) for i in range(1,11)])
Arbres unaire-binaires#
Les arbres unaires-binaires sont des arbres dont chaque noeud possède exactement 0, un fils (central) ou deux fils (gauche et droit). Définir la série génératrice correspondante \(BU(z)\) et calculez avec Sage les premiers coefficients.
// Ecrire votre code ici
[BU.coefficient(i) for i in range(1,11)]
oeis([BU.coefficient(i) for i in range(1,11)])
Quelques opérations#
Séries mutuellement récursives#
On crée la série \(M\) des mots sur \(\{a,b \}\) ne contenant ni 2 \(a\) consécutifs, ni 3 \(b\) consécutifs. On va définir \(M\) comme étant la somme de deux séries \(M_a\) et \(M_b\) où \(M_a\) représente les mots de l’ensemble commençant par \(a\) et \(M_b\) les mots de l’ensemble commençant par \(b\).
Ma = L()
Mb = L()
Si un mot commence par \(a\), il est suivi d’un mot qui commence par \(b\) ou par le mot vide.
Ma.define(z*(Mb + 1))
Si un mot commence par \(b\), il peut-être suivi d’un \(b\) (lui-même suivi d’un mot qui commence par \(a\) ou par le mot vide), ou il est suivi d’un mot qui commence par \(a\) ou par le mot vide.
Mb.define(z*(Ma + 1) + z^2*(Ma + 1))
M = 1 + Ma + Mb;
M.compute_coefficients(10);
M
La composition#
# Arbres binaires bi-colorés
C2 = C.compose(2*z)
[C2.coefficient(i) for i in range(11)]
[C.coefficient(i) for i in range(11)]
# Arbres binaires de mots de Fibonacci
# Attention ! Pas de composition possible si élément vide
C3 = C.compose(F - 1)
[C3.coefficient(i) for i in range(11)]
L’inversion#
Sage est capable de trouver la série inverse d’une série donnée \(F\). C’est à dire, la série \(G\) telle que \(FG = 1\). Voyons déjà l’inversion de quelques séries finies.
b = ~(1-z)
b.compute_coefficients(10); b
b = ~(1 - z - z^2)
b.compute_coefficients(10); b
On retrouve les nombre de Fibonacci.
On peut calculer l’inverse de la série des nombres de Catalan
C = L()
C.define(1 + z*C*C)
b = ~C
b.compute_coefficients(10); b
Pouvez-vous expliquer le résultat obtenu à partir de l’équation fonctionnelle ? Rappel des coefficients de C:
C.compute_coefficients(10); C
Un algorithme d’inversion de série#
On présente sur un exemple un algorithme d’inversion de série.
Soit \(F(z) = 1 - z - z^2\)
F = 1 - z - z^2
F.compute_coefficients(5)
F
On définit la suite suivante
\(G_0 = 1\)
\(G_{i+1} = 2G_i - F G_i^2\)
Calculez avec Sage les premiers coefficients des premiers termes, que constatez-vous ?
// Ecrire votre code ici
// Ecrire votre code ici
// Ecrire votre code ici
// Ecrire votre code ici
// Ecrire votre code ici
Montrez que pour tout \(F\) tel que \(F(0) = 1\), \(G_{i+1} - G_i\) est un multiple de \(z^{2^i}\). Que peut-on en conclure ?
Quelques références pour aller plus loin#
Enumération combinatoire dans Sage: Chapitre Combinatoire de Calcul Mathématiques avec Sage
Le livre de référence pour les séries génératrices et la combinatoire (correspondance série / combinatoire, dénombrement, calcul asymptotique, génération aléatoire, etc.) : Analytic Combinatorics Philippe Flajolet, Robert Sedgewick