Combinatoire

Pour les articles homonymes, voir combinatoire (homonymie).

Une planche de l'encyclopédie de Diderot et d'Alembert illustrant l'article « Carreleur »

En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.

Généralités et historique

La combinatoire remonte à l'Antiquité  : Plutarque rapporte ainsi un débat entre Chrysippe et Hipparque sur le nombre de façons de combiner dix propositions, le résultat n'ayant été compris qu'au XX^e siècle. Parmi, les autres précurseurs, on peut citer Bhāskara II au XII^e siècle (nombre de choix de p éléments parmi n), Raymond Lulle au XIII^e siècle, Gersonide au début du XIV^e siècle (rapport entre le nombre d'arrangements et le nombre de combinaison), Michael Stifel au XVI^e siècle (première approche du triangle de Pascal). Elle se développe de façon significative à partir du XVII^e siècle, en même temps que le calcul des probabilités avec Blaise Pascal et Pierre de Fermat. Initialement, elle avait pour objet la résolution des problèmes de dénombrement, provenant de l'étude des jeux de hasard. Plus tard, elle se lia à la théorie des nombres et à la théorie des graphes.

En particulier, la combinatoire s'intéresse aux méthodes permettant de compter les éléments dans des ensembles finis (combinatoire énumérative) et à la recherche des optima dans les configurations ainsi qu'à leur existence (combinatoire extrémale).

Voici quelques exemples de situations donnant lieu à des questions d'analyse combinatoire :

• les rangements de livres sur une étagère ;
• les dispositions de personnes autour d'une table ronde ;
• les tirages avec remise d'un certain nombre de boules numérotées dans une urne ;
• les placements de jetons sur un damier ;
• le nombre d'ordonnancements possibles des cartes d'un jeu de 52 cartes.

Dans ce dernier exemple, le nombre est égal à 52! (le « ! » dénotant la factorielle). Il peut sembler étonnant que ce nombre, environ 8,065817517094 ×10⁶⁷, soit si grand. C'est environ 8 suivi de 67 zéros. Il est, par exemple, plus grand que le nombre d'Avogadro, égal à 6,022 ×10²³.

Domaines de la combinatoire

La combinatoire moderne comporte de nombreux champs très développés, et utilise des outils puissants empruntés à des branches mathématiques parfois inattendues ; on distingue ainsi :

• Combinatoire arithmétique
• Combinatoire des mots
• Combinatoire algébrique
• Combinatoire analytique
• Combinatoire probabiliste
• Combinatoire topologique (en)
• Combinatoire géométrique (en)
• Théorie de Ramsey ;

de plus, on rencontre des outils combinatoires en

• Théorie des graphes
• Théorie des partitions
• Théorie des matroïdes
• Théorie des ordres
• Conception combinatoire (en)
• Théorie des séries génératrices.

Dénombrement dans des ensembles finis

Théorèmes fondamentaux

Dans cette section, si A est un ensemble fini, on note $\mathrm{card}(A)$ (lire « cardinal de A ») le nombre de ses éléments. Par exemple, $\mathrm{card}(\{e, f, g\}) = 3$.

Théorème 1 — Soit $A$ une partie d'un ensemble fini $E$.
Alors A est elle-même finie et $\mathrm{card}(A)$ ≤ $\mathrm{card}(E)$.
Si en outre $\mathrm{card}(A)=\mathrm{card}(E)$, alors $A=E$.

Caractérisation des applications injectives — Soit $E$ un ensemble fini, $F$ un ensemble et $f$ une application de $E$ dans $F$.
On a :

1. $\mathrm{card}(f(E))$ ≤ $\mathrm{card}(E)$
2. $f$ est injective $\Leftrightarrow$ $\mathrm{card}(f(E))=\mathrm{card}(E)$

Démonstration

Pour démontrer le point 1, on peut s'intéresser à l'ensemble des éléments de $E$ qui ont une image par $f$. Si on le note $A$, alors l'application induite par $f$ de $A$ dans $f(E)$ est une bijection. Comme $A$ est un sous-ensemble de $E$, il est fini et $\mathrm{card}(f(E))=\mathrm{card}(A)$ ≤ $\mathrm{card}(E)$.
Le point 2 vient du fait que lorsque $f$ est injective, tous les éléments de $f(E)$ ont un antécédent unique, donc l'application induite de $E$ dans $f(E)$ est une bijection. Donc $\mathrm{card}(f(E))=\mathrm{card}(E)$. Réciproquement si $\mathrm{card}(f(E))=\mathrm{card}(E)$, alors $\mathrm{card}(A)=\mathrm{card}(E)$ puis il vient que $A=E$.

