Dénombrement

Leçon 1 : Ensembles, principe additif et principe multiplicatif

Voir la vidéo de la leçon 1

1.1 Vocabulaire des ensembles

Un ensemble fini $E$ est formé d'un nombre fini d'objets, ses éléments. On écrit $x \in E$ (« $x$ appartient à $E$ »). On peut donner un ensemble en extension, en écrivant ses éléments entre accolades : $E = \{a\,;b\,;c\}$. L'ordre d'écriture ne compte pas, et chaque élément n'est écrit qu'une fois : $\{a\,;b\,;c\} = \{c\,;a\,;b\}$.

• Le cardinal de $E$, noté $\mathrm{Card}(E)$, est son nombre d'éléments. Par exemple $\mathrm{Card}(\{a\,;b\,;c\}) = 3$.
• L'ensemble vide, noté $\varnothing$, n'a aucun élément : $\mathrm{Card}(\varnothing) = 0$.
• $A$ est une partie (ou un sous-ensemble) de $E$, et on note $A \subset E$, si tout élément de $A$ est un élément de $E$. L'ensemble vide et $E$ lui-même sont des parties de $E$.
• Pour deux parties $A$ et $B$ de $E$ : l'intersection $A \cap B$ contient les éléments communs à $A$ et à $B$ ; la réunion $A \cup B$ contient les éléments qui sont dans $A$ ou dans $B$ (ou dans les deux) ; le complémentaire de $A$ dans $E$, noté $\overline{A}$ ou $E \setminus A$, contient les éléments de $E$ qui ne sont pas dans $A$.
• $A$ et $B$ sont disjoints s'ils n'ont aucun élément commun : $A \cap B = \varnothing$.

1.2 Le principe additif

Propriété (programme : principe additif). Si $A$ et $B$ sont deux ensembles finis disjoints, alors $\mathrm{Card}(A \cup B) = \mathrm{Card}(A) + \mathrm{Card}(B).$ Plus généralement, si $A_1, A_2, \ldots, A_p$ sont des ensembles finis deux à deux disjoints, alors $\mathrm{Card}(A_1 \cup A_2 \cup \cdots \cup A_p) = \mathrm{Card}(A_1) + \mathrm{Card}(A_2) + \cdots + \mathrm{Card}(A_p)$.

Exemple 1. Le jeudi après-midi, un lycée propose $4$ sports et $3$ ateliers artistiques. Chaque élève choisit une seule activité. Les deux listes n'ont aucune activité en commun : il y a $4 + 3 = 7$ choix possibles.

Conséquence : le complémentaire. Une partie $A$ de $E$ et son complémentaire $\overline{A}$ sont disjoints, et leur réunion est $E$. Donc $\mathrm{Card}(\overline{A}) = \mathrm{Card}(E) - \mathrm{Card}(A).$ C'est souvent plus rapide de compter ce que l'on ne veut pas, puis de le retirer du total.

Quand les ensembles ne sont pas disjoints, on découpe en morceaux disjoints.

Exemple 2. Dans une classe de $35$ élèves, $18$ chantent dans la chorale, $10$ font partie du club d'échecs, et $4$ font les deux.

• Seulement la chorale : $18 - 4 = 14$ élèves ; seulement les échecs : $10 - 4 = 6$ élèves ; les deux : $4$ élèves.
• Ces trois groupes sont disjoints. Par le principe additif, $14 + 6 + 4 = 24$ élèves pratiquent au moins l'une des deux activités.
• Par complémentaire, $35 - 24 = 11$ élèves ne pratiquent aucune des deux.

On peut ranger ces nombres dans un tableau à double entrée :

	Échecs	Pas échecs	Total
Chorale	$4$	$14$	$18$
Pas chorale	$6$	$11$	$17$
Total	$10$	$25$	$35$

Remarque. Ce découpage donne la formule $\mathrm{Card}(A \cup B) = \mathrm{Card}(A) + \mathrm{Card}(B) - \mathrm{Card}(A \cap B)$ : dans $\mathrm{Card}(A) + \mathrm{Card}(B)$, les éléments de $A \cap B$ sont comptés deux fois. Ici, $18 + 10 - 4 = 24$.

1.3 Couples, $k$-uplets et produit cartésien

Ces notions sont définies pour des ensembles quelconques, finis ou non.

