Combinatoire analytique

Une classe combinatoire est par définition un ensemble ${\displaystyle {\mathcal {A}}}$ muni d'une application ${\displaystyle |\cdot |:{\mathcal {A}}\to \mathbb {N} }$ appelée taille qui, à chaque élément ${\displaystyle a}$ de l'ensemble ${\displaystyle {\mathcal {A}}}$ associe un entier naturel ${\displaystyle |a|}$. On demande de plus que, pour chaque ${\displaystyle n}$, le nombre d'éléments de taille ${\displaystyle n}$ est fini.

Comme la définition le suggère, un même ensemble peut être doté de plusieurs tailles différentes. Ainsi, la taille des arbres binaires peut être leur nombre de sommet; une autre taille est leur hauteur. Mais le nombre de feuilles n'est pas une taille valide, parce qu'il existe une infinité d'arbres binaires « filiformes » (où chaque nœud n'a qu'il seul enfant) qui n'ont qu'une feuille unique. En général, un objet d'une certaine taille est formé de composants élémentaires que l’on appelle parfois des atomes (comme les sommets d'un graphe par exemple).

Soit maintenant ${\displaystyle {\mathcal {A}}}$ un ensemble combinatoire, et soit ${\displaystyle a_{n}}$ le nombre d'éléments de taille ${\displaystyle n}$ de ${\displaystyle {\mathcal {A}}}$. La série génératrice ordinaire associée à ${\displaystyle {\mathcal {A}}}$ est par définition la série ${\displaystyle A(z)}$ définie par

${\displaystyle A(z)=\sum _{n=0}^{\infty }a_{n}z^{n}}$.

Il est parfois commode de considérer une autre expression équivalente pour la série, à savoir :

${\displaystyle A(z)=\sum _{a\in {\mathcal {A}}}z^{|a|}}$.

On considère aussi, dans le cas de structures étiquetées, des séries génératrices exponentielles dont il sera question plus bas.

En général, les séries génératrices associées au dénombrement d'objets combinatoires sont des séries formelles, que l'on peut manipuler sans considération de convergence (au sens de convergence dans les réels ou dans les complexes), mais il existe en fait une notion de convergence dans l'anneau des séries formels qui repose sur la valuation des séries et qui donne un cadre rigoureux à toutes les manipulations mentionnées ci-après. Dans le cadre de la combinatoire analytique, les questions de convergence jouent d'ailleurs un rôle, puisqu'on étudie le comportement des séries en des points précis, dans le cadre de l’analyse complexe. L'observation fondamentale utilisée - qui est explicitée plus loin - est que la nature de la singularité sur l'axe réel positif donne des informations précises sur la croissance des nombres ${\displaystyle a_{n}}$ d'objets de taille ${\displaystyle n}$.

Une notation utile pour l'extraction de coefficients d'une série génératrice ${\displaystyle f(z)}$ est la suivante : on désigne par ${\displaystyle [z^{n}]}$ le coefficient de la variable ${\displaystyle z^{n}}$, de sorte que, pour

${\displaystyle f(z)=\sum _{n=0}^{\infty }f_{n}z^{n}}$,

on a :

${\displaystyle [z^{n}]f(z)=f_{n}}$.

Dans la suite de cet article, on parlera parfois avec un léger abus de langage des coefficients d'une fonction, pour désigner les coefficients du développement de Taylor en 0 de cette fonction.

Quelques exemples usuels sont les suivants.

• Classe des mots sur un alphabet binaire, la taille est la longueur du mot. Il y a ${\displaystyle 2^{n}}$ mots de longueur ${\displaystyle n}$. La série génératrice est ${\displaystyle {\frac {1}{1-2z}}}$.
• Compositions d'entiers (une composition d'un entier positif ${\displaystyle n}$ est une suite ${\displaystyle (p_{1},p_{2},\ldots ,p_{r})}$ d'entiers positifs tels que ${\displaystyle p_{1}+p_{2}+\cdots +p_{r}=n}$). Chaque entier positif ${\displaystyle n}$ possède ${\displaystyle 2^{n-1}}$ compositions. La série génératrice est ${\displaystyle {\frac {z}{1-2z}}}$.
• Arbres binaires complets. Le nombre d'arbres binaires complets à ${\displaystyle n}$ nœuds internes est ${\displaystyle {\frac {1}{n+1}}{\binom {2n}{n}}}$, et la série génératrice est ${\displaystyle {\frac {1-{\sqrt {1-4z}}}{2z}}}$.

Les briques de base sont des classes formées d'un seul objet. Deux types de classes sont utiles : celles où le singleton est de taille nulle, et celles dont le singleton est de taille un. Une classe ${\displaystyle {\mathcal {E}}=\{\varepsilon \}}$ du premier type a donc un élément ${\displaystyle \varepsilon }$ de taille nulle, et sa série génératrice est la fonction constante ${\displaystyle E(z)=1}$. Une classe ${\displaystyle {\mathcal {Z}}=\{z\}}$ du deuxième type a un seul élément, de taille un, et sa série génératrice est ainsi ${\displaystyle Z(z)=z}$. Les opérations élémentaires sont l'union disjointe, le produit cartésien, la formation de suites.

On écrit ${\displaystyle {\mathcal {A}}={\mathcal {B}}+{\mathcal {C}}}$ si la classe ${\displaystyle {\mathcal {A}}}$ est l’union disjointe des classes ${\displaystyle {\mathcal {B}}}$ et ${\displaystyle {\mathcal {C}}}$. Cette relation se traduit en séries génératrices par

${\displaystyle A(z)=B(z)+C(z)}$

puisqu'en effet

${\displaystyle A(z)=\sum _{a\in {\mathcal {A}}}z^{|a|}=\sum _{a\in {\mathcal {B}}}z^{|a|}+\sum _{a\in {\mathcal {C}}}z^{|a|}=B(z)+C(z)}$.

On écrit ${\displaystyle {\mathcal {A}}={\mathcal {B}}\times {\mathcal {C}}}$ si la classe ${\displaystyle {\mathcal {A}}}$ est l'ensemble des couples ${\displaystyle a=(b,c)}$, avec ${\displaystyle b\in {\mathcal {B}}}$ et ${\displaystyle c\in {\mathcal {C}}}$. La fonction taille est définie par ${\displaystyle |a|=|b|+|c|}$. On a alors, pour les séries génératrices, la relation

${\displaystyle A(z)=B(z)C(z)}$.

On écrit ${\displaystyle {\mathcal {A}}={\mathsf {Seq}}({\mathcal {B}})}$ lorsque ${\displaystyle {\mathcal {A}}}$ est l'ensemble des suites finies d'éléments de ${\displaystyle {\mathcal {B}}}$. Cette construction est aussi appelée étoile de Kleene en théorie des langages. On peut l'écrire plus formellement comme

${\displaystyle {\mathcal {A}}={\mathcal {E}}+{\mathcal {B}}+{\mathcal {B}}\times {\mathcal {B}}+{\mathcal {B}}\times {\mathcal {B}}\times {\mathcal {B}}+\cdots }$, ou encore ${\displaystyle {\mathcal {A}}=\{(b_{1},\ldots ,b_{h})\mid h\geq 0,b_{j}\in {\mathcal {B}}\}}$.

La taille d'une suite ${\displaystyle (b_{1},\ldots ,b_{h})}$ est la somme des tailles de ses composants. Pour que l’opération soit bien définie, la classe ${\displaystyle {\mathcal {B}}}$ ne doit pas contenir d'élément de taille 0 car sinon la classe ${\displaystyle {\mathcal {A}}}$ contiendrait une infinité d'éléments d'une taille donnée. La traduction en séries génératrices est

${\displaystyle A(z)={\frac {1}{1-B(z)}}}$.

La série ${\displaystyle A(z)}$ est appelée parfois le quasi-inverse de la série ${\displaystyle B(z)}$.

Lorsque certaines conditions assez techniques sont remplies[2], on peut définir une classe combinatoire de façon récursive. Voici des exemples.

Le premier exemple est celui des arbres binaires. Un arbre binaire est soit l’arbre binaire vide, soit formé d'une racine et de deux sous-arbres qui sont des arbres binaires. L'équation de la classe combinatoire ${\displaystyle {\mathcal {B}}}$ des arbres binaires est donc :

${\displaystyle {\mathcal {B}}={\mathcal {E}}+{\mathcal {Z}}\times {\mathcal {B}}\times {\mathcal {B}}}$,

où ${\displaystyle {\mathcal {E}}}$ est réduite à un élément de taille 0 et ${\displaystyle {\mathcal {Z}}}$ est composé d'un élément de taille 1. Cette équation se traduit en l’équation

${\displaystyle B(z)=1+zB(z)^{2}}$.

Un arbre unaire-binaire est un arbre où chaque nœud interne a un ou deux enfants. L'équation symbolique s'écrit

${\displaystyle {\mathcal {U}}={\mathcal {Z}}+{\mathcal {Z}}\times {\mathcal {B}}+{\mathcal {Z}}\times {\mathcal {B}}\times {\mathcal {B}}}$

d'où l'on déduit l'équation fonctionnelle

${\displaystyle U(z)=z+zU(z)+zU(z)^{2}}$.

On peut employer la méthode symbolique même dans des cas très élémentaires :

Un mot binaire est une suite de symboles 0 et 1. On a deux classes combinatoires ${\displaystyle {\mathcal {Z}}_{0}=\{0\}}$ et ${\displaystyle {\mathcal {Z}}_{1}=\{1\}}$ dont la série génératrice est ${\displaystyle z}$. Les mots binaires sont donnés par la construction

${\displaystyle {\mathcal {W}}_{0}={\mathsf {Seq}}({\mathcal {Z}}_{0}+{\mathcal {Z}}_{1})}$,

leur série génératrice est

${\displaystyle W(z)={\frac {1}{1-(z+z)}}}$ et ${\displaystyle [z^{n}]W(z)=2^{n}}$.

C'est utiliser une grosse artillerie pour un exemple tout simple.

Le problème est de couvrir le segment ${\displaystyle [0,n]}$ avec des briques de taille 1 et 2, en d'autre termes d'écrire l'entier ${\displaystyle n}$ comme une somme dont les termes sont 1 ou 2, et de compter le nombre de façons de le faire. Par exemple, l'entier 4 possède les cinq écritures :

4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2 .

Il est facile de voir directement que le nombre de ces compositions de ${\displaystyle n}$ est ${\displaystyle F_{n}}$, le ${\displaystyle n}$^e nombre de Fibonacci. Pour utiliser la méthode symbolique, on considère deux classes ${\displaystyle {\mathcal {Z}}_{1}}$ et ${\displaystyle {\mathcal {Z}}_{2}}$ composées d'un élément unique de taille 1 et de taille 2 respectivement. Alors la classe de couvertures est

${\displaystyle {\mathcal {F}}={\mathsf {Seq}}({\mathcal {Z}}_{1}+{\mathcal {Z}}_{2})}$

et la série génératrice est :

${\displaystyle F(z)={\frac {1}{1-z-z^{2}}}=1+z+2z^{2}+3z^{3}+5z^{4}+\cdots }$.

D'autre constructions symboliques importantes sont : Cycles. Les cycles ${\displaystyle {\mathcal {A}}={\mathsf {Cyc}}({\mathcal {B}})}$ sont comme des séquences, sauf que deux objets qui s'obtiennent l'un de l'autre par une rotation circulaire ne sont pas considérés comme distincts. La série génératrice est nettement plus compliquée; dans le cas étiqueté, elle est plus simple. Ici, elle s'écrit

${\displaystyle A(z)=\sum _{k=1}^{\infty }{\frac {\phi (k)}{k}}\log {\frac {1}{1-B(z^{k})}}}$

où ${\displaystyle \phi (k)\,}$ est l'indicatrice d'Euler. Classe pointée. La classe ${\displaystyle \Theta {\mathcal {B}}}$ est formée d'objets de ${\displaystyle {\mathcal {B}}}$ qui sont « pointés » : dans chaque objet, un atome est distingué. Par exemple, les arbres enracinés sont des arbres libres pointés. Formellement, chaque objet est augmenté d'un élément de taille zéro sur un de ses atomes. La série génératrice est

${\displaystyle z{\frac {\partial }{\partial z}}B(z)}$.

Substitution. La classe ${\displaystyle {\mathcal {B}}\circ {\mathcal {C}}}$ est obtenue en substituant, à chaque atome d'un élément de ${\displaystyle {\mathcal {B}}}$, un élément de la classe ${\displaystyle {\mathcal {C}}}$. La série génératrice est simplement ${\displaystyle B(C(z))}$.

Pour les séries rationnelles, une décomposition en éléments simples donne une forme close pour le terme ${\displaystyle f_{n}}$, qui s'écrit donc comme une somme de termes de la forme ${\displaystyle c_{j}n^{j}R_{j}^{-n}}$. Ainsi, si la singularité dominante R est de multiplicité ${\displaystyle k}$, alors

${\displaystyle [z^{n}]f(z)\sim \left(\lim _{z\rightarrow R}f(z)(z-R)^{k}\right)\times {\frac {R^{-n}n^{k-1}}{(k-1)!}}}$.

Exemple. On considère la série rationnelle

${\displaystyle f(z)=(1-z^{2}/2)^{-5}(1-z^{3})^{-1}(1-2z)^{-5}(1-z-z^{2})^{-1}}$.

Ses singularités sont ${\displaystyle {\sqrt {2}},-{\sqrt {2}},1,1/2,\phi ,{\bar {\phi }}}$ (où ${\displaystyle \phi }$ désigne le nombre d'or). La singularité dominante est 1/2, et sa multiplicité est 5. On a donc

${\displaystyle [z^{n}]f(z)\sim {\frac {1048576}{117649}}{\frac {1}{4!}}2^{n}n^{4}}$.

Considérons maintenant la classe des fonctions algébrico-logarithmiques, c'est-à-dire les sommes et produits de ${\displaystyle (1-z)^{\alpha }}$ et de ${\displaystyle \log(1-z)}$. Pour des séries génératrices ayant une telle forme, des méthodes d'analyse complexe[3] donnent l'asymptotique suivante pour leurs coefficients, exprimée ici dans le cas où la singularité est 1 (on peut toujours s'y ramener par un changement de variable):

Soient ${\displaystyle \alpha \in \mathbb {R} \setminus \{0,-1,-2,\ldots \}}$ et ${\displaystyle k\in \mathbb {N} }$. On a

${\displaystyle [z^{n}]{\frac {1}{(1-z)^{\alpha }}}\log ^{k}\left({\frac {1}{1-z}}\right)\sim {\frac {n^{\alpha -1}}{\Gamma (\alpha )}}\log ^{k}(n)}$,

où ${\displaystyle \Gamma }$ est la fonction Gamma usuelle.

Cet équivalent asymptotique peut en fait être poussé à n'importe quel ordre, ce qui donne par exemple[4] :

Fonction	Coefficients
${\displaystyle (1-z)^{3/2}}$	${\displaystyle {\frac {1}{\sqrt {\pi n^{5}}}}{\bigl (}{\frac {3}{4}}+{\frac {45}{32n}}+{\frac {1155}{512n^{2}}}+O{\bigl (}{\frac {1}{n^{3}}}{\bigr )}{\bigr )}}$
${\displaystyle (1-z)^{1/2}}$	${\displaystyle -{\frac {1}{\sqrt {\pi n^{3}}}}{\bigl (}{\frac {1}{2}}+{\frac {3}{16n}}+{\frac {25}{256n^{2}}}+O({\frac {1}{n^{3}}}){\bigr )}}$
${\displaystyle (1-z)^{1/2}\log(1-z)}$	${\displaystyle -{\frac {1}{\sqrt {\pi n^{3}}}}{\bigl (}{\frac {1}{2}}\log n+{\frac {\gamma +2\log 2-2}{2}}+O{\bigl (}{\frac {\log n}{n}}{\bigr )}{\bigr )}}$
${\displaystyle (1-z)^{-1/2}}$	${\displaystyle {\frac {1}{\sqrt {\pi n}}}{\bigl (}1-{\frac {1}{8n}}+{\frac {1}{128n^{2}}}+{\frac {5}{1024n^{3}}}+O{\bigl (}{\frac {1}{n^{4}}}{\bigr )}{\bigr )}}$
${\displaystyle (1-z)^{-1/3}}$	${\displaystyle {\frac {1}{\Gamma (1/3)n^{2/3}}}{\bigl (}1+O{\bigl (}{\frac {1}{n}}{\bigr )}{\bigr )}}$
${\displaystyle (1-z)^{-1}\log ^{2}(1-z)}$	${\displaystyle \log ^{2}n+2\gamma \log n+\gamma ^{2}-{\frac {\pi ^{2}}{6}}+O{\bigl (}{\frac {\log n}{n}}{\bigr )}}$

Remarquons que la classe des fonctions algébrico-logarithmiques n'englobe pas toutes les fonctions algébriques, mais toute fonction algébrique possède un développement en série de Puiseux qui est une somme infinie de briques de base du type ${\displaystyle (1-z)^{\alpha }}$, et la troncation de cette somme à un ordre donné est bien une fonction algébrico-logarithmique. Le théorème de transfert détaillé dans la section suivante permet de lier le développement asympotique des coefficients de la somme infinie et de sa truncation.

Le théorème de transfert[5] énonce qu'il suffit de connaître le comportement de deux fonctions autour de leur plus petite singularité pour pouvoir comparer le comportement asymptotique de leurs coefficients. L'énoncé est le suivant.

Soient ${\displaystyle f(z)}$ et ${\displaystyle g(z}$) deux fonctions dont la plus petite singularité est 1. Alors — Si ${\displaystyle f(z)\sim _{z\to 1}g(z)}$, alors ${\displaystyle f_{n}\sim g_{n}}$.
— Si ${\displaystyle f(z)=_{z\to 1}O(g(z))}$, alors ${\displaystyle f_{n}=O(g_{n})}$.
— Si ${\displaystyle f(z)=_{z\to 1}o(g(z))}$, alors ${\displaystyle f_{n}=o(g_{n})}$.

On retrouve comme suit l'évaluation asymptotique du nombre d'arbres binaires. On part de l'équation symbolique

${\displaystyle {\mathcal {B}}={\mathcal {E}}+{\mathcal {Z}}\times {\mathcal {B}}\times {\mathcal {B}}}$,

où ${\displaystyle {\mathcal {E}}}$ est réduite à un élément de taille 0 et ${\displaystyle {\mathcal {Z}}}$ est composé d'un élément de taille 1. Cette équation se traduit en l’équation

${\displaystyle B(z)=1+zB(z)^{2}}$.

On résout l'équation et on trouve

${\displaystyle B(z)={\frac {1-{\sqrt {1-4z}}}{2z}}}$.

La fonction a une singularité algébrique en ${\displaystyle z=1/4}$, d'exposant ${\displaystyle 1/2}$. Autour de ${\displaystyle z=1/4}$, on a

${\displaystyle B(z)\sim 2(1-4z)^{1/2}}$

et, par le théorème précédent sur les singularités algébrico-logarithmiques, on obtient

${\displaystyle [z^{n}]B(z)\sim -2{\frac {4^{n}n^{-3/2}}{\Gamma (-1/2)}}={\frac {4^{n}n^{-3/2}}{\sqrt {\pi }}}}$

parce que ${\displaystyle \Gamma (-1/2)=-2{\sqrt {\pi }}}$.

Plus formellement, soit ${\displaystyle {\mathcal {A}}}$ une classe combinatoire étiquetée, et soit ${\displaystyle a_{n}}$, pour ${\displaystyle n\geq 0}$, le nombre d'objets de taille ${\displaystyle n}$ dans cette classe. La série génératrice exponentielle associée à ${\displaystyle {\mathcal {A}}}$ est

${\displaystyle A(z)=\sum _{n=0}^{\infty }a_{n}{\frac {z^{n}}{n!}}}$.

Il est équivalent d'écrire

${\displaystyle A(z)=\sum _{a\in {\mathcal {A}}}{\frac {z^{|a|}}{|a|!}}}$ .

L'extraction d'un coefficient de cette série donne

${\displaystyle [z^{n}]A(z)={\frac {a_{n}}{n!}}}$, donc ${\displaystyle a_{n}=n![z^{n}]A(z)}$.

Permutations. Soit ${\displaystyle {\mathcal {P}}}$ la classe des permutations. Sa série génératrice exponentielle est

${\displaystyle P(z)=\sum _{n\geq 0}n!{\frac {z^{n}}{n!}}={\frac {1}{1-z}}}$.

Graphes sans arête. Il existe, pour chaque entier n, un seul graphe sans arête. La série génératrice correspondante est

${\displaystyle \sum _{n\geq 0}{\frac {z^{n}}{n!}}=e^{z}}$

La même série compte les graphes complets.

Graphes cycliques. Le nombre de graphes étiquetés de n sommets formés d'un seul cycle est (n-1)!. Leur série génératrice exponentielle est donc

${\displaystyle \sum _{n\geq 0}(n-1)!{\frac {z^{n}}{n!}}=\sum _{n\geq 0}{\frac {z^{n}}{n}}=\log {\bigl (}{\frac {1}{1-z}}{\bigr )}}$.

La construction d'une somme disjointe de classes combinatoires se transpose sans modifications aux classes étiquetées. Pour le produit, il faut être plus attentif. Soient ${\displaystyle {\mathcal {B}}}$ et ${\displaystyle {\mathcal {C}}}$ deux classes combinatoires étiquetées. Le produit cartésien est formé de couples ${\displaystyle (b,c)}$ d'objets étiquetées, mais un tel couple n’est pas correctement étiqueté puisque ses éléments n'ont pas des étiquettes distinctes. On définit une structure ${\displaystyle (b',c')}$ associée, dont les éléments ont exactement les étiquettes ${\displaystyle \{1,\ldots ,|b|+|c|\}}$, et où l'ordre relatif des étiquettes de chaque élément est respecté. On définit

${\displaystyle b\star c}$

comme l'ensemble des couples ${\displaystyle (b',c')}$ ainsi ré-étiquetés. La famille ${\displaystyle b\star c}$ contient exactement ${\displaystyle {\binom {|b|+|c|}{|b|}}}$ éléments. Le produite étiqueté des classes ${\displaystyle {\mathcal {B}}}$ et ${\displaystyle {\mathcal {C}}}$ est par définition

${\displaystyle {\mathcal {A}}={\mathcal {B}}\star {\mathcal {C}}=\bigcup _{b\in {\mathcal {B}},c\in {\mathcal {C}}}b\star c}$.

Pour les séries génératrices exponentielles, on a

${\displaystyle A(z)=B(z)C(z)}$.

En effet, pour ${\displaystyle b\in {\mathcal {B}}}$ et ${\displaystyle c\in {\mathcal {C}}}$, on a

${\displaystyle \sum _{a\in b\star c}{\frac {z^{|a|}}{|a|!}}=\sum _{a\in b\star c}{\frac {z^{|b|+|c|}}{|b|+|c|!}}={\binom {|b|+|c|}{|b|}}{\frac {z^{|b|+|c|}}{|b|+|c|!}}={\frac {z^{|b|}}{|b||!}}{\frac {z^{|c|!}}{|c|!}}}$,

et donc

${\displaystyle A(z)=\sum _{a\in {\mathcal {A}}}{\frac {z^{|a|}}{|a|!}}=\sum _{b\in {\mathcal {B}}}\sum _{c\in {\mathcal {C}}}{\frac {z^{|b|}}{|b|!}}{\frac {z^{|c|!}}{|c|!}}=B(z)C(z)}$.

À partir de la somme disjointe et du produit, on construit l'opérateur de séquence comme dans le cas ordinaire : On écrit ${\displaystyle {\mathcal {A}}={\mathsf {Seq}}({\mathcal {B}})}$ lorsque ${\displaystyle {\mathcal {A}}}$ est l'ensemble des suites finies d'éléments de ${\displaystyle {\mathcal {B}}}$; ici ${\displaystyle {\mathcal {B}}}$ n'a pas d'élément de taille nulle. En d'autres termes,

${\displaystyle {\mathcal {A}}={\mathcal {E}}+{\mathcal {B}}+{\mathcal {B}}\times {\mathcal {B}}+{\mathcal {B}}\times {\mathcal {B}}\times {\mathcal {B}}+\cdots }$,

ou encore ${\displaystyle {\mathcal {A}}=\{(b_{1},\ldots ,b_{h})\mid h\geq 0,b_{j}\in {\mathcal {B}}\}}$, où les suites son ré-étiquetées. La série génératrices exponentielle est

${\displaystyle A(z)=\sum _{h\geq 0}B(z)^{h}={\frac {1}{1-B(z)}}}$.

Les définitions d'ensemble et de cycle donnée ici s'appliquent aussi bien aux structures non étiquetées. On définit la classe

${\displaystyle {\mathsf {Set}}_{h}({\mathcal {B}})}$

comme la classe des parties de la classe ${\displaystyle {\mathcal {B}}}$ contenant ${\displaystyle h}$ éléments. On peut voir cette classe comme la classe quotient de

${\displaystyle {\mathsf {Seq}}_{h}({\mathcal {B}})/{\mathfrak {R}}}$,

où ${\displaystyle {\mathsf {Seq}}_{h}({\mathcal {B}})}$ est l’ensemble des suites à ${\displaystyle h}$ éléments de ${\displaystyle {\mathcal {B}}}$, et où ${\displaystyle {\mathfrak {R}}}$ met en équivalence deux suites qui sont les mêmes à une permutation de ses éléments près. On a

${\displaystyle |{\mathsf {Seq}}_{h}({\mathcal {B}})|=h!|{\mathsf {Set}}_{h}({\mathcal {B}})|}$.

La classe des parties de la classe ${\displaystyle {\mathcal {B}}}$ est par définition

${\displaystyle {\mathcal {A}}={\mathsf {Set}}({\mathcal {B}})=\bigcup _{h\geq 0}{\mathsf {Set}}_{h}({\mathcal {B}})}$,

et la série génératrice exponentielle correspondante est

${\displaystyle A(z)=\sum _{h\geq 0}{\frac {1}{h!}}B(z)^{h}=\exp(B(z))}$.

On définit la classe

${\displaystyle {\mathsf {Cyc}}_{h}({\mathcal {B}})}$

comme la classe des cycles de ${\displaystyle h}$ éléments de la classe ${\displaystyle {\mathcal {B}}}$. On peut la voir comme le quotient de la classe des suites de longueur ${\displaystyle h}$ d'éléments de ${\displaystyle {\mathcal {B}}}$ par l'ensemble des permutations circulaires de ses éléments. On a

${\displaystyle |{\mathsf {Seq}}_{h}({\mathcal {B}})|=h|{\mathsf {Cyc}}_{h}({\mathcal {B}})|}$.

La classe des cycles de la classe ${\displaystyle {\mathcal {B}}}$ est par définition

${\displaystyle {\mathcal {A}}={\mathsf {Cyc}}({\mathcal {B}})=\bigcup _{h\geq 0}{\mathsf {Cyc}}_{h}({\mathcal {B}})}$,

et la série génératrice exponentielle correspondante est

${\displaystyle A(z)=\sum _{h\geq 0}{\frac {1}{h}}B(z)^{h}=\log(1-B(z))}$.

Deux cas particuliers sont l'opérateur de construction des cycles de longueur paire, et celui de longueur impaire, qui sont respectivement

${\displaystyle \bigcup _{h\geq 0}{\mathsf {Cyc}}_{2h}({\mathcal {B}})}$ et ${\displaystyle \bigcup _{h\geq 0}{\mathsf {Cyc}}_{2h+1}({\mathcal {B}})}$.

Leurs séries génératrices sont respectivement

${\displaystyle {\frac {1}{2}}\log {\frac {1}{1-B(z)^{2}}}}$ et ${\displaystyle {\frac {1}{2}}\log {\frac {1+B(z)}{1-B(z)}}}$.

Permutations. Une permutation peut être vue comme un ensemble de cycles de supports disjoints. Ceci conduit à l'équation symbolique

${\displaystyle {\mathcal {P}}={\mathsf {Set}}({\mathsf {Cyc}}({\mathcal {Z}}))}$,

où ${\displaystyle {\mathcal {Z}}}$ est la classe formée d'un seul élément de taille 1. La série génératrice exponentielle est

${\displaystyle P(z)=\exp {\bigl (}\log {\bigl (}{\frac {1}{1-z}}{\bigr )}{\bigr )}={\frac {1}{1-z}}}$.

Involutions. Une involution est une permutation ${\displaystyle \sigma }$ telle que ${\displaystyle \sigma ^{2}=\operatorname {Id} }$. On peut voir une involution comme un ensemble de cycles de longueur 1 ou 2 à supports disjoints. L'équation symbolique est donc

${\displaystyle {\mathcal {I}}={\mathsf {Set}}({\mathsf {Cyc_{1}}}({\mathcal {Z}})+{\mathsf {Cyc_{2}}}({\mathcal {Z}}))}$,

et a série génératrice exponentielle est ${\displaystyle I(z)=exp(z+z^{2}/2)}$. Un calcul élémentaire permet d'obtenir l'expression close

${\displaystyle [z^{n}]I(z)=\sum _{i=0}^{\lceil n/2\rceil }{\frac {n!}{i!(n-2i)!2^{i}}}}$

Dérangements. Un dérangement est une permutation sans point fixe. La définition symbolique est

${\displaystyle {\mathcal {D}}={\mathsf {Set}}({\mathsf {Cyc}}_{h\geq 2}({\mathcal {Z}}))}$,

et la fonction génératrice exponentielle est

${\displaystyle D(z)=\exp(z^{2}/2+z^{3}/3+\cdots )=\exp {\bigl (}\log {\bigl (}{\frac {1}{1-z}}{\bigr )}-z{\bigr )}={\frac {e^{-z}}{1-z}}}$.

Pour évaluer le nombre d_n de dérangements de taille ${\displaystyle n}$, on observe que la singularité de ${\displaystyle D(z)}$ est en ${\displaystyle z=1}$. Autour de ce point, le développement de ${\displaystyle D(z)}$ est

${\displaystyle D(z)\sim _{z\to 1}{\frac {e^{-1}}{1-z}}}$, de sorte ${\displaystyle d_{n}=[z^{n}]D(z)\sim {\frac {n!}{e}}}$.

Arbres. Un arbre enraciné est formé d'un sommet et d'un ensemble de sous-arbres. Ce sont des structures étiquetées ou non. Pour les arbres étiquetés, l'équation symbolique est

${\displaystyle {\mathcal {T}}={\mathcal {Z}}\star {\mathsf {Set}}({\mathcal {T}})}$,

et la série exponentielle correspondante est :

${\displaystyle T(z)=z\exp(T(z))}$.

Pour un arbre plane enraciné et non étiqueté, formé d'un sommet et d'une suite de sous-arbres, l'équation symbolique est

${\displaystyle {\mathcal {T}}={\mathcal {Z}}\times {\mathsf {Seq}}({\mathcal {T}})}$,

et la série génératrice ordinaire est :

${\displaystyle T(z)={\frac {z}{1-z}}}$.

La construction de la classe des multi-ensembles ou parties avec multiplicité est semblable à celle des parties. Dans la classe

${\displaystyle {\mathcal {A}}={\mathsf {MSet}}({\mathcal {B}})}$,

chaque élément de ${\displaystyle {\mathcal {B}}}$ peut figurer un nombre arbitraire de fois dans une partie. On obtient :

${\displaystyle {\mathcal {A}}={\mathsf {MSet}}({\mathcal {B}})=\prod _{b\in {\mathcal {B}}}{\mathsf {Seq}}(\{b\}).}$

Ceci conduit à la relation (ici ${\displaystyle B_{n}}$ est le nombre d'éléments de taille ${\displaystyle n}$ de ${\displaystyle {\mathcal {B}}}$) :

${\displaystyle {\begin{aligned}A(z)&{}=\prod _{b\in {\mathcal {B}}}(1-z^{|b|})^{-1}=\prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\\&{}=\exp \left(\log \prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\right)=\exp \left(\sum _{n=1}^{\infty }-B_{n}\log(1-z^{n})\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {B(z^{k})}{k}}\right),\end{aligned}}}$

Un exemple d'application est constitué des partitions d'entiers. On définit d'abord la classe des entiers positifs, notée ici ${\displaystyle {\mathcal {I}}}$, où la taille de chaque entier est sa valeur

${\displaystyle {\mathcal {I}}={\mathcal {Z}}\times {\mathsf {Seq}}({\mathcal {Z}})}$.

La série génératrice de${\displaystyle {\mathcal {I}}}$ iest alors

${\displaystyle I(z)={\frac {z}{1-z}}.}$

L'ensemble des partitions d'entiers est la classe des multi-ensembles d'entiers positifs. Si on la note ${\displaystyle {\mathcal {P}}}$, on obtient donc la formule

${\displaystyle {\mathcal {P}}={\mathsf {MSet}}({\mathcal {I}}).}$

La série génératrice de ${\displaystyle {\mathcal {P}}}$ est

${\displaystyle P(z)=\exp \left(I(z)+{\frac {1}{2}}I(z^{2})+{\frac {1}{3}}I(z^{3})+\cdots \right).}$

Il n'y a pas de formule close connue pour cette série, mais on peut calculer la valeur asymptotique de ses coefficients.