Corollaire — Soit $f$ une application injective d'un ensemble $E$ dans un ensemble $F$.
si $f(E)$ est fini, alors $E$ est fini et $\mathrm{card}(E)=\mathrm{card}(f(E))$.

Ce corollaire n'est en fait que l'application de la caractérisation des applications injectives dans le cas particulier où l'ensemble d'arrivée de $f$ est $f(E)$.

Théorème — Soit E et F deux ensembles finis tels que $\mathrm{card}(E)=\mathrm{card}(F)$. Si $f$ est une application de $E$ dans $F$ on a :
$f$ est injective $\Leftrightarrow$ $f$ est surjective $\Leftrightarrow$ $f$ est bijective.

Propriétés

Cardinal de l'union de deux ensembles finis disjoints —  Soient $E$ et $F$ deux ensembles finis disjoints avec $\mathrm{card}(E)=k$ et $\mathrm{card}(F)=n$.
Alors on a $\mathrm{card}(E \cup F) = \mathrm{card}(E) + \mathrm{card}(F) = n+k$.

Démonstration

En effet soient $f$ une bijection de $E$ dans $[\![ 1,k ]\!]$ et $g$ une bijection de $F$ dans $[\![ 1+k,n+k ]\!]$, alors on peut construire $h$ l'application de $E \cup F$ dans $[\![ 1,n+k ]\!]$ dont la restriction à $E$ est $f$ et celle à $F$ est $g$. Comme $h$ est une bijection, c'est une injection et le corollaire de caractérisation conclue que $\mathrm{card}(h(E \cup F))=\mathrm{card}( [\![ 1,n+k ]\!] )=n+k$.

Par récurrence, on généralise cette propriété à une famille d'ensembles finis disjoints :

Cardinal de l'union de $n$ ensembles finis deux-à-deux disjoints —  Soit $(E_i)_{i=1}^n$ une famille de $n$ ensembles finis deux à deux disjoints.
Alors on a $\mathrm{card}(\bigcup_{i=1}^n E_i)=\sum_{i=1}^n(\mathrm{card}(E_i))$.

Cardinal du complémentaire —  Soit $E$ un ensemble fini, $A \subset E$, et $\overline A$ son complémentaire dans $E$.
Alors on a $\mathrm{card}(A)+\mathrm{card(\overline A)}=\mathrm{card}(E)$.

Démonstration

Démonstration : $A$ et $\overline A$ sont deux ensembles finis d'intersection vide et $A \cup \overline A=E$. La première propriété permet de conclure.

Cardinal de l'union de deux ensembles finis —  Soient $E$ et $F$ deux ensembles finis.
Alors on a $\mathrm{card}(E \cup F) = \mathrm{card}(E) + \mathrm{card}(F) - \mathrm{card}(E \cap F)$.

Démonstration

Démonstration : Comme $A \cap B$ et $A-B$ sont complémentaires dans $A$, la propriété précédente s'applique et on a $\mathrm{card}(A \cap B)$ + $\mathrm{card}(A - B)=\mathrm{card}(A)$. Ce même raisonnement s'applique pour $B-A$ et $A \cap B$. Remarquons enfin que $A-B$,$A \cap B$ et $B-A$ forment une partition de $A \cup B$. L'identité se déduit des trois résultats précédents.

Cardinal de la réunion disjointe de deux ensembles finis — Soient $E$ et $F$ deux ensembles finis de cardinaux respectifs $n$ et $k$.
Alors $E\sqcup F$ est finie de cardinal $\mathrm{card}(E\sqcup F) = \mathrm{card}(E) + \mathrm{card}(F) = n+k$.

Ce résultat peut se généraliser à plus de deux ensembles.

Cardinal de la réunion disjointe de $n$ ensembles finis — Soient $E_i$ une famille d'ensembles finis.
$\mathrm{card}(E_1\sqcup E_2\sqcup E_3\,\dots\,\sqcup E_n) = \sum_{i=1}^n\mathrm{card}(E_i).$