• Un couple $(x\,;y)$ est formé d'un premier élément $x$ et d'un second élément $y$. L'ordre compte : $(1\,;2) \neq (2\,;1)$. Deux couples sont égaux quand ils ont le même premier élément et le même second élément. Un couple peut avoir deux fois le même élément : $(1\,;1)$.
• Le produit cartésien de deux ensembles $E$ et $F$ est l'ensemble des couples dont le premier élément est dans $E$ et le second dans $F$ : $E \times F = \{(x\,;y) \text{ avec } x \in E \text{ et } y \in F\}.$
• De même, un triplet $(x\,;y\,;z)$ a trois éléments rangés dans un ordre, et un $k$-uplet (ou $k$-liste) $(x_1\,;x_2\,;\ldots\,;x_k)$ en a $k$. Le produit cartésien $E_1 \times E_2 \times \cdots \times E_k$ est l'ensemble des $k$-uplets dont le premier élément est dans $E_1$, le deuxième dans $E_2$, etc.
• Si $A$ est un ensemble, on note $A^k = A \times A \times \cdots \times A$ ($k$ facteurs) l'ensemble des $k$-uplets d'éléments de $A$.

Exemples. Les couples de réels forment $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$ : ce sont les coordonnées des points du plan dans un repère. Les triplets de réels forment $\mathbb{R}^3$, qui repère les points de l'espace (chapitre 3).

1.4 Le principe multiplicatif

Propriété (programme : principe multiplicatif). Si $E$ et $F$ sont deux ensembles finis, alors $\mathrm{Card}(E \times F) = \mathrm{Card}(E) \times \mathrm{Card}(F).$ Plus généralement, $\mathrm{Card}(E_1 \times E_2 \times \cdots \times E_k) = \mathrm{Card}(E_1) \times \mathrm{Card}(E_2) \times \cdots \times \mathrm{Card}(E_k)$.

Pourquoi. Si $\mathrm{Card}(E) = n$ et $\mathrm{Card}(F) = p$, on range les couples dans un tableau à $n$ lignes (une par élément de $E$) et $p$ colonnes (une par élément de $F$) : il a $n \times p$ cases. On peut aussi dire que $E \times F$ est la réunion des $n$ ensembles disjoints $\{x\} \times F$, qui ont chacun $p$ éléments : principe additif.

Exemple 3. On lance une pièce, puis un dé à six faces. Une issue est un couple, par exemple $(P\,;3)$ (pile, puis trois). L'ensemble des issues est $\{P\,;F\} \times \{1\,;2\,;3\,;4\,;5\,;6\}$ : il y a $2 \times 6 = 12$ issues.

Exemple 4. La cantine propose $2$ entrées, $3$ plats et $2$ desserts. Un menu est un triplet (entrée ; plat ; dessert). Il y a $2 \times 3 \times 2 = 12$ menus. Un arbre les montre tous : $2$ branches au premier niveau, puis $3$ branches au bout de chacune, puis $2$ : $12$ chemins.

En pratique. Quand on fait un choix en plusieurs étapes, et que le nombre de possibilités à chaque étape ne dépend pas des choix précédents, on multiplie ces nombres.

Leçon 2 : Listes et parties d'un ensemble

Voir la vidéo de la leçon 2

2.1 Nombre de $k$-uplets

Propriété (programme). Si $A$ est un ensemble à $n$ éléments et $k \geq 1$ un entier, le nombre de $k$-uplets (ou $k$-listes) d'éléments de $A$ est $\mathrm{Card}(A^k) = n^k.$

C'est le principe multiplicatif avec $k$ facteurs égaux à $n$ : $n$ choix pour le premier élément, $n$ pour le deuxième, et ainsi de suite. Dans un $k$-uplet, l'ordre compte et les répétitions sont permises.

Exemple 5 (un code). Un cadenas a quatre molettes, chacune avec les chiffres de $0$ à $9$. Un code est un $4$-uplet de $\{0\,;1\,;\ldots\,;9\}$ : il y a $10^4 = 10\,000$ codes, de $0000$ à $9999$.

Exemple 6 (génétique). L'ADN est écrit avec quatre bases, notées $A$, $C$, $G$ et $T$. Une suite de trois bases, appelée codon, est un triplet de $\{A\,;C\,;G\,;T\}$ : il y a $4^3 = 64$ codons.

Exemple 7 (informatique). Un octet est une suite de huit bits, chacun valant $0$ ou $1$ : c'est un $8$-uplet de $\{0\,;1\}$. Il y a $2^8 = 256$ octets différents.

2.2 Nombre de parties d'un ensemble

Les parties de $E = \{a\,;b\,;c\}$, rangées selon leur nombre d'éléments, sont :

• $\varnothing$ ;
• $\{a\}$, $\{b\}$, $\{c\}$ ;
• $\{a\,;b\}$, $\{a\,;c\}$, $\{b\,;c\}$ ;
• $\{a\,;b\,;c\}$.

