Appendice B
Rappels mathématiques : combinatoire
Nous rassemblons ici les notions de combinatoire que nous utilisons dans ce
livre. Pour approfondir ces notions, le livre de Graham et al. Mathématiques
concrètes [122] permet de se familiariser avec la manipulation de coefficients
binomiaux, d’autres nombres « classiques », de sommations ou de fonctions
génératrices, ainsi qu’avec quelques notions de probabilités discrètes et de calcul
asymptotique. Le livre plus ancien de Greene et Knuth, Mathematics for the Analysis of Algorithms [123], est intéressant car il rassemble dans un seul ouvrage les
outils mathématiques nécessaires à l’analyse des algorithmes (identités binomiales,
relations de récurrence, analyse asymptotique) et utilise des fonctions génératrices.
Pour la combinatoire analytique, la référence est le livre de Flajolet et Sedgewick,
Analytic Combinatorics [94].
Nous présentons ici les notions de base de combinatoire analytique, notamment
la méthode symbolique, notions qui s’appuient sur quelques éléments d’analyse
complexe que nous rappelons autant que nécessaire. Plusieurs notations, fonctions
et formules classiques sont réunies dans la section finale B.5.1.
Nous renvoyons souvent au livre de Flajolet et Sedgewick [94], y compris pour
des résultats basiques de mathématiques qui se trouvent évidemment aussi dans des
livres de mathématiques classiques, et exposés de façon plus complète. Ce choix se
justifie par une plus grande facilité d’utilisation pour le lecteur de notre livre.
B.1 Structures combinatoires
B.1.1 Classes
Une classe combinatoire (ou classe) est un ensemble C muni d’une application «
taille » notée |·| : C → N et tel que l’ensemble C n = {γ ∈ C; |γ | = n} des
éléments (dits aussi objets) de taille n soit fini pour tout n ≥ 0.
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0
447
Rappels mathématiques : combinatoire
Nous rassemblons ici les notions de combinatoire que nous utilisons dans ce
livre. Pour approfondir ces notions, le livre de Graham et al. Mathématiques
concrètes [122] permet de se familiariser avec la manipulation de coefficients
binomiaux, d’autres nombres « classiques », de sommations ou de fonctions
génératrices, ainsi qu’avec quelques notions de probabilités discrètes et de calcul
asymptotique. Le livre plus ancien de Greene et Knuth, Mathematics for the Analysis of Algorithms [123], est intéressant car il rassemble dans un seul ouvrage les
outils mathématiques nécessaires à l’analyse des algorithmes (identités binomiales,
relations de récurrence, analyse asymptotique) et utilise des fonctions génératrices.
Pour la combinatoire analytique, la référence est le livre de Flajolet et Sedgewick,
Analytic Combinatorics [94].
Nous présentons ici les notions de base de combinatoire analytique, notamment
la méthode symbolique, notions qui s’appuient sur quelques éléments d’analyse
complexe que nous rappelons autant que nécessaire. Plusieurs notations, fonctions
et formules classiques sont réunies dans la section finale B.5.1.
Nous renvoyons souvent au livre de Flajolet et Sedgewick [94], y compris pour
des résultats basiques de mathématiques qui se trouvent évidemment aussi dans des
livres de mathématiques classiques, et exposés de façon plus complète. Ce choix se
justifie par une plus grande facilité d’utilisation pour le lecteur de notre livre.
B.1 Structures combinatoires
B.1.1 Classes
Une classe combinatoire (ou classe) est un ensemble C muni d’une application «
taille » notée |·| : C → N et tel que l’ensemble C n = {γ ∈ C; |γ | = n} des
éléments (dits aussi objets) de taille n soit fini pour tout n ≥ 0.
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0
447