Cardinal du produit cartésien de deux ensembles finis — Soient $E$ et $F$ deux ensembles finis de cardinaux respectif $n$ et $k$.
Alors $E\times F$ est fini de cardinal $\mathrm{card}(E\times F) = \mathrm{card}(E) \times \mathrm{card}(F) =nk$.

Plus généralement, pour une suite d'ensembles finis :

Cardinal du produit cartésien d'une suite d'ensembles finis — Soient $E_i$ une famille d'ensembles finis.
Alors $\mathrm{card}(E_1\times E_2\times E_3\,\dots\,\times E_n) = \prod_{i=1}^n\mathrm{card}(E_i).$

Cardinal des parties d'un ensemble fini — Soient $E$ un ensemble fini de cardinal $k$.
Comme $\mathcal P(E)$ est en correspondance biunivoque avec l'ensemble des applications de $E$ dans $\left\{0,1\right\}$, alors $\mathcal P(E)$ est un ensemble fini et on a $\mathrm{card}(\mathcal P(E)) = 2^{\mathrm{card}(E)} =2^k$.

Cardinal de l'ensemble des correspondances de $E$ dans $F$ — Soient $E$ et $F$ deux ensembles finis.
L'ensemble des correspondances de $E$ dans $F$, noté habituellement $\mathrm{Corr}(E, F)$, s'identifie à $\mathcal P(E\times F)$ donc est fini de cardinal $\ \mathrm{card}(\mathrm{Corr}(E, F)) = 2^{\mathrm{card}(E)\times \mathrm{card}(F)} = 2^{nk}$.

Cardinal de l'ensemble des applications de $E$ dans $F$ — Soient $E$ et $F$ deux ensembles finis de cardinaux respectifs $k$ et $n$.
L'ensemble des applications de $E$ dans $F$, souvent noté $\mathcal F (E, F)$, est fini de cardinal $\ \mathrm{card}(\mathcal F(E, F)) = \mathrm{card}(F)^{\mathrm{card}(E)} =n^k$ avec la convention 0⁰=1 si $E$ et $F$ sont tous deux vides.

Cette propriété justifie la notation plus courante $F^E$.

Cardinal des surjections de $E$ dans $F$ — Soient $E$ et $F$ deux ensembles finis de cardinaux respectifs $k$ et $n$.
L'ensemble des surjections de $E$ dans $F$, noté habituellement $\mathrm{Surj}(E, F)$, a pour cardinal la somme suivante:
$\ \mathrm{card}(\mathrm{Surj}(E, F)) = \sum_{i = 0}^{n} (-1)^{i} \frac{n!}{ i! (n - i)! } (n - i)^{k}$.
Cette somme est nulle si $\mathrm{card}(E)<\mathrm{card}(F)$.

Les applications injectives, qui jouent un rôle important en combinatoire, sont traitées de manière plus approfondie dans les paragraphes suivants.

Permutations (dispositions, ordonnancements)

Permutations sans répétition d'objets discernables

Article détaillé : Permutation.

Les permutations sans répétition d'un ensemble fini E sont les bijections de E sur lui-même.

Comme exemple d'introduction, considérons le nombre de dispositions de six objets discernables dans six cases consécutives numérotées avec un et un seul objet par case. Chacun des objets peut être placé dans la première case, ce qui donne six possibilités d'occuper la première place. Une fois la première place occupée par l'un des objets, il reste encore cinq candidats pour la deuxième place, la deuxième place étant attribuée, il reste seulement quatre candidats pour la troisième place, et ainsi de suite. Pour l'avant-dernière place, il ne reste plus que deux objets, et une fois l'un des deux placé, la dernière place doit être occupée par le dernier objet.

Il y a ainsi 6 × 5 × 4 × 3 × 2 × 1 ou 6! = 720 possibilités de disposer six objets discernables.

Généralisation 

Nous allons voir que le nombre de dispositions de n éléments discernables est égal à n !

Une disposition des objets d'un ensemble E de cardinal n, dans n cases avec un et un seul objet par case, ou un ordonnancement des éléments de E se représente par une bijection de {1, 2, …, n} dans E ou une permutation de E. Il est commode de représenter une telle bijection par un n-uplet (ou n-liste) d'éléments de E, (x₁, x₂, …, x_n).

Théorème — Il y a n! permutations (sans répétition) de n éléments.