Il y en a $8 = 2^3$.

Propriété (programme). Un ensemble à $n$ éléments a $2^n$ parties.

Pourquoi : un codage par des 0 et des 1. Écrivons $E = \{x_1\,;x_2\,;\ldots\,;x_n\}$. À chaque partie $A$ de $E$, on associe le $n$-uplet $(c_1\,;c_2\,;\ldots\,;c_n)$ de $\{0\,;1\}$ défini par : $c_i = 1$ si $x_i \in A$, et $c_i = 0$ sinon.

• Pour $E = \{a\,;b\,;c\}$ : $\{a\,;c\}$ est codée par $(1\,;0\,;1)$, $\varnothing$ par $(0\,;0\,;0)$ et $E$ par $(1\,;1\,;1)$.
• Inversement, un $n$-uplet de $\{0\,;1\}$ code une seule partie : celle des éléments $x_i$ pour lesquels $c_i = 1$.

Chaque partie correspond ainsi à un $n$-uplet de $\{0\,;1\}$ et un seul, et réciproquement (c'est une bijection). Il y a donc autant de parties que de $n$-uplets de $\{0\,;1\}$, c'est-à-dire $2^n$.

Trois autres façons de voir ces $2^n$ objets (programme).

• Des mots de longueur $n$ sur un alphabet à deux lettres : $(1\,;0\,;1)$ s'écrit simplement $101$.
• Des chemins dans un arbre à $n$ niveaux, avec deux branches à chaque nœud : au niveau $i$, on prend $x_i$ ou on ne le prend pas. L'arbre a $2^n$ chemins.
• Les issues d'une succession de $n$ épreuves à deux issues, succès $S$ ou échec $\overline{S}$ (les épreuves de Bernoulli du chapitre 11) : une issue est un $n$-uplet de $\{S\,;\overline{S}\}$, et il y en a $2^n$. Pour $n = 3$ : $SSS$, $SS\overline{S}$, $S\overline{S}S$, $S\overline{S}\,\overline{S}$, $\overline{S}SS$, $\overline{S}S\overline{S}$, $\overline{S}\,\overline{S}S$, $\overline{S}\,\overline{S}\,\overline{S}$.

Exemple 8. Une pizzeria propose une base, sur laquelle on ajoute ou non chacun de $6$ ingrédients. Une pizza correspond à une partie de l'ensemble des $6$ ingrédients : il y a $2^6 = 64$ pizzas différentes, en comptant la pizza sans ingrédient (la partie vide).

Leçon 3 : Listes d'éléments distincts, permutations

Voir la vidéo de la leçon 3

3.1 Un exemple : le podium

Huit nageuses disputent la finale d'un $100$ mètres. Combien de podiums (or, argent, bronze) sont possibles ?

• $8$ choix pour la médaille d'or ;
• puis $7$ pour l'argent (toutes sauf la gagnante) ;
• puis $6$ pour le bronze.

Le nombre de choix à chaque étape ne dépend pas des choix déjà faits. Par le principe multiplicatif, il y a $8 \times 7 \times 6 = 336$ podiums. Un podium est un triplet de nageuses distinctes.

3.2 Nombre de $k$-uplets d'éléments distincts

Propriété (programme). Soit $E$ un ensemble à $n$ éléments et $k$ un entier tel que $1 \leq k \leq n$. Le nombre de $k$-uplets d'éléments distincts de $E$ est $n(n-1)(n-2)\cdots(n-k+1) \qquad (k \text{ facteurs}).$

Pourquoi. On choisit les éléments un par un : $n$ choix pour le premier, $n - 1$ pour le deuxième (tous sauf le premier), …, $n - k + 1$ pour le $k$-ième. Si $k > n$, il n'existe aucun $k$-uplet d'éléments distincts.

Exemple 9. Un code de $4$ chiffres dont les chiffres sont tous différents est un $4$-uplet d'éléments distincts de $\{0\,;1\,;\ldots\,;9\}$ : il y en a $10 \times 9 \times 8 \times 7 = 5\,040$. Par complémentaire, $10\,000 - 5\,040 = 4\,960$ codes ont au moins deux chiffres égaux.

3.3 La factorielle

Définition (programme). Pour tout entier $n \geq 1$, la factorielle de $n$ est $n! = 1 \times 2 \times 3 \times \cdots \times n.$ Par convention, $0! = 1$. On lit « factorielle $n$ ».

Pour tout entier $n \geq 0$, $(n + 1)! = (n + 1) \times n!$. La factorielle grandit très vite : $20! \approx 2{,}43 \times 10^{18}$.

3.4 Permutations

Définition. Une permutation d'un ensemble fini $E$ à $n$ éléments est un $n$-uplet d'éléments distincts de $E$ : c'est une façon de ranger tous les éléments de $E$ dans un ordre.

Propriété (programme). Le nombre de permutations d'un ensemble à $n$ éléments est $n!$.

C'est le cas $k = n$ de la propriété 3.2 : $n(n - 1) \cdots 2 \times 1 = n!$.

Exemple 10. Les permutations de $\{a\,;b\,;c\}$ sont $(a\,;b\,;c)$, $(a\,;c\,;b)$, $(b\,;a\,;c)$, $(b\,;c\,;a)$, $(c\,;a\,;b)$ et $(c\,;b\,;a)$ : il y en a $3! = 6$.

Exemple 11. On range $5$ livres différents sur une étagère : il y a $5! = 120$ rangements. De même, en mélangeant les cinq lettres, toutes différentes, du mot PLAGE, on écrit $120$ mots (qui ont un sens ou non).

3.5 Écriture avec des factorielles

Pour $1 \leq k \leq n$ : $n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!},$ car les facteurs de $1$ à $n - k$ de $n!$ se simplifient avec ceux de $(n - k)!$. Par exemple, $8 \times 7 \times 6 = \dfrac{8!}{5!} = \dfrac{40\,320}{120} = 336$.

