Dénombrement
Ce chapitre fait partie du programme de Prépa, 1re année.
Dénombrer, c'est compter les éléments d'un ensemble fini sans les énumérer un par un, en le découpant, en le mettant en bijection avec un ensemble connu ou en le comptant de deux façons. Ces techniques servent en probabilités, en algèbre (formule du binôme, polynômes) et en informatique (complexité, structures de données).
Prérequis
- Ensembles, parties, complémentaire, réunion, intersection, produit cartésien
- Applications : injection, surjection, bijection, composition, réciproque, image directe
- Raisonnement par récurrence — Revoir Raisonnement par récurrence
- Factorielle et coefficients binomiaux définis par $\binom{n}{k}=\frac{n!}{k!(n-k)!}$, formule de Pascal et formule du binôme vues dans le chapitre de calcul
- Fonction indicatrice d'une partie
À la fin du chapitre, on sait
- Connaître la définition du cardinal et les propriétés des parties et des images d'un ensemble fini
- Savoir qu'entre deux ensembles finis de même cardinal, injective, surjective et bijective sont équivalentes
- Calculer le cardinal d'une réunion, d'un complémentaire, d'un produit cartésien
- Dénombrer les applications, les parties, les $p$-listes d'éléments distincts, les injections, les permutations
- Dénombrer les parties à $k$ éléments et interpréter $\binom{n}{k}$
- Rédiger une preuve combinatoire : bijection, découpage en cas disjoints, double comptage
- Choisir le bon modèle (ordre ou non, répétition ou non) dans une situation concrète
1.Ensembles finis et cardinal
Ensemble fini, cardinal
Un ensemble $E$ est fini s'il est vide ou s'il existe $n\in\mathbb{N}^*$ et une bijection de $\llbracket 1,n\rrbracket$ sur $E$.
L'entier $n$ est alors unique (résultat admis) : on l'appelle le cardinal de $E$, noté $\operatorname{Card} E$, $|E|$ ou $\#E$. Par convention $\operatorname{Card}\varnothing=0$.
Numéroter les éléments de $E$ sous la forme $x_1,\dots,x_n$ revient exactement à se donner une telle bijection $k\mapsto x_k$.
Invariance par bijection
Si $E$ est fini et s'il existe une bijection de $E$ sur $F$, alors $F$ est fini et $\operatorname{Card} F=\operatorname{Card} E$.
En effet, si $\varphi:\llbracket 1,n\rrbracket\to E$ et $f:E\to F$ sont bijectives, $f\circ\varphi:\llbracket 1,n\rrbracket\to F$ est bijective.
C'est l'outil de base : pour compter $F$, on le met en bijection avec un ensemble dont on connaît le cardinal.
Cardinal d'un intervalle d'entiers
Pour $a\le b$ entiers, l'application $k\mapsto k-a+1$ est une bijection de $\llbracket a,b\rrbracket$ sur $\llbracket 1,b-a+1\rrbracket$. Donc $$\operatorname{Card}\llbracket a,b\rrbracket=b-a+1.$$ Par exemple $\llbracket 10,25\rrbracket$ contient $16$ entiers, et non $15$.
Les multiples de $7$ dans $\llbracket 1,100\rrbracket$ sont les $7k$ avec $1\le 7k\le 100$, soit $k\in\llbracket 1,14\rrbracket$ : il y en a $14$ (l'application $k\mapsto 7k$ est une bijection).
Parties d'un ensemble fini
Soit $E$ un ensemble fini et $A\subset E$. Alors $A$ est fini et $$\operatorname{Card} A\le\operatorname{Card} E,$$ avec égalité si et seulement si $A=E$.
Ce résultat est admis. Le cas d'égalité sert souvent à prouver une égalité d'ensembles : si $A\subset E$ et $\operatorname{Card}A=\operatorname{Card}E$, alors $A=E$.
Image d'un ensemble fini
Soit $f:E\to F$ avec $E$ fini. Alors $f(E)$ est fini et $$\operatorname{Card} f(E)\le\operatorname{Card} E,$$ avec égalité si et seulement si $f$ est injective.
Conséquences :
- si $f:E\to F$ est injective et $F$ fini, alors $\operatorname{Card}E\le\operatorname{Card}F$ ;
- si $f:E\to F$ est surjective et $E$ fini, alors $\operatorname{Card}F\le\operatorname{Card}E$.
Si $f$ est injective, elle induit une bijection de $E$ sur $f(E)$, d'où l'égalité. La réciproque est admise.
Principe des tiroirs
Par contraposée : si $\operatorname{Card}E>\operatorname{Card}F$, aucune application de $E$ dans $F$ n'est injective. Deux éléments distincts de $E$ ont donc la même image.
Exemple : parmi $13$ personnes, l'application « mois de naissance » va d'un ensemble à $13$ éléments dans un ensemble à $12$ éléments ; elle n'est pas injective, donc deux personnes au moins sont nées le même mois.
Applications entre ensembles de même cardinal
Soient $E$ et $F$ deux ensembles finis de même cardinal et $f:E\to F$. Les assertions suivantes sont équivalentes :
- $f$ est injective ;
- $f$ est surjective ;
- $f$ est bijective.
Preuve
Notons $n=\operatorname{Card}E=\operatorname{Card}F$. Il suffit de montrer que 1 implique 3 et que 2 implique 3, les autres implications étant immédiates.
Injective implique bijective. Si $f$ est injective, $\operatorname{Card}f(E)=\operatorname{Card}E=n=\operatorname{Card}F$. Comme $f(E)\subset F$, le cas d'égalité des parties donne $f(E)=F$ : $f$ est surjective, donc bijective.
Surjective implique bijective. Si $f$ est surjective, on choisit pour chaque $y\in F$ un antécédent $g(y)\in E$. On définit ainsi $g:F\to E$ avec $f\circ g=\mathrm{id}_F$. L'application $g$ est injective : si $g(y)=g(y')$, alors $y=f(g(y))=f(g(y'))=y'$. D'après le point précédent (appliqué de $F$ dans $E$, qui ont même cardinal), $g$ est bijective. Alors $f=f\circ g\circ g^{-1}=g^{-1}$ est bijective.
Hypothèses indispensables
Le théorème est faux pour des ensembles infinis : $n\mapsto n+1$ est injective de $\mathbb{N}$ dans $\mathbb{N}$ sans être surjective.
Il est faux aussi si les cardinaux diffèrent : $x\mapsto x$ de $\{1,2\}$ dans $\{1,2,3\}$ est injective, pas surjective. Avant d'invoquer ce théorème, on vérifie toujours : ensembles finis, même cardinal.
Prouver qu'une application est bijective en dimension finie
Pour montrer que $f:E\to F$ est bijective avec $E$, $F$ finis :
- on vérifie que $\operatorname{Card}E=\operatorname{Card}F$ ;
- on démontre seulement l'injectivité (souvent la plus facile : $f(x)=f(x')\Rightarrow x=x'$), ou seulement la surjectivité ;
- on conclut par le théorème.
Exemple : $p$ premier, $a\in\llbracket 1,p-1\rrbracket$. L'application $x\mapsto$ reste de $ax$ modulo $p$ va de $\llbracket 1,p-1\rrbracket$ dans lui-même (car $p\nmid ax$). Elle est injective : si $ax\equiv ax'\ [p]$, alors $p\mid a(x-x')$, donc $p\mid x-x'$ par le lemme d'Euclide, et $|x-x'|<p$ impose $x=x'$. Elle est donc bijective.
2.Réunion, complémentaire, produit cartésien
Réunion disjointe
Si $A_1,\dots,A_m$ sont des parties finies deux à deux disjointes, alors $$\operatorname{Card}\Big(\bigcup_{i=1}^m A_i\Big)=\sum_{i=1}^m\operatorname{Card}A_i.$$ On l'appelle le principe additif. Le cas $m=2$ s'obtient en recollant une numérotation de $A_1$ (indices $1$ à $a$) et une de $A_2$ (indices $a+1$ à $a+b$) ; le cas général suit par récurrence sur $m$.
Complémentaire, différence
Si $E$ est fini et $A\subset E$ : $$\operatorname{Card}(E\setminus A)=\operatorname{Card}E-\operatorname{Card}A.$$ Plus généralement, pour $A,B$ finis, $\operatorname{Card}(B\setminus A)=\operatorname{Card}B-\operatorname{Card}(A\cap B)$.
Preuve : $E=A\cup(E\setminus A)$ est une réunion disjointe, et $B=(B\setminus A)\cup(A\cap B)$ aussi.
Réunion de deux ensembles finis
Pour $A$ et $B$ finis : $$\operatorname{Card}(A\cup B)=\operatorname{Card}A+\operatorname{Card}B-\operatorname{Card}(A\cap B).$$
Preuve
On écrit $A\cup B=A\cup(B\setminus A)$, réunion disjointe. Donc $$\operatorname{Card}(A\cup B)=\operatorname{Card}A+\operatorname{Card}(B\setminus A)=\operatorname{Card}A+\operatorname{Card}B-\operatorname{Card}(A\cap B),$$ en utilisant la propriété précédente pour $\operatorname{Card}(B\setminus A)$.
Entiers divisibles par 2 ou par 3
Dans $E=\llbracket 1,100\rrbracket$, soit $A$ l'ensemble des multiples de $2$ et $B$ celui des multiples de $3$.
- $\operatorname{Card}A=50$ ;
- $\operatorname{Card}B=33$ (car $3\times 33=99\le 100<102$) ;
- $A\cap B$ est l'ensemble des multiples de $6$ : $\operatorname{Card}(A\cap B)=16$ (car $6\times16=96$).
Donc $\operatorname{Card}(A\cup B)=50+33-16=67$. Il y a $100-67=33$ entiers de $E$ divisibles ni par $2$ ni par $3$.
Formule du crible (hors programme)
Pour trois ensembles finis : $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.$$ La formule générale de Poincaré pour $m$ ensembles est hors programme ; elle se redémontre si un énoncé la demande (par récurrence ou avec les fonctions indicatrices).
Produit cartésien
Si $E$ et $F$ sont finis : $$\operatorname{Card}(E\times F)=\operatorname{Card}E\times\operatorname{Card}F.$$ Par récurrence, $\operatorname{Card}(E_1\times\cdots\times E_m)=\prod_{i=1}^m\operatorname{Card}E_i$ et $\operatorname{Card}(E^m)=(\operatorname{Card}E)^m$.
Preuve
Notons $n=\operatorname{Card}E$ et $p=\operatorname{Card}F$. On écrit $$E\times F=\bigcup_{x\in E}\{x\}\times F.$$ Ces $n$ parties sont deux à deux disjointes (la première coordonnée diffère). Chacune est en bijection avec $F$ via $(x,y)\mapsto y$, donc a $p$ éléments. Le principe additif donne $\operatorname{Card}(E\times F)=\sum_{x\in E}p=np$.
Lemme des bergers
Soit $f:E\to F$ une application surjective entre ensembles finis telle que chaque élément de $F$ ait exactement $k$ antécédents. Alors $$\operatorname{Card}E=k\,\operatorname{Card}F.$$ Preuve : $E=\bigcup_{y\in F}f^{-1}(\{y\})$, réunion disjointe de $\operatorname{Card}F$ parties à $k$ éléments.
Le nom vient de l'image du berger qui compte les pattes et divise par $4$. On s'en sert surtout pour diviser : si chaque objet a été compté $k$ fois, on divise par $k$.
Principe additif, principe multiplicatif
- Additif : si les objets à compter se répartissent en cas disjoints qui recouvrent tout, on compte chaque cas et on additionne.
- Multiplicatif : si un objet se construit par une suite de choix successifs et que le nombre d'options à chaque étape ne dépend pas des choix précédents (même si les options elles-mêmes en dépendent), on multiplie ces nombres.
La rédaction doit expliciter le découpage ou la suite de choix, puis vérifier que chaque objet est obtenu exactement une fois.
Codes et mots
- Un code à $4$ chiffres est un élément de $\llbracket 0,9\rrbracket^4$ : il y en a $10^4=10\,000$.
- Un mot de passe formé de $2$ lettres majuscules suivies de $3$ chiffres : $26^2\times10^3=676\,000$.
- Codes à $4$ chiffres contenant au moins un $0$ : on passe au complémentaire. Il y a $9^4=6561$ codes sans $0$, donc $10\,000-6561=3439$ codes avec au moins un $0$.
3.Applications, listes, injections, permutations
$p$-listes
Soit $F$ un ensemble et $p\in\mathbb{N}^*$. Une $p$-liste (ou $p$-uplet) d'éléments de $F$ est un élément $(y_1,\dots,y_p)$ de $F^p$. L'ordre compte et les répétitions sont permises.
Une $p$-liste d'éléments distincts est une $p$-liste où $y_i\ne y_j$ pour $i\ne j$.
Nombre d'applications
Si $E$ et $F$ sont finis, l'ensemble $F^E$ des applications de $E$ dans $F$ est fini et $$\operatorname{Card}(F^E)=(\operatorname{Card}F)^{\operatorname{Card}E}.$$
Preuve
Notons $n=\operatorname{Card}E$, $p=\operatorname{Card}F$, et numérotons $E=\{x_1,\dots,x_n\}$. L'application $$\Phi:F^E\to F^n,\quad f\mapsto\big(f(x_1),\dots,f(x_n)\big)$$ est bijective : une application est entièrement déterminée par ses valeurs, et toute $n$-liste $(y_1,\dots,y_n)$ est l'image de l'unique $f$ telle que $f(x_i)=y_i$. Donc $\operatorname{Card}(F^E)=\operatorname{Card}(F^n)=p^n$.
Si $E=\varnothing$, il existe une seule application (l'application vide), et $p^0=1$ : la formule reste vraie.
Ordre des exposants
Le cardinal de l'ensemble d'arrivée est à la base, celui de départ est à l'exposant. Pour chaque élément de départ, on choisit une image parmi les éléments d'arrivée.
Exemple : il y a $3^5=243$ applications d'un ensemble à $5$ éléments dans un ensemble à $3$ éléments, et $5^3=125$ dans l'autre sens.
Nombre de parties
Si $E$ est fini de cardinal $n$, l'ensemble $\mathcal{P}(E)$ de ses parties est fini et $$\operatorname{Card}\mathcal{P}(E)=2^n.$$
Preuve
L'application $A\mapsto\mathbf{1}_A$ est une bijection de $\mathcal{P}(E)$ sur $\{0,1\}^E$ : une partie est déterminée par son indicatrice, et toute $g:E\to\{0,1\}$ est l'indicatrice de $A=g^{-1}(\{1\})$. Donc $\operatorname{Card}\mathcal{P}(E)=\operatorname{Card}\{0,1\}^E=2^n$.
Concrètement : pour chacun des $n$ éléments, on décide s'il est dans la partie ou non, soit $2$ choix à chaque fois.
Nombre de $p$-listes d'éléments distincts
Soit $F$ de cardinal $n$ et $p\in\mathbb{N}^*$. Le nombre de $p$-listes d'éléments distincts de $F$ vaut $$n(n-1)\cdots(n-p+1)=\frac{n!}{(n-p)!}\quad\text{si }p\le n,$$ et $0$ si $p>n$.
Preuve
Notons $L_p$ l'ensemble de ces listes. Si $p>n$, $L_p=\varnothing$ par le principe des tiroirs. Supposons $p\le n$ et raisonnons par récurrence sur $p$.
Pour $p=1$ : $L_1$ est en bijection avec $F$, donc $\operatorname{Card}L_1=n$.
Soit $p<n$ tel que $\operatorname{Card}L_p=\frac{n!}{(n-p)!}$. L'application $$\pi:L_{p+1}\to L_p,\quad(y_1,\dots,y_{p+1})\mapsto(y_1,\dots,y_p)$$ est surjective, et chaque $(y_1,\dots,y_p)\in L_p$ a exactement $n-p$ antécédents : $y_{p+1}$ est un élément quelconque de $F\setminus\{y_1,\dots,y_p\}$, qui a $n-p$ éléments. Le lemme des bergers donne $$\operatorname{Card}L_{p+1}=(n-p)\frac{n!}{(n-p)!}=\frac{n!}{(n-p-1)!}.$$ Cela conclut la récurrence.
Injections et permutations
Soient $E$ de cardinal $p$ et $F$ de cardinal $n$.
- Le nombre d'injections de $E$ dans $F$ vaut $\frac{n!}{(n-p)!}$ si $p\le n$, et $0$ si $p>n$.
- Le nombre de bijections de $E$ sur $F$ vaut $n!$ si $p=n$.
- En particulier, le groupe symétrique $\mathfrak{S}_n$ des permutations de $\llbracket1,n\rrbracket$ a $n!$ éléments.
Preuve : avec $E=\{x_1,\dots,x_p\}$, la bijection $f\mapsto(f(x_1),\dots,f(x_p))$ envoie les injections exactement sur les $p$-listes d'éléments distincts. Pour $p=n$, une injection est une bijection (même cardinal), et $\frac{n!}{0!}=n!$.
Applications chiffrées
- Tiercé dans l'ordre avec $16$ chevaux : $16\times15\times14=3360$ arrivées possibles (3-listes d'éléments distincts).
- Codes à $4$ chiffres tous distincts : $10\times9\times8\times7=5040$.
- Injections de $\llbracket1,3\rrbracket$ dans $\llbracket1,5\rrbracket$ : $5\times4\times3=60$, parmi les $5^3=125$ applications.
- Surjections de $\llbracket1,3\rrbracket$ sur $\{a,b\}$ : parmi les $2^3=8$ applications, seules les $2$ applications constantes ne sont pas surjectives, d'où $6$ surjections.
- Façons d'asseoir $6$ personnes sur $6$ chaises numérotées : $6!=720$.
Notation $A_n^p$
Le nombre $\frac{n!}{(n-p)!}$ est parfois noté $A_n^p$ (nombre d'arrangements). Cette notation n'est pas celle du programme : on peut l'utiliser à condition de la définir dans la copie.
4.Parties à k éléments et coefficients binomiaux
Parties à $k$ éléments
Soit $E$ un ensemble fini et $k\in\mathbb{N}$. On note $\mathcal{P}_k(E)$ l'ensemble des parties de $E$ ayant exactement $k$ éléments. On les appelle aussi $k$-combinaisons de $E$ : l'ordre ne compte pas, il n'y a pas de répétition.
Rappel : pour $0\le k\le n$, $\binom{n}{k}=\frac{n!}{k!(n-k)!}$, et $\binom{n}{k}=0$ si $k>n$.
Interprétation combinatoire de $\binom{n}{k}$
Si $\operatorname{Card}E=n$, alors pour tout $k\in\mathbb{N}$ : $$\operatorname{Card}\mathcal{P}_k(E)=\binom{n}{k}.$$ $\binom{n}{k}$ se lit « $k$ parmi $n$ ».
Preuve
Si $k>n$, aucune partie de $E$ n'a $k$ éléments, et $\binom{n}{k}=0$. Si $k=0$, seule $\varnothing$ convient, et $\binom{n}{0}=1$.
Soit $1\le k\le n$ et $L_k$ l'ensemble des $k$-listes d'éléments distincts de $E$. L'application $$\sigma:L_k\to\mathcal{P}_k(E),\quad(y_1,\dots,y_k)\mapsto\{y_1,\dots,y_k\}$$ est bien à valeurs dans $\mathcal{P}_k(E)$ car les $y_i$ sont distincts. Elle est surjective. Une partie $A\in\mathcal{P}_k(E)$ a pour antécédents toutes les façons d'ordonner ses éléments, c'est-à-dire les bijections de $\llbracket1,k\rrbracket$ sur $A$ : il y en a $k!$.
Le lemme des bergers donne $\operatorname{Card}L_k=k!\operatorname{Card}\mathcal{P}_k(E)$, d'où $$\operatorname{Card}\mathcal{P}_k(E)=\frac{1}{k!}\cdot\frac{n!}{(n-k)!}=\binom{n}{k}.$$
Mains de cartes
Un jeu de $32$ cartes contient $4$ as. Une main est une partie à $5$ cartes.
- Nombre de mains : $\binom{32}{5}=\frac{32\times31\times30\times29\times28}{120}=201\,376$.
- Mains avec exactement $2$ as : on choisit les $2$ as parmi $4$, puis les $3$ autres cartes parmi les $28$ qui ne sont pas des as : $\binom{4}{2}\binom{28}{3}=6\times3276=19\,656$.
- Mains avec au moins un as : complémentaire des mains sans as, $\binom{32}{5}-\binom{28}{5}=201\,376-98\,280=103\,096$.
« Exactement », « au moins », « au plus »
- Exactement $j$ objets d'un type : on choisit les $j$ objets dans ce type, puis les autres hors de ce type, et on multiplie.
- Au moins un : on compte le complémentaire (« aucun ») et on soustrait du total.
- Au moins $j$ ou au plus $j$ : on somme les cas « exactement $i$ » (cas disjoints), ou on passe au complémentaire si c'est plus court.
On évite de « choisir d'abord un objet du type voulu puis le reste librement » : chaque configuration serait comptée plusieurs fois.
Symétrie
Pour $0\le k\le n$ : $\binom{n}{k}=\binom{n}{n-k}$.
Preuve combinatoire : l'application $A\mapsto E\setminus A$ est une bijection de $\mathcal{P}_k(E)$ sur $\mathcal{P}_{n-k}(E)$ (elle est sa propre réciproque). Choisir les $k$ éléments retenus revient à choisir les $n-k$ éléments exclus.
Formule de Pascal
Pour $n\ge1$ et $1\le k\le n$ : $$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}.$$
Preuve combinatoire
Soit $E$ de cardinal $n\ge1$ et $a\in E$ fixé. On partage $\mathcal{P}_k(E)$ en deux parties disjointes :
- les parties contenant $a$ : $A\mapsto A\setminus\{a\}$ est une bijection vers $\mathcal{P}_{k-1}(E\setminus\{a\})$, de cardinal $\binom{n-1}{k-1}$ ;
- les parties ne contenant pas $a$ : ce sont exactement les éléments de $\mathcal{P}_k(E\setminus\{a\})$, de cardinal $\binom{n-1}{k}$ (nul si $k=n$).
Le principe additif donne la formule.
Formule du binôme
Soient $a,b$ deux éléments d'un anneau qui commutent ($ab=ba$), par exemple deux complexes. Pour $n\in\mathbb{N}$ : $$(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k}.$$
Preuve combinatoire
On écrit $(a+b)^n=(a+b)(a+b)\cdots(a+b)$ avec $n$ facteurs numérotés de $1$ à $n$. Développer par distributivité revient à choisir, dans chaque facteur, soit $a$, soit $b$, et à sommer tous les produits obtenus. Un tel choix est déterminé par la partie $K\subset\llbracket1,n\rrbracket$ des facteurs où l'on prend $a$. Comme $a$ et $b$ commutent, le produit correspondant vaut $a^{\operatorname{Card}K}b^{n-\operatorname{Card}K}$. Donc $$(a+b)^n=\sum_{K\subset\llbracket1,n\rrbracket}a^{\operatorname{Card}K}b^{n-\operatorname{Card}K}=\sum_{k=0}^n\operatorname{Card}\mathcal{P}_k(\llbracket1,n\rrbracket)\,a^kb^{n-k},$$ en regroupant les parties selon leur cardinal $k$. On conclut avec $\operatorname{Card}\mathcal{P}_k(\llbracket1,n\rrbracket)=\binom{n}{k}$.
Sommes classiques
Pour $n\in\mathbb{N}$ : $$\sum_{k=0}^n\binom{n}{k}=2^n.$$ Preuve combinatoire : $\mathcal{P}(E)$ est la réunion disjointe des $\mathcal{P}_k(E)$ pour $0\le k\le n$.
Pour $n\ge1$, le binôme avec $a=-1$, $b=1$ donne $\sum_{k=0}^n(-1)^k\binom{n}{k}=0$ : un ensemble non vide a autant de parties de cardinal pair que de cardinal impair, soit $2^{n-1}$ de chaque.
Chemins dans un quadrillage
On va de $(0,0)$ à $(p,q)$ par pas élémentaires $(1,0)$ (droite) ou $(0,1)$ (haut). Un chemin compte $p+q$ pas, dont $p$ vers la droite. Il est déterminé par l'ensemble des numéros des pas vers la droite, partie à $p$ éléments de $\llbracket1,p+q\rrbracket$. Il y a donc $\binom{p+q}{p}$ chemins.
Pour $(3,2)$ : $\binom{5}{3}=10$ chemins.
Autre exemple : un polygone convexe à $n$ sommets a $\binom{n}{2}-n=\frac{n(n-3)}{2}$ diagonales (segments joignant deux sommets, moins les $n$ côtés). Pour $n=10$ : $45-10=35$.
5.Preuves combinatoires
Rédiger une preuve combinatoire
Pour démontrer une identité entre entiers par le dénombrement :
- Choisir un ensemble $X$ dont l'un des membres est visiblement le cardinal (comités, parties, chemins, couples...).
- Le compter d'une seconde façon : par découpage en cas disjoints (on obtient une somme), par choix successifs (un produit), ou par une bijection avec un ensemble connu.
- Conclure : les deux expressions sont égales car elles valent $\operatorname{Card}X$.
On appelle double comptage cette démarche. La rédaction précise toujours l'ensemble compté et justifie que le découpage est disjoint et exhaustif.
Comité avec président
Montrons que, pour $1\le k\le n$ : $k\binom{n}{k}=n\binom{n-1}{k-1}$.
Soit $E$ un ensemble de $n$ personnes. On compte l'ensemble $X$ des couples $(A,x)$ où $A\in\mathcal{P}_k(E)$ est un comité et $x\in A$ son président.
- On choisit d'abord le comité ($\binom{n}{k}$ façons), puis le président parmi ses $k$ membres : $\operatorname{Card}X=k\binom{n}{k}$.
- On choisit d'abord le président ($n$ façons), puis les $k-1$ autres membres parmi les $n-1$ personnes restantes : $\operatorname{Card}X=n\binom{n-1}{k-1}$.
D'où l'égalité. Contrôle : $n=5$, $k=2$ donne $2\times10=5\times4$.
Somme des $k\binom{n}{k}$
Montrons que, pour $n\ge1$ : $\sum_{k=0}^nk\binom{n}{k}=n2^{n-1}$.
Soit $E$ de cardinal $n$ et $X=\{(A,x)\mid A\subset E,\ x\in A\}$.
- En regroupant selon le cardinal $k$ de $A$ : il y a $\binom{n}{k}$ parties à $k$ éléments, et $k$ choix de $x$ pour chacune, soit $\operatorname{Card}X=\sum_{k=0}^nk\binom{n}{k}$.
- En choisissant d'abord $x$ ($n$ choix), puis $A=\{x\}\cup B$ avec $B\subset E\setminus\{x\}$ quelconque ($2^{n-1}$ choix) : $\operatorname{Card}X=n2^{n-1}$.
Contrôle : $n=3$ donne $0+3+6+3=12=3\times4$.
Formule de Vandermonde
Pour $p,q,n\in\mathbb{N}$ : $$\sum_{k=0}^n\binom{p}{k}\binom{q}{n-k}=\binom{p+q}{n}.$$ Cette formule n'est pas explicitement au programme, mais elle est classique et sa preuve est exigible dans l'esprit du chapitre.
Preuve combinatoire
Soit $E=A\cup B$ avec $A$, $B$ disjoints, $\operatorname{Card}A=p$, $\operatorname{Card}B=q$. Alors $\operatorname{Card}E=p+q$ et $\operatorname{Card}\mathcal{P}_n(E)=\binom{p+q}{n}$.
On partage $\mathcal{P}_n(E)$ selon $k=\operatorname{Card}(X\cap A)\in\llbracket0,n\rrbracket$. Une partie $X$ avec $\operatorname{Card}(X\cap A)=k$ est déterminée par le couple $(X\cap A,X\cap B)\in\mathcal{P}_k(A)\times\mathcal{P}_{n-k}(B)$, et tout tel couple convient (sa réunion a $n$ éléments). Il y a donc $\binom{p}{k}\binom{q}{n-k}$ telles parties. Le principe additif donne la formule (les termes avec $k>p$ ou $n-k>q$ sont nuls, ce qui est cohérent).
Somme des carrés
Avec $p=q=n$ dans Vandermonde et la symétrie $\binom{n}{n-k}=\binom{n}{k}$ : $$\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}.$$ Contrôle : $n=3$ donne $1+9+9+1=20=\binom{6}{3}$.
Partage selon le plus grand élément
Montrons que, pour $0\le k\le n$ : $\sum_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}$.
On compte les parties à $k+1$ éléments de $\llbracket1,n+1\rrbracket$ selon leur plus grand élément $m$. On a $m\in\llbracket k+1,n+1\rrbracket$, et les $k$ autres éléments forment une partie quelconque à $k$ éléments de $\llbracket1,m-1\rrbracket$ : $\binom{m-1}{k}$ choix. Avec $j=m-1\in\llbracket k,n\rrbracket$, le principe additif donne la formule.
Contrôle : $k=1$, $n=4$ donne $1+2+3+4=10=\binom{5}{2}$.
Anagrammes
Combien de mots (suites de lettres) s'écrivent avec les lettres de ANANAS ? Il y a $6$ positions, avec $3$ A, $2$ N et $1$ S.
Par choix successifs : on choisit les positions des A ($\binom{6}{3}=20$), puis celles des N parmi les $3$ restantes ($\binom{3}{2}=3$), le S occupe la dernière : $20\times3=60$.
Par le lemme des bergers : les $6!=720$ ordonnements de six jetons distincts $A_1,A_2,A_3,N_1,N_2,S$ donnent chaque mot exactement $3!\times2!=12$ fois (permutations des A entre eux et des N entre eux). D'où $720/12=60$.
Solutions entières d'une équation
Combien de triplets $(x_1,x_2,x_3)\in\mathbb{N}^3$ vérifient $x_1+x_2+x_3=4$ ?
On associe à un triplet le mot formé de $x_1$ étoiles, une barre, $x_2$ étoiles, une barre, $x_3$ étoiles. Par exemple $(1,0,3)\mapsto\star|\,|\star\star\star$. C'est une bijection vers les mots de longueur $6$ contenant $4$ étoiles et $2$ barres, déterminés par la position des barres : $\binom{6}{2}=15$ solutions.
Plus généralement, le nombre de solutions de $x_1+\cdots+x_k=n$ dans $\mathbb{N}^k$ vaut $\binom{n+k-1}{k-1}$. Ce résultat n'est pas au programme : il se redémontre par cette bijection.
6.Modéliser une situation de dénombrement
On choisit $p$ objets dans un ensemble à $n$ éléments. Deux questions déterminent le modèle : l'ordre compte-t-il ? les répétitions sont-elles possibles ?
| ordre compte | ordre ne compte pas | |
|---|---|---|
| répétitions possibles | $p$-listes : $n^p$ | $\binom{n+p-1}{p}$ (hors programme) |
| sans répétition | $p$-listes d'éléments distincts : $\frac{n!}{(n-p)!}$ | parties à $p$ éléments : $\binom{n}{p}$ |
Passage d'une colonne à l'autre sans répétition : chaque partie à $p$ éléments correspond à $p!$ listes ordonnées, d'où $\frac{n!}{(n-p)!}=p!\binom{n}{p}$.
Démarche de modélisation
- Décrire précisément un résultat : qu'est-ce qui distingue deux issues ? (« une main de 5 cartes », « un podium ordonné »).
- Choisir l'ensemble modèle : listes, listes d'éléments distincts, parties, applications, produit cartésien.
- Vérifier la correspondance : chaque issue est représentée une et une seule fois. Sinon, corriger par le lemme des bergers (diviser par le nombre de répétitions) ou découper en cas disjoints.
- Calculer, puis contrôler sur un petit cas ou par un second comptage.
Urne : trois façons de tirer
Une urne contient $10$ boules numérotées : $4$ rouges et $6$ blanches. On tire $3$ boules.
Tirage simultané (parties à $3$ éléments) : $\binom{10}{3}=120$ tirages. Exactement $2$ rouges : $\binom{4}{2}\binom{6}{1}=36$.
Tirages successifs sans remise ($3$-listes d'éléments distincts) : $10\times9\times8=720$ tirages. Exactement $2$ rouges : on choisit les rangs des rouges ($\binom{3}{2}=3$), puis les boules dans l'ordre : $3\times4\times3\times6=216$.
Tirages successifs avec remise ($3$-listes) : $10^3=1000$ tirages. Exactement $2$ rouges : $3\times4^2\times6=288$.
Les proportions $\frac{36}{120}$ et $\frac{216}{720}$ valent toutes deux $0{,}3$ : sans remise, tenir compte de l'ordre ne change pas les proportions, à condition de le faire partout.
Cohérence du modèle
Dans un même calcul, on garde un seul modèle. Compter le total en parties et les cas favorables en listes (ou l'inverse) donne un résultat faux d'un facteur $p!$.
De même, « choisir $3$ délégués » (parties) et « choisir un président, un trésorier, un secrétaire » (listes d'éléments distincts) ne sont pas la même question : $\binom{10}{3}=120$ contre $10\times9\times8=720$.