En effet, pour former un n-uplet d'éléments de E, nous devons choisir un élément de E pour la première place du n-uplet et il y a n possibilités, il y a n - 1 choix possibles d'un élément de E pour la deuxième place, n - 2 pour la troisième etc. Il n'y a plus qu'un seul choix d'élément pour la dernière place. Donc au total n × (n-1) × (n-2) × … × 2 × 1 permutations.

Cette propriété se démontre par récurrence sur n.

Permutations avec répétition d'objets discernables

Article détaillé : permutation avec répétition.

Pour déterminer le nombre des dispositions possibles d'objets de plusieurs classes et mutuellement indiscernables dans chaque classe, il est utile de considérer le nombre de dispositions possibles de ces objets en les supposant tous discernables, et ensuite de trouver combien de ces dispositions sont indiscernables. Le nombre des dispositions possibles de ces objets est égal au nombre de dispositions possibles des objets considérés comme discernables divisé par le nombre des dispositions indiscernables.

Par exemple, si nous devons déterminer le nombre total de dispositions d'objets dont deux sont d'une première classe, trois d'une deuxième classe et cinq d'une troisième classe, alors nous calculons le nombre total de dispositions de ces objets considérés comme discernables, ce qui donne (2 + 3 + 5)!, soit 3 628 800 dispositions possibles. Mais certaines dispositions restent inchangées lorsque les objets indiscernables d'une même classe sont échangés mutuellement, et il y a 2! × 3! × 5! soit 1 440 façons de permuter les objets de chacune de ces classes.

Nous obtenons au total 3 628 800 ÷ 1 440 = 2 520 dispositions différentes. Il s'agit aussi du nombre de permutations avec répétition de 10 éléments avec 2, 3 et 5 répétitions.

Généralisation 

Théorème — Le nombre de permutations de n éléments, répartis dans k classes dont n₁ sont de classe 1, n₂ sont de classe 2, …, n_k sont de classe k, indiscernables dans chaque classe, ou le nombre de permutations de n éléments avec n₁, n₂, …, n_k répétitions, avec $\left ( \sum^k_{i=1} n_i = n \right )$, est égal à : $\frac{n!}{n_1! n_2! \ldots n_k!}$.