Leçon 4 : Combinaisons

Voir la vidéo de la leçon 4

4.1 Définition

Définition (programme). Soit $E$ un ensemble à $n$ éléments et $k$ un entier tel que $0 \leq k \leq n$. Une combinaison de $k$ éléments de $E$ est une partie de $E$ à $k$ éléments. Leur nombre se note $\binom{n}{k}, \qquad \text{qui se lit « } k \text{ parmi } n \text{ ».}$

Dans une combinaison, l'ordre ne compte pas et il n'y a pas de répétition. Les nombres $\binom{n}{k}$ sont aussi appelés coefficients binomiaux.

Exemple 12. Les parties à $2$ éléments de $E = \{a\,;b\,;c\,;d\}$ sont $\{a\,;b\}$, $\{a\,;c\}$, $\{a\,;d\}$, $\{b\,;c\}$, $\{b\,;d\}$ et $\{c\,;d\}$. Donc $\dbinom{4}{2} = 6$.

4.2 Des listes aux parties : les formules

Toujours avec $E = \{a\,;b\,;c\,;d\}$, il y a $4 \times 3 = 12$ couples d'éléments distincts. Chaque partie $\{x\,;y\}$ donne exactement deux couples, $(x\,;y)$ et $(y\,;x)$. Donc $12 = 6 \times 2$, c'est-à-dire $\dbinom42 = \dfrac{4 \times 3}{2}$.

Cas général. Les $k$ éléments d'une partie à $k$ éléments peuvent être rangés de $k!$ façons : chaque partie donne $k!$ $k$-uplets d'éléments distincts. Et chaque $k$-uplet d'éléments distincts est obtenu une seule fois, à partir de la partie formée de ses éléments. Donc $k! \times \binom{n}{k} = n(n-1)\cdots(n-k+1).$

Propriété (programme : formules). Pour tous entiers $n$ et $k$ tels que $0 \leq k \leq n$ : $\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{(n-k)!\,k!}.$

Pour $k = 0$, le produit du numérateur n'a aucun facteur et vaut $1$ par convention ; la seconde formule donne directement $\dfrac{n!}{n!\,0!} = 1$.

Exemple 13. $\dbinom{5}{2} = \dfrac{5 \times 4}{2} = 10$ et $\dbinom{6}{3} = \dfrac{6 \times 5 \times 4}{3 \times 2 \times 1} = \dfrac{120}{6} = 20$.

4.3 L'ordre compte-t-il ?

Exemple 14. Une association compte $12$ membres.

• Pour élire un bureau (un président, un trésorier, un secrétaire), l'ordre compte : chaque poste est différent. Un bureau est un triplet de membres distincts : $12 \times 11 \times 10 = 1\,320$ bureaux.
• Pour désigner une commission de $3$ membres, sans poste, l'ordre ne compte pas : une commission est une partie à $3$ éléments. Il y en a $\dbinom{12}{3} = \dfrac{1\,320}{3!} = 220$.

Chaque commission correspond à $3! = 6$ bureaux : on répartit les trois postes entre ses trois membres.

Exemple 15 (un jeu de cartes). Un jeu de $32$ cartes est distribué. Une main de $5$ cartes est une partie à $5$ éléments de l'ensemble des $32$ cartes : il y a $\binom{32}{5} = \frac{32 \times 31 \times 30 \times 29 \times 28}{5!} = 201\,376 \text{ mains.}$

À la calculatrice, $\binom{n}{k}$ s'obtient avec la touche ou le menu « Combinaison » (souvent noté nCr).

Leçon 5 : Valeurs particulières, symétrie, relation de Pascal

Voir la vidéo de la leçon 5

5.1 Valeurs particulières

Pour tout entier $n \geq 0$ (et $n \geq 1$ ou $n \geq 2$ quand il le faut) :

• $\dbinom{n}{0} = 1$ : la seule partie à $0$ élément est l'ensemble vide ;
• $\dbinom{n}{1} = n$ : les parties à un élément sont les $n$ ensembles $\{x\}$ ;
• $\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ : c'est la formule pour $k = 2$ ;
• $\dbinom{n}{n} = 1$ : la seule partie à $n$ éléments est $E$ lui-même.

Exemple 16. Dans un tournoi de handball, $10$ équipes se rencontrent une fois chacune. Un match correspond à une paire d'équipes, c'est-à-dire une partie à $2$ éléments : il y a $\dbinom{10}{2} = \dfrac{10 \times 9}{2} = 45$ matchs.

5.2 Symétrie

Propriété (programme). Pour tous entiers $n$ et $k$ tels que $0 \leq k \leq n$ : $\binom{n}{n-k} = \binom{n}{k}.$

Par le calcul. $\dbinom{n}{n-k} = \dfrac{n!}{\big(n - (n-k)\big)!\,(n-k)!} = \dfrac{n!}{k!\,(n-k)!} = \dbinom{n}{k}$.

Par le dénombrement. Choisir les $k$ éléments que l'on prend, c'est choisir les $n - k$ éléments que l'on laisse. À chaque partie $A$ à $k$ éléments, on associe son complémentaire $\overline{A}$, qui a $n - k$ éléments ; et chaque partie à $n - k$ éléments est obtenue une seule fois, comme complémentaire de son propre complémentaire. Il y a donc autant de parties à $k$ éléments que de parties à $n - k$ éléments.

Exemple 17. $\dbinom{30}{28} = \dbinom{30}{2} = \dfrac{30 \times 29}{2} = 435$ : choisir $28$ élèves sur $30$ revient à choisir les $2$ qui restent.

5.3 La relation de Pascal

Propriété (programme : relation de Pascal). Pour tous entiers $n$ et $k$ tels que $0 \leq k \leq n - 1$ : $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}.$

Par exemple, $\dbinom41 + \dbinom42 = 4 + 6 = 10 = \dbinom52$.

Démonstration par le calcul (programme). On part de la formule avec les factorielles : $\binom{n}{k} + \binom{n}{k+1} = \frac{n!}{k!\,(n-k)!} + \frac{n!}{(k+1)!\,(n-k-1)!}.$ On met les deux fractions au même dénominateur $(k+1)!\,(n-k)!$, en utilisant $(k+1)! = (k+1) \times k!$ et $(n-k)! = (n-k) \times (n-k-1)!$ (valable car $n - k \geq 1$) : $\binom{n}{k} + \binom{n}{k+1} = \frac{n!\,(k+1)}{(k+1)!\,(n-k)!} + \frac{n!\,(n-k)}{(k+1)!\,(n-k)!} = \frac{n!\,\big((k+1) + (n-k)\big)}{(k+1)!\,(n-k)!} = \frac{n!\,(n+1)}{(k+1)!\,(n-k)!}.$ Or $n!\,(n+1) = (n+1)!$ et $n - k = (n+1) - (k+1)$. On reconnaît $\frac{(n+1)!}{(k+1)!\,\big((n+1)-(k+1)\big)!} = \binom{n+1}{k+1}.$

Démonstration par le dénombrement (programme : méthode combinatoire). Soit $F$ un ensemble à $n + 1$ éléments, et $a$ un élément de $F$. On compte les parties de $F$ à $k + 1$ éléments en deux groupes disjoints.

• Celles qui contiennent $a$. En retirant $a$, on obtient une partie à $k$ éléments de $F \setminus \{a\}$, qui a $n$ éléments ; et inversement, en ajoutant $a$ à une telle partie, on retrouve la partie de départ. Il y en a $\dbinom{n}{k}$.
• Celles qui ne contiennent pas $a$. Ce sont les parties à $k + 1$ éléments de $F \setminus \{a\}$. Il y en a $\dbinom{n}{k+1}$.

Par le principe additif, $\dbinom{n+1}{k+1} = \dbinom{n}{k} + \dbinom{n}{k+1}$.