Arrangements (choix en tenant compte de l'ordre)

Arrangements sans répétition

Article détaillé : Arrangement.

Nous disposons de n objets discernables et nous voulons en placer k, en tenant compte de l'ordre, dans k cases numérotées de 1 à k avec un et un seul objet par case. Le nombre de dispositions est alors égal au nombre de k-listes distinctes formées à partir de ces objets. Au lieu de constituer un n-uplet, à partir de n objets discernables, nous formons ici des k-uplets avec $k \le n \text{,} \left( x_1, x_2, \ldots, x_k \right)$ à partir de ces n objets tels que pour $i \neq j$, on ait $x_i \neq x_j$. Un tel k-uplet s'appelle un arrangement sans répétition de n éléments pris k à k.

Théorème — Le nombre d'arrangements sans répétition de n éléments pris k à k est égal à $A_n^k$ (égal à $\frac{n!}{(n-k)!}$ si k≤n et à 0 sinon).

En effet, Il y a n choix possibles de l'objet qui occupe la première place du k-uplet, n-1 choix pour l'objet de la 2^e place ; pour la k^e, il ne reste plus que n-(k-1) objets et donc n-k+1 choix possibles. Le produit $n \cdot (n-1) \ldots (n-k+1)$ s'écrit bien sous la forme : $\frac{n!}{(n-k)!}$. C'est juste le nombre des injections de l'ensemble {1,2, ..., k} dans l'ensemble {1,2, ..., n}.

Le cas n = k nous oblige alors à diviser par (0)! (rappelons que (0)! vaut 1).

Arrangements avec répétition

Article détaillé : Arrangement avec répétition.

Lorsque nous voulons placer des objets pris parmi n objets discernables dans k emplacements en tenant compte de l'ordre, ces objets pouvant apparaître plusieurs fois, le nombre de dispositions est alors égal au nombre de k-uplets formés à partir de ces n objets. Un tel k-uplet, avec k≤n, (x₁, x₂, …, x_k) formé à partir de ces n objets s'appelle un arrangement avec répétition de n éléments pris k à k.

Comme chaque emplacement peut être occupé indifféremment par l'un quelconque de ces n objets, il y en a au total n^k.

Quand nous tirons 11 fois l'un de 3 numéros en tenant compte de l'ordre d'apparition nous obtenons au total 3¹¹ = 177 147 tirages différents. Comme exemple tiré de la génétique, nous pouvons donner le nombre total de codons de base (triplets formés de quatre codes) : 4³= 64.

Combinaisons (choix sans tenir compte de l'ordre)

Contrairement aux arrangements, les combinaisons sont des dispositions d'objets qui ne tiennent pas compte de l'ordre de placement de ces objets. Par exemple, si a, b et c sont des boules tirées d'une urne, abc et acb correspondent au même tirage. Il y a donc moins de combinaisons que d'arrangements.

Combinaisons sans répétition

Article détaillé : Combinaison (mathématiques).

Si nous tirons sans remise k objets parmi n objets discernables, et nous les disposons sans tenir compte de l'ordre d'apparition, nous pouvons représenter ces k objets par une partie à k éléments d'un ensemble à n éléments. Ce sont des combinaisons sans répétition de n éléments pris k à k.

Pour déterminer le nombre de ces dispositions, nous pouvons déterminer le nombre d'arrangements de k objets et diviser par le nombre de dispositions obtenues les unes à partir des autres par une permutation. Il y en a ${n \choose k}=\frac{A_n^k}{k!}=C_n^k$ (pour la notation, voir aussi l'article sur le coefficient binomial).

Par exemple le jeu Euromillions demande de choisir 5 nombres différents entre 1 et 50 et 2 nombres entre 1 et 11, soit ${50 \choose 5} \times {11 \choose 2}=116\,531\,800$ possibilités.

Combinaisons avec répétition

Article détaillé : Combinaison avec répétition.

Si nous tirons avec remise k objets parmi n objets discernables, et nous les disposons sans tenir compte de l'ordre d'apparition; ces objets peuvent apparaître plusieurs fois et nous ne pouvons les représenter ni avec une partie à k éléments, ni avec un k-uplet puisque leur ordre de placement n'intervient pas. Il est cependant possible de représenter de telles dispositions avec des applications appelées combinaisons avec répétition.

Théorème — Le nombre de combinaisons avec répétition de n éléments pris k à k est égal à : $\Gamma_n^k={ n+k-1 \choose k}$.

Donnons l'exemple du jeu de domino. Les pièces sont fabriquées en disposant côte à côte deux éléments de l'ensemble {blanc, 1, 2, 3, 4, 5, 6}. Si nous retournons un domino, nous changeons l'ordre des deux éléments, mais le domino reste identique. Nous avons une combinaison avec répétition de 7 éléments pris 2 à 2, et au total il y a : $\Gamma_7^2={8 \choose 2}=28$ dominos dans un jeu.

Fonction de comptage

Soit S_n l'ensemble des permutations de {1, 2, …, n}. Nous pouvons considérer la fonction qui à n associe le nombre de permutations. Cette fonction est la fonction factorielle et sert à compter les permutations.

Étant donnée une collection infinie d'ensembles finis $\left\{ E_n | n \in \mathbb{N} \right\}$ indexée par l'ensemble des entiers naturels, une fonction de comptage est une fonction qui à un entier n associe le nombre d'éléments de E_n. Une fonction de comptage f permet donc de compter les objets de E_n pour n'importe quel n. Les éléments de E_n ont habituellement une description combinatoire relativement simple et une structure additionnelle, permettant souvent de déterminer f.

Certaines fonctions de comptage, sont données par des formules « fermées », et peuvent être exprimées comme composées de fonctions élémentaires telles que des factorielles, des puissances, et ainsi de suite.

Cette approche peut ne pas être entièrement satisfaisante (ou pratique) pour certains problèmes combinatoires. Par exemple, soit f(n) le nombre de sous-ensembles distincts de nombres entiers dans l'intervalle [1, n] qui ne contiennent pas deux nombres entiers consécutifs. Par exemple, avec n = 4, nous obtenons ∅, { 1 }, { 2 }, { 3 }, { 4 }, { 1, 3 }, { 1, 4 }, { 2, 4 }, et donc f(4) = 8. Il s'avère que f(n) est le nème nombre de Fibonacci, qui peut être exprimé sous la forme « fermée » suivante :

$f(n)=\frac{\phi^n}{\sqrt{5}}-\frac{(1-\phi)^n}{\sqrt{5}}$

où Φ = (1 + √5)/2, est le nombre d'or. Cependant, étant donné que nous considérons des ensembles de nombres entiers, la présence du √5 dans le résultat peut être considérée comme inesthétique d'un point de vue combinatoire. Aussi f(n) peut-il être exprimé par une relation de récurrence :

f(n) = f(n - 1) + f (n - 2)

ce qui peut être plus satisfaisant (d'un point de vue purement combinatoire), puisque la relation montre plus clairement comment le résultat a été trouvé.

Dans certains cas, un équivalent asymptotique g de f,

f(n)~g(n) quand n tend vers l'infini

où g est une fonction « familière », permet d'obtenir une bonne approximation de f. Une fonction asymptotique simple peut être préférable à une formule « fermée » extrêmement compliquée et qui informe peu sur le comportement du nombre d'objets. Dans l'exemple ci-dessus, un équivalent asymptotique serait :

$f(n)\sim\frac{\phi^n}{\sqrt{5}}$

quand n devient grand.

Une autre approche est celle des séries entières. f(n) peut être exprimé par une série entière formelle, appelée fonction génératrice de f, qui peut être le plus couramment :

• la fonction génératrice ordinaire

$\sum_{n > 0} f(n) \cdot x^n$

• ou la fonction génératrice exponentielle

$\sum_{n > 0} f(n) \cdot \frac{x^n}{n!}$

Une fois déterminée, la fonction génératrice peut permettre d'obtenir toutes les informations fournies par les approches précédentes. En outre, les diverses opérations usuelles comme l'addition, la multiplication, la dérivation, etc., ont une signification combinatoire ; et ceci permet de prolonger des résultats d'un problème combinatoire afin de résoudre d'autres problèmes.

Quelques résultats

Un théorème, dû à Franck P. Ramsey, donne un résultat surprenant. À une soirée à laquelle se rendent au moins six personnes, il y a au moins trois personnes qui se connaissent mutuellement ou au moins trois qui sont étrangères les unes aux autres.

Démonstration 

soit $P_1$ une personne quelconque présente à la soirée. Sur les n-1 autres, soit elle en connaît au plus deux, soit elle en connaît au moins trois. Supposons que l’on est dans le second cas, et soient $P_2,\, P_3 \text{ et } P_4$ trois personnes connues de $P_1$. Si deux d’entre elles se connaissent, mettons $P_2 \text{ et } P_3$, alors $P_1,\, P_2 \text{ et } P_3$ se connaissent toutes trois. Sinon, $P_2,\, P_3 \text{ et } P_4$ ne se connaissent pas du tout, et le résultat annoncé est encore juste. Dans l’autre cas de figure ($P_1$ connaît au plus deux personnes du groupe), le même raisonnement, inversé, fonctionne avec les trois personnes que $P_1$ ne connaît pas.

(C'est un cas particulier du théorème de Ramsey.)

L'idée de trouver un ordre dans des configurations aléatoires mène à la théorie de Ramsey. Essentiellement, cette théorie indique que n'importe quelle configuration suffisamment grande contiendra au moins un autre type de configuration.

Domaines connexes

• Optimisation combinatoire
• Théorie des codes
• Géométrie algorithmique
• Phylogénie

Voir aussi

Articles connexes

• Combinaison avec répétition
• Mathématiques discrètes
• Mot sans facteur carré
• Principe d'inclusion-exclusion de Moivre
• Coefficient binomial

Lien externe

(en) L'histoire de la pensée économique : à propos de Frank P. Ramsey.

Bibliographie

• (en) Richard P. Stanley, Enumerative Combinatorics, vol. 1 et 2 [détail des éditions] (LCCN 96044267) [présentation en ligne] 
• (en) Nicholas A. Loehr, Bijective combinatorics, Chapman Hall/CRC, 2011 (ISBN 978-1-4398-4884-5) 
• Claude Berge, Principes de combinatoire, Paris, Dunod, 1968 
  Traduction anglaise : Principles of Combinatorics, Academic Press, 1971 (ISBN 978-0124109780) 
• Louis Comtet, Analyse combinatoire, Tomes I et II, Paris, Presses Universitaires de France, coll. « Sup - Le Mathématicien », 1970 
• Louis Comtet, Advanced Combinatorics : The Art of Finite and Infinite Expansions, Dordrecht, Reidel, 1974 (ISBN 978-902770441-2) [lire en ligne] 
  Traduit du français par J. W. Nienhuys. Réimpression par Springer Netherlands en 2010 (ISBN 978-9048183418) [présentation en ligne]