Exemple 18. $F = \{a\,;b\,;c\,;d\,;e\}$. Parmi ses $\dbinom52 = 10$ parties à $2$ éléments, $4$ contiennent $a$ ($\{a\,;b\}$, $\{a\,;c\}$, $\{a\,;d\}$, $\{a\,;e\}$), et $\dbinom42 = 6$ ne le contiennent pas : $4 + 6 = 10$.

Leçon 6 : Triangle de Pascal, mots et chemins

Voir la vidéo de la leçon 6

6.1 Le triangle de Pascal

On range les nombres $\binom{n}{k}$ dans un tableau : la ligne $n$ contient $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Chaque ligne commence et finit par $1$. Grâce à la relation de Pascal, chaque autre nombre est la somme du nombre situé juste au-dessus et de son voisin de gauche.

Par exemple, $\binom73 = \binom62 + \binom63 = 15 + 20 = 35$. Chaque ligne se lit de la même façon dans les deux sens : c'est la symétrie $\binom{n}{n-k} = \binom{n}{k}$.

6.2 Un peu d'histoire

Ce tableau porte le nom de Blaise Pascal, qui lui consacre un traité au XVIIe siècle. Mais des propriétés arithmétiques de ce triangle étaient déjà présentes dans les travaux combinatoires des mathématiques indiennes et chinoises, bien avant lui. La combinatoire est aussi un sujet favori des récréations mathématiques depuis l'Antiquité, et l'est encore chez des arithméticiens du XIXe siècle comme Lucas, Delannoy et Laisant. Aujourd'hui, les « mathématiques discrètes » se développent beaucoup, portées notamment par l'informatique et l'intelligence artificielle.

6.3 Représentation par des mots

Propriété. Le nombre de mots de longueur $n$, écrits avec les lettres $0$ et $1$, qui contiennent exactement $k$ fois la lettre $1$, est $\binom{n}{k}$.

Pourquoi. Un tel mot est connu dès qu'on sait où sont ses $k$ lettres $1$ : c'est une partie à $k$ éléments de l'ensemble des positions $\{1\,;2\,;\ldots\,;n\}$.

Exemple 19. Les mots de longueur $5$ avec exactement deux $1$ sont $11000$, $10100$, $10010$, $10001$, $01100$, $01010$, $01001$, $00110$, $00101$ et $00011$ : il y en a $\dbinom52 = 10$.

De même, dans une succession de $n$ épreuves à deux issues, il y a $\binom{n}{k}$ issues comportant exactement $k$ succès : il suffit de choisir les rangs des succès. Dans l'arbre, ce sont les chemins qui passent exactement $k$ fois par une branche $S$. Pour $n = 3$ et $k = 2$ : $SS\overline{S}$, $S\overline{S}S$ et $\overline{S}SS$, soit $\binom32 = 3$ issues. Le chapitre 11 s'en servira.

6.4 Représentation par des chemins sur un quadrillage

Exemple 20. Dans un quartier dont les rues forment un quadrillage, on va du point $A$ au point $B$, situé $4$ rues plus à droite et $3$ rues plus haut, en allant toujours vers la droite ($D$) ou vers le haut ($H$). Un trajet est un mot de $7$ lettres, avec $4$ lettres $D$ et $3$ lettres $H$, par exemple $DHDDHHD$. Il est connu dès qu'on choisit les $3$ positions des $H$ parmi les $7$ : il y a $\dbinom73 = 35$ trajets.

6.5 Somme des nombres d'une ligne

Propriété (programme). Pour tout entier $n \geq 0$ : $\sum_{k=0}^{n} \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n.$

Le symbole $\displaystyle\sum_{k=0}^{n}$ (« somme pour $k$ allant de $0$ à $n$ ») est une écriture courte de cette somme de $n + 1$ termes.

Démonstration par dénombrement (programme). Soit $E$ un ensemble à $n$ éléments. Chaque partie de $E$ a un nombre d'éléments $k$ compris entre $0$ et $n$.

1. Pour chaque $k$, il y a $\binom{n}{k}$ parties à $k$ éléments.
2. Ces $n + 1$ groupes de parties sont deux à deux disjoints (une partie n'a qu'un seul nombre d'éléments), et ensemble ils contiennent toutes les parties de $E$.
3. Par le principe additif, le nombre de parties de $E$ est $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n}$.
4. Or ce nombre vaut $2^n$ (leçon 2). D'où l'égalité.

Exemple 21. Ligne $4$ : $1 + 4 + 6 + 4 + 1 = 16 = 2^4$. Ligne $7$ : $1 + 7 + 21 + 35 + 35 + 21 + 7 + 1 = 128 = 2^7$.

Conséquence. Un ensemble à $n$ éléments a $2^n - 1$ parties non vides. Par exemple, avec $6$ ingrédients, on compose $2^6 - 1 = 63$ pizzas avec au moins un ingrédient.

Leçon 7 : Algorithmes en Python

Voir la vidéo de la leçon 7

Les programmes ci-dessous utilisent les listes de Python (programme : générer une liste en extension, par ajouts successifs ou en compréhension, la parcourir). En langage naturel, l'affectation s'écrit avec une flèche : « $L \leftarrow [1]$ » se lit « $L$ prend la valeur $[1]$ ».

7.1 Le triangle de Pascal

Une ligne à partir de la précédente. La ligne suivante commence par $1$, contient ensuite les sommes de deux nombres voisins de la ligne $L$, et finit par $1$ : c'est la relation de Pascal.

def ligne_suivante(L):
    M = [1]
    for k in range(1, len(L)):
        M.append(L[k-1] + L[k])
    M.append(1)
    return M

La même fonction s'écrit aussi avec une liste en compréhension : return [1] + [L[k-1] + L[k] for k in range(1, len(L))] + [1].

La ligne $n$. On part de la ligne $0$, qui vaut [1], et on applique $n$ fois la fonction.

def pascal(n):
    L = [1]
    for i in range(n):
        L = ligne_suivante(L)
    return L

>>> pascal(5)
[1, 5, 10, 10, 5, 1]
>>> sum(pascal(10))
1024

La seconde ligne vérifie la propriété de la leçon 6 : $\sum\limits_{k=0}^{10} \binom{10}{k} = 2^{10} = 1\,024$.

7.2 Les parties à 2 ou 3 éléments d'un ensemble

On représente un ensemble par la liste de ses éléments. Pour obtenir chaque partie une seule fois, on impose aux indices d'être rangés dans l'ordre croissant : $i < j$.

E = ['a', 'b', 'c', 'd', 'e']
n = len(E)
P2 = [[E[i], E[j]] for i in range(n) for j in range(i+1, n)]

>>> P2
[['a', 'b'], ['a', 'c'], ['a', 'd'], ['a', 'e'], ['b', 'c'], ['b', 'd'], ['b', 'e'], ['c', 'd'], ['c', 'e'], ['d', 'e']]
>>> len(P2)
10

On retrouve $\binom52 = 10$. Pour les parties à $3$ éléments, on impose $i < j < k$ :

P3 = [[E[i], E[j], E[k]] for i in range(n) for j in range(i+1, n) for k in range(j+1, n)]

len(P3) vaut 10, c'est-à-dire $\binom53$.

7.3 Les permutations d'un ensemble fini

On construit les débuts de permutations étape par étape, comme dans un arbre : à chaque étape, on prolonge chaque liste déjà obtenue par chacun des éléments qu'elle ne contient pas encore.

def permutations(E):
    P = [[]]
    for etape in range(len(E)):
        P = [p + [x] for p in P for x in E if x not in p]
    return P

>>> permutations([1, 2, 3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>>> len(permutations([1, 2, 3, 4, 5]))
120

Avec [1, 2, 3], la liste P vaut [[1], [2], [3]] après la première étape ($3$ choix), puis contient $6$ listes de deux éléments ($3 \times 2$), puis les $6$ permutations ($3 \times 2 \times 1 = 3!$). En faisant seulement $k$ étapes, on obtiendrait les $k$-uplets d'éléments distincts.

7.4 Tirer une permutation au hasard

On tire au hasard un élément parmi ceux qui restent, on le retire de la liste, et on l'ajoute à la permutation, jusqu'à ce qu'il ne reste rien.

from random import randint

def permutation_hasard(E):
    reste = list(E)
    P = []
    while len(reste) > 0:
        i = randint(0, len(reste) - 1)
        P.append(reste.pop(i))
    return P

randint(0, len(reste) - 1) tire un indice au hasard dans la liste reste, et reste.pop(i) retire l'élément d'indice i en le renvoyant. Un appel permutation_hasard([1, 2, 3, 4, 5]) peut renvoyer par exemple [4, 1, 5, 3, 2]. On fait $n$ tirages, puis $n - 1$, et ainsi de suite : chacune des $n!$ permutations peut sortir, avec la même chance.

Leçon 8 : Reconnaître l'objet à dénombrer

Voir la vidéo de la leçon 8

8.1 Deux questions à se poser

Pour choisir $k$ objets parmi $n$, on se demande : l'ordre compte-t-il ? et peut-on reprendre plusieurs fois le même objet ?

Repères de vocabulaire : des tirages « successifs avec remise » donnent des $k$-uplets ; « successifs sans remise », des $k$-uplets d'éléments distincts ; « simultanés », des parties.

8.2 Trois outils pour combiner

• Des cas qui ne se recouvrent pas (« ou ») : on additionne (principe additif).
• Des choix successifs (« puis », « et ») : on multiplie (principe multiplicatif).
• « Au moins un » : on compte souvent le complémentaire (« aucun »), puis on le retire du total.

Pour ne rien oublier ni compter deux fois, on s'aide d'une représentation : diagramme, tableau, arbre.

8.3 Exemples

Exemple 22 (un digicode). Un digicode demande une lettre parmi $A$, $B$, $C$, puis trois chiffres. L'ordre compte et les chiffres peuvent se répéter : $3 \times 10^3 = 3\,000$ codes. Si les trois chiffres doivent être différents : $3 \times 10 \times 9 \times 8 = 2\,160$ codes.

Exemple 23 (une équipe). Un club compte $10$ filles et $8$ garçons. On forme une équipe de $4$ joueurs, sans poste particulier.

• Nombre d'équipes. L'ordre ne compte pas : une équipe est une partie à $4$ éléments des $18$ membres. Il y en a $\dbinom{18}{4} = 3\,060$.
• Exactement deux filles et deux garçons. On choisit les filles, puis les garçons : $\dbinom{10}{2} \times \dbinom{8}{2} = 45 \times 28 = 1\,260$ équipes.
• Au moins un garçon. Le contraire est « aucun garçon », c'est-à-dire quatre filles : $\dbinom{10}{4} = 210$ équipes. Il reste $3\,060 - 210 = 2\,850$ équipes avec au moins un garçon.
• Une probabilité. Si l'équipe est tirée au sort, toutes les équipes ont la même probabilité. La probabilité d'obtenir deux filles et deux garçons est $\dfrac{1\,260}{3\,060} = \dfrac{7}{17} \approx 0{,}41$.

Exemple 24 (des mots avec des lettres répétées). Combien de mots différents peut-on écrire avec les six lettres du mot ANANAS ? On choisit les $3$ positions des $A$ parmi les $6$ : $\dbinom63 = 20$ choix ; puis les $2$ positions des $N$ parmi les $3$ qui restent : $\dbinom32 = 3$ choix ; le $S$ prend la dernière place. Il y a $20 \times 3 = 60$ mots. Attention : ce n'est pas $6! = 720$, car échanger deux $A$ ne change pas le mot.

Ce qu'il faut retenir du chapitre

1. Principe additif : si $A$ et $B$ sont disjoints, $\mathrm{Card}(A \cup B) = \mathrm{Card}(A) + \mathrm{Card}(B)$. En particulier, $\mathrm{Card}(\overline{A}) = \mathrm{Card}(E) - \mathrm{Card}(A)$.
2. Principe multiplicatif : $\mathrm{Card}(E \times F) = \mathrm{Card}(E) \times \mathrm{Card}(F)$ ; pour des choix successifs, on multiplie les nombres de possibilités.
3. Un ensemble à $n$ éléments a $n^k$ $k$-uplets (ordre, répétitions permises) et $2^n$ parties (codées par les $n$-uplets de $\{0\,;1\}$).
4. Il a $n(n-1)\cdots(n-k+1) = \dfrac{n!}{(n-k)!}$ $k$-uplets d'éléments distincts, et $n!$ permutations. Par convention, $0! = 1$.
5. Une combinaison de $k$ éléments est une partie à $k$ éléments : $\dbinom{n}{k} = \dfrac{n(n-1)\cdots(n-k+1)}{k!} = \dfrac{n!}{(n-k)!\,k!}$.
6. $\dbinom{n}{0} = \dbinom{n}{n} = 1$, $\dbinom{n}{1} = n$, $\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ ; symétrie $\dbinom{n}{n-k} = \dbinom{n}{k}$ ; relation de Pascal $\dbinom{n}{k} + \dbinom{n}{k+1} = \dbinom{n+1}{k+1}$, démontrée par le calcul et par le dénombrement.
7. $\dbinom{n}{k}$ compte aussi les mots de longueur $n$ à $k$ lettres $1$, et les chemins à $k$ succès dans un arbre ; la somme d'une ligne du triangle de Pascal vaut $2^n$ (démontré par dénombrement).
8. Pour dénombrer, on se demande si l'ordre compte et si les répétitions sont permises ; on additionne des cas disjoints, on multiplie des choix successifs, et on passe au complémentaire pour « au moins un ».