Dénombrement
Dans ce chapitre, on cherche à apprendre à dénombrer un ensemble, c’est-à-dire à compter son nombre d’éléments. On se concentre sur les méthodes de dénombrement et on omet, conformément au programme de MPSI, la plupart des démonstrations.
I) Cardinal d'un ensemble fini
Soit $E$ un ensemble.
- Ensemble fini/infini : On dit que $E$ est $\Emph{fini}$ s'il existe une bijection de $\Intn{1}{n}$ sur $E$, pour un certain $n \in \N$. Dans le cas contraire, $E$ est dit $\Emph{infini}$.
- Cardinal : Si $E$ est fini, l'entier $n$ de la définition précédente est unique. On l'appelle le $\Emph{cardinal}$ de $E$, ou le $\Emph{nombre d'éléments}$ de $E$, et on le note $\abs{E}$ (ou $\Card{E}$ ou $\#E$).
En particulier, l'ensemble vide est fini et $\abs{\emptyset}=0$.
Soient $m, n \in \mathbb{Z}$ deux entiers pour lesquels $m < n$. L'ensemble $\Intn{m}{n}$ est fini de cardinal $n-m+1$ car la fonction $k \mapsto k+m-1$ est bijective de $\Intn{1}{n-m+1}$ sur $\Intn{m}{n}$ et de réciproque $k \mapsto k-m+1$.
On dit que deux ensembles $E$ et $F$ sont équipotents s'il existe une bijection de $E$ sur $F$. La relation d'équipotence est une relation d'équivalence.
Soient $E$ et $F$ deux ensembles. Si $E$ est fini et si $E$ et $F$ sont équipotents, alors $F$ est fini et $\abs{E}=\abs{F}$.
Comme $E$ est fini, il existe une bijection $f:\Intn{1}{n}\to E$ pour un certain $n \in \N$. Comme $E$ et $F$ sont équipotents, il existe une bijection $g:E\to F$. Alors $g\circ f:\Intn{1}{n}\to F$ est une bijection. Donc $F$ est fini et $\abs{F}=n = \abs{E}$.
Soit $E$ un ensemble fini et $A$ une partie de $E$. Alors $A$ est finie et $\abs{A} \leq \abs{E}$, avec égalité si et seulement si $A = E$.
Pour montrer que deux ensembles finis $A$ et $B$ sont égaux, on peut remplacer l'une des deux inclusions par la vérification de $\abs{A}=\abs{B}$.
Soient $E$ et $F$ deux ensembles et $f : E \to F$ une application.
- Si $f$ est injective et si $E$ est fini, alors $F$ est fini et $\abs{E} \leq \abs{F}$, avec égalité si et seulement si $f$ est bijective.
- Si $f$ est surjective et si $E$ est fini, alors $F$ est fini et $\abs{E} \geq \abs{F}$, avec égalité si et seulement si $f$ est bijective.
- Si $E$ et $F$ sont finis de même cardinal : $$ f \text{ est bijective } \iff f \text{ est injective } \iff f \text{ est surjective.} $$
Une application est injective si deux points distincts ont deux images distinctes. Cela n'est possible que s'il y a au moins autant d'éléments à l'arrivée qu'au départ, c'est-à-dire $\abs{E} \leq \abs{F}$.
Une application est surjective si tout élément de l'ensemble d'arrivée a au moins un antécédent. Cela n'est possible que s'il y a au moins autant d'éléments au départ qu'à l'arrivée, c'est-à-dire $\abs{F}\leq\abs{E}$.
Quand on range $n+1$ chaussettes dans $n$ tiroirs, deux chaussettes au moins se retrouvent dans le même tiroir.
Ranger $n+1$ chaussettes dans $n$ tiroirs revient à choisir une application d'un ensemble de cardinal $n+1$ dans un ensemble de cardinal $n$. Puisque $n+1>n$, cette application ne peut pas être injective : deux chaussettes au moins sont donc rangées dans le même tiroir --- d'où le résultat.
Étant donnés $5$ points dans un carré de côté $2$, on peut toujours en trouver deux dont la distance est inférieure ou égale à $\sqrt{2}$.
Découpons le carré en quatre carrés de côté $1$. Les $5$ points étant répartis dans ces $4$ carrés, le principe des tiroirs assure que deux d'entre eux au moins appartiennent au même petit carré. Or la distance maximale entre deux points d'un carré de côté $1$ est la longueur de sa diagonale, soit $\sqrt{2}$. Ces deux points sont donc distants d'au plus~$\sqrt{2}$.
Pour tout ensemble fini $E$ et toute partie $A$ de $E$ : $\abs{A} = \Sum{x \in E}{} \one_A(x)$.
Compter les éléments d'un ensemble $A$, c'est parcourir tous les éléments de $E$ et compter $1$ lorsque l'élément considéré appartient à $A$, et $0$ sinon.
II) Dénombrement
A - Principe du dénombrement
Dénombrer, c'est compter. Lorsqu'un ensemble contient beaucoup d'éléments, il n'est pas envisageable de les énumérer un par un. Le dénombrement consiste précisément à développer des méthodes permettant de compter efficacement.
Pour dénombrer un ensemble, on peut commencer par se demander :
Comment construire un élément quelconque de cet ensemble ?
On peut alors décomposer sa construction en une succession de choix, et compter le nombre de possibilités à chaque étape.
Imaginons que vous alliez au restaurant. Le menu du midi propose $4$ entrées, $2$ plats et $3$ desserts. Combien de menus différents peut-on composer ? Plutôt que de les écrire un par un, décomposons la construction d'un menu :
- il faut d'abord choisir une entrée : $4$ possibilités ;
- puis choisir un plat : $2$ possibilités ;
- enfin choisir un dessert : $3$ possibilités.
À ce stade, une remarque est essentielle : ce qui compte n'est pas le choix effectué, mais le nombre de possibilités qu'il laisse pour la suite. Par exemple, que l'on ait choisi l'entrée $E_1$ ou l'entrée $E_2$, il reste dans les deux cas $2$ choix de plats, puis $3$ choix de desserts. On obtient donc $4\times2\times3=24$ menus différents.
Cependant, construire un objet par choix successifs n'est pas toujours aussi direct. Il faut parfois trouver une manière plus astucieuse de procéder.
Considérons maintenant cinq lancers d'un dé, et cherchons le nombre de suites de résultats dans lesquelles le $6$ apparaît exactement deux fois, le $1$ exactement deux fois et le $4$ exactement une fois. On pourrait essayer de construire la suite lancer après lancer.
Pour le premier lancer, les seules valeurs compatibles avec la condition recherchée sont $1$, $4$ et $6$. Mais les possibilités pour les lancers suivants dépendent des résultats déjà obtenus, ce qui oblige à distinguer de nombreux cas. Par exemple, si les deux premiers lancers sont $6,6$, les trois suivants doivent être $1,1,4$, tandis que si les deux premiers sont $6,1$, il reste encore plusieurs possibilités pour la suite. Le dénombrement devient alors rapidement fastidieux.
Il faut alors changer de point de vue.
Une telle suite est entièrement déterminée par les positions occupées par les deux $6$, puis par les positions occupées par les deux $1$. La position restante est alors nécessairement occupée par le $4$.
On peut donc commencer par choisir deux positions parmi les cinq pour y placer les $6$ : il y a $\binom{5}{2}$ possibilités. Il reste alors trois positions, parmi lesquelles on choisit les deux positions occupées par les $1$ : il y a $\binom{3}{2}$ possibilités. La dernière position est automatiquement occupée par le $4$. On obtient ainsi $\binom{5}{2}\times\binom{3}{2}=30$ suites possibles.
B - Réunion et différence
- Réunion : $\abs{A \cup B} = \abs{A} + \abs{B} - \abs{A \cap B}$. En particulier, si $A$ et $B$ sont disjoints : $\abs{A \cup B} = \abs{A} + \abs{B}$.
[6pt] Plus généralement, si $A_1, \ldots, A_n$ sont deux à deux disjoints : $\abs{\mkern2mu \bigsqcup_{i=1}^n A_i} = \Sum{i=1}{n} \abs{A_i}.$ - Différence : $\abs{A \setminus B} = \abs{A} - \abs{A \cap B}$. En particulier, si $B \subset A : \hquad \abs{A \setminus B} = \abs{A} - \abs{B}$.
L'idée derrière la formule de la réunion est simple : en additionnant $|A|$ et $|B|$, on compte deux fois les éléments communs, ceux de $A \cap B$. Il faut donc les retrancher une fois pour compenser.
En revanche, dès que les ensembles sont disjoints, ce problème de double comptage disparaît : on additionne les cardinaux sans rien retrancher. Ce cas particulier, décliné pour $n$ ensembles de même cardinal, porte même un petit nom :
Toute réunion disjointe de $n$ ensembles de même cardinal $p$ est un ensemble de cardinal $np$.
Bref, un berger qui possède $n$ moutons possède aussi $4n$ pattes de moutons !
C'est sans doute le principe que nous utiliserons le plus dans ce chapitre, car il correspond à une situation très fréquente~: un problème de dénombrement qui se décompose en deux étapes successives, « étape 1 » offrant $n$ choix possibles, puis « étape 2 » offrant $p$ choix possibles quel que soit le choix fait à l'étape 1. Le problème complet admet alors $np$ solutions.
Un cadenas à trois molettes, chacune graduée de $0$ à $9$, possède $10^3$ codes possibles : $10$ choix pour la première molette, puis $10$ pour la deuxième, puis $10$ pour la troisième, indépendamment des choix précédents.
Combien y a-t-il de couples $(x,y)$ dans $\Intn{1}{n}^2$ pour lesquels $x \neq y$ ?
Pour construire un tel couple, on peut d'abord choisir $x$, puis choisir $y$. Il y a $n$ valeurs possibles de $x$, et pour chacune de ces valeurs, $n-1$ valeurs restantes pour $y$ — donc en tout $n(n-1)$ couples possibles.
À partir d'un alphabet de $p$ lettres, combien de mots de $n$ lettres peut-on former qui ne contiennent jamais deux lettres identiques consécutives ?
Pour la première lettre, on peut choisir n'importe quelle lettre de l'alphabet ($p$ possibilités). Pour chacune des $n-1$ lettres suivantes, il faut éviter de répéter la précédente : il reste donc $p-1$ choix à chaque fois — d'où un total de $p(p-1)^{n-1}$ mots.
Une urne contient $2n$ boules numérotées de $1$ à $2n$ qu'on tire successivement sans remise. Combien de tirages peut-on faire pour lesquels un numéro pair est toujours suivi d'un numéro impair et un numéro impair d'un numéro pair ?
Les tirages à dénombrer sont de deux types : ceux qui commencent par un numéro pair et ceux qui commencent par un numéro impair. Nous allons dénombrer séparément ces deux ensembles de tirages et additionner à la fin les deux cardinaux obtenus.
- Cas 1 : tirages commençant par un numéro pair. Faire un tel tirage consiste à tirer successivement :
- une boule paire ($n$ possibilités),
- puis une boule impaire ($n$ possibilités),
- puis une boule paire restante ($n-1$ possibilités),
- puis une boule impaire restante ($n-1$ possibilités),
- \dots
- Cas 2 : tirages commençant par un numéro impair. Un raisonnement analogue montre que $(n!)^2$ tirages exactement commencent par un numéro impair.
Le nombre total de tirages recherchés est donc $(n!)^2 + (n!)^2 = 2 \times (n!)^2. $
Comment savoir s'il faut additionner ou multiplier ? Le réflexe à avoir :
$\begin{array}{cl} \text{\Og soit ceci, soit cela \Fg} & \Rightarrow \quad \textbf{Addition} \\ \text{\Og d'abord ceci, \textbf{puis} cela \Fg} & \Rightarrow \quad \textbf{Multiplication} \end{array}$
C - Produit cartésien, listes et arrangements
Pour tous ensembles finis $E_1, \dots, E_p$, $|E_1 \times \dots \times E_p| = |E_1| \times \dots \times |E_p|.$ En particulier, $|E|^p = |E^p|.$
Construire un élément de $E_1 \times \dots \times E_p$, c'est choisir successivement un élément de $E_1$ ($|E_1|$ possibilités), puis un élément de $E_2$ ($|E_2|$ possibilités), \dots, puis un élément de $E_p$ ($|E_p|$ possibilités) — indépendamment des choix précédents. Le principe des bergers donne alors un total de $|E_1| \times \dots \times |E_p|$ éléments
Soit $p \in \N^*$. On appelle p-liste de $E$ ou p-uplet de $E$ toute famille de $p$ éléments de $E$, i.e. tout élément de $E^p$.
Si on pose $n = |E|$, il existe $n^p$ p-listes de $E$.
Une liste, c'est une famille et non un ensemble : l'ordre des éléments compte, et un même élément peut y figurer plusieurs fois.
C'est exactement ce qui se passe lors d'un tirage successif avec remise : on tire un élément, on le remet, on retire, etc. — d'où la modélisation des tirages successifs avec remise par des listes.
Il y a $52^5$ façons de tirer 5 cartes successivement avec remise dans un jeu de 52 cartes.
Un mot de passe est composé de 9 caractères, chacun choisi parmi 26 lettres. Combien de mots de passe contiennent, à des positions consécutives, la séquence MATHS ?
Un mot de passe de 9 caractères ne peut contenir MATHS qu'une seule fois : si les 5 lettres qui le composent apparaissaient deux fois, il faudrait au moins 10 caractères pour les loger sans qu'elles se chevauchent. Pour construire un tel mot de passe, il suffit donc de :
- choisir la position du bloc MATHS : le M initial peut se placer à n'importe laquelle des positions $1$ à $5$, soit $5$ possibilités ;
- puis remplir les $4$ positions restantes avec des lettres quelconques, i.e. choisir une 4-liste de l'alphabet ($26^4$ possibilités).
D'où un total de $5 \times 26^4$ mots de passe.
Soit $p \in \N^*$. On appelle p-arrangement de $E$ toute p-liste de $E$ d'éléments distincts.
Si on pose $n = |E|$, il existe $\frac{n!}{(n-p)!}$ p-arrangements de $E$ si $p \leq n$, et il n'en existe pas si $p > n$.
En particulier, pour $p = n$, on peut ordonner de $n!$ façons différentes exactement les $n$ éléments de $E$.
Pour construire un p-arrangement dans le cas où $p \leq n$, on peut choisir un premier élément dans $E$ (n possibilités), puis un deuxième distinct du premier ($n-1$ possibilités), etc., enfin un p-ème distinct des précédents ($n - p + 1$ possibilités). D'où un total de $n \times (n-1) \times \dots \times (n - p + 1) = \frac{n!}{(n-p)!}$ arrangements de $E$.
Les arrangements sont utilisés pour modéliser des tirages successifs sans remise — les répétitions sont interdites.
De combien de façons peut-on tirer 5 cartes successivement sans remise dans un jeu de 52 cartes ? Il y a $52$ choix pour la première, $51$ pour la deuxième, etc. Ainsi, il y en a au total $\dfrac{52!}{(52 - 5)!} = 52 \times 51 \times 50 \times 49 \times 48.$
De combien de façons peut-on asseoir $n$ personnes sur un banc rectiligne ? Et autour d'une table ronde ? Dans les deux cas, ce qui compte pour chaque personne, c'est de savoir qui se trouve à sa gauche et à sa droite.
Banc rectiligne : Numérotons les $n$ personnes de $1$ à $n$. Les asseoir sur un banc, c'est choisir dans quel ordre les énumérer de gauche à droite, i.e. se donner un $n$-arrangement de $\{1, \dots, n\}$ — d'où $n!$ configurations possibles.
Table ronde : Autour d'une table ronde, il n'y a en revanche pas de « première place » : faire glisser tout le monde d'un cran vers la droite ne change rien à la configuration. On peut donc asseoir arbitrairement une première personne, puis placer les $n-1$ autres de proche en proche autour d'elle, i.e. se donner un $(n-1)$-arrangement de $\{1, \dots, n-1\}$ — d'où $(n-1)!$ configurations possibles.
On peut retrouver ce résultat autrement. Chacune des $n!$ configurations rectilignes donne une configuration circulaire en joignant ses deux extrémités, mais ce procédé construit chaque configuration circulaire plusieurs fois : une configuration circulaire donnée provient exactement de $n$ configurations rectilignes distinctes, selon l'endroit où on la « coupe » pour la mettre en ligne. Il y a donc bien $\dfrac{n!}{n} = (n-1)!$ configurations circulaires.
D - Ensembles d'applications
Une p-liste de $E$ n'est en fait rien d'autre qu'une application de $\Intn{1}{p}$ dans $E$ : à la p-liste $(x_1, \dots, x_p)$ correspond l'application $i \mapsto x_i$, et réciproquement, toute application $f$ de $\Intn{1}{p}$ dans $E$ redonne la p-liste $(f(1), \dots, f(p))$. Cette identification permet d'adapter directement les résultats du paragraphe précédent aux applications : les arrangements y jouent pour les applications le même rôle que les listes, mais du côté des injections.
Soient $E$ et $F$ deux ensembles finis. On pose $p = |E|$ et $n = |F|$.
- Applications quelconques : $|F^E| = |F|^{|E|} = n^p$.
- Applications injectives : Une application injective de $E$ dans $F$ n'existe que si $p \le n$.
Sous cette condition, l'ensemble des applications injectives de $E$ dans $F$ est de cardinal $\dfrac{n!}{(n-p)!}$. - Bijections : Une bijection de $E$ sur $F$ n'existe que si $p = n$.
L'ensemble des bijections de $E$ dans $F$ est alors de cardinal $n!$. En particulier, $|S_E| = |E|!$.
- Pour construire une application quelconque $f : E = \{e_1, \dots, e_p\} \to F$, il suffit de se donner une p-liste $(f(e_1), \dots, f(e_p))$ de $F$ et de poser $f : e_i \mapsto f(e_i)$ — d'où un total de $|F|^p = |F|^{|E|}$ applications.
- Pour construire une application injective, il suffit là encore de se donner une p-liste $(f(e_1), \dots, f(e_p))$ de $F$, mais l'injectivité impose que cette p-liste soit en fait un p-arrangement de $F$ — d'où un total de $\dfrac{n!}{(n-p)!}$ applications injectives si $p \le n$, et $0$ si $p > n$.
- Une application injective entre deux ensembles finis de même cardinal est automatiquement bijective. Le calcul de $|S_E|$ découle donc de (ii) en prenant $p = n = |E|$.
Soit $n \ge 3$. Combien y a-t-il de permutations de $\llbracket 1, n \rrbracket$ qui envoient $1$ sur $2$ et $2$ sur $3$ ?
Soit $\sigma$ une telle permutation : les images $\sigma(1) = 2$ et $\sigma(2) = 3$ sont fixées. Il reste à choisir les images des $n-2$ éléments restants, en respectant l'injectivité de $\sigma$ :
- $\sigma(3)$ peut être choisi parmi les $n-2$ valeurs de $\Intn{1}{n} \setminus \{2, 3\}$ ;
- $\sigma(4)$ doit être distinct de $\sigma(3)$ : $n-3$ possibilités restantes ;
- \dots
- $\sigma(n)$ est alors la seule valeur restante : $1$ possibilité.
D'où un total de $(n-2) \times (n-3) \times \dots \times 1 = (n-2)!$ permutations possibles.
Autrement dit, une fois $\sigma(1)$ et $\sigma(2)$ fixés, se donner $\sigma$ revient exactement à se donner une bijection quelconque de $\{3, \dots, n\}$ sur $\Intn{1}{n} \setminus \{2, 3\}$ — deux ensembles de cardinal $n-2$ — d'où là encore $(n-2)!$ possibilités.
E - Combinaisons
- Combinaison : Soit $E$ un ensemble fini et $p \in \Z$. On appelle p-combinaison de $E$ toute partie de $E$ de cardinal $p$. Cet ensemble est noté $\mathcal{P}_p(E)$ (notation non universelle).
- Coefficients binomiaux : Soient $n \in \N$ et $k \in \Z$.
On appelle $\mathbf{k}$ parmi $\mathbf{n}$ et on note $\dbinom{n}{k}$ le nombre de parties de cardinal $k$ de l'ensemble $\Intn{1}{n}$. On a alors :Si on pose $n = |E|$, le nombre de p-combinaisons de $E$ vaut alors $|\mathcal{P}_p(E)| = \binom{n}{p}$.- Si $k < 0 \text{ ou } k > n$, $\dbinom{n}{k} = 0$.
- Si $k \in \Intn{0}{n}$, $\displaystyle \dbinom{n}{k} = \f{n!}{k!(n-k)!}$.
Si $k \in \Intn{0}{n}$, on compte de deux façons le nombre de $k$-uplets d'éléments distincts de $\Intn{1}{n}$.
- Premier comptage : pour construire $(x_1, \dots, x_k)$, il y a $n$ choix pour $x_1$, puis $n-1$ choix pour $x_2$ (distinct de $x_1$), \dots, puis $n-k+1$ choix pour $x_k$. Il y a donc $$n(n-1)\cdots(n-k+1) = \f{n!}{(n-k)!}$$ tels $k$-uplets.
- Second comptage : construire $(x_1, \dots, x_k)$, c'est aussi
- choisir une partie $A = \{x_1, \dots, x_k\}$ de cardinal $k$ de $\Intn{1}{n}$ : il y a $\dbinom{n}{k}$ choix possibles ;
- ordonner les éléments de $A$, c'est-à-dire d'une bijection de $\Intn{1}{k}$ dans $A$ : il y a $k!$ choix possibles.
Par double comptage : $\dbinom{n}{k} \, k! = \f{n!}{(n-k)!}.$
Une combinaison est un ensemble, et non une famille : ses éléments sont donnés sans ordre. On peut toujours décider de les numéroter pour les manipuler, mais ce choix de numérotation est totalement arbitraire — une combinaison n'a pas, en tant que telle, de premier élément, de deuxième, etc.
C'est exactement ce qui se passe lors d'un tirage simultané : on prélève plusieurs éléments d'un coup, sans qu'aucun ordre n'apparaisse entre eux — d'où la modélisation des tirages simultanés par des combinaisons.
Il y a $\binom{52}{5}$ façons de tirer 5 cartes simultanément dans un jeu de 52 cartes.
Soient $n,k \in \N$.
- Symétrie : $\dbinom{n}{k} = \dbinom{n}{n-k}$.
- Formule de Pascal : $\dbinom{n}{k} + \dbinom{n}{k+1} = \dbinom{n+1}{k+1}$.
- Formule du capitaine : Si $n \geq 1$ et $k \in \Intn{1}{n}$ : $ k\dbinom{n}{k} = n \dbinom{n-1}{k-1}$.
La formule reste vraie lorsque $k > n$ ou $k \leq 0$.
On démontre les formules (i) et (ii) lorsque $n \geq 1$ et $k \in \Intn{0}{n}$.
- Choisir une partie à $k$ éléments de $\Intn{1}{n}$ revient à choisir les $n-k$ éléments qui ne seront pas dans la partie. Il y a donc $\dbinom{n}{k}$ possibilités mais aussi $\dbinom{n}{n-k}$ possibilités.
- On compte de deux façons le nombre de parties à $k+1$ éléments dans $\Intn{1}{n+1}$.
- On peut directement choisir les $k+1$ éléments --- $\dbinom{n+1}{k+1}$ choix.
- Nous pouvons distinguer selon que la partie contienne l'entier $n+1$ ou non.
- Si elle contient $n+1$, il reste $k$ éléments à choisir dans $\Intn{1}{n}$ --- $\dbinom{n}{k}$ choix.
- Sinon, il reste $k+1$ éléments à choisir dans $\Intn{1}{n}$ --- $\dbinom{n}{k+1}$ choix.
- Ici, $k \in \Intn{1}{n}$. Cherchons à dénombrer le nombre de couples $(A,k)$ où $A$ est une partie de $\Intn{1}{n}$ et $k \in A$ est le représentant de cette partie, dit « capitaine ». On procède encore par double comptage.
- Premier comptage : Pour construire le couple $(A,k)$, on peut :
- commencer par choisir l'ensemble $A$ --- $\dbinom{n}{k}$ choix ;
- choisir le représentant de $A$ --- $k$ choix.
- Deuxième comptage : On peut aussi :
- commencer par choisir le représentant --- $n$ choix ;
- choisir les $k-1$ éléments restants de $A$ parmi les $n-1$ entiers restants --- $\dbinom{n-1}{k-1}$ choix.
- Premier comptage : Pour construire le couple $(A,k)$, on peut :
Pour tout $k \in \llbracket 1, n \rrbracket$, il existe $\binom{n}{k}$ familles d'entiers $(i_1, \dots, i_k)$ pour lesquelles $1 \le i_1 < \dots < i_k \le n$.
Il y a autant de telles familles que de $k$-combinaisons de $\Intn{1}{n}$, car il n'y a qu'une seule manière de ranger les éléments d'une $k$-combinaison de $\Intn{1}{n}$ dans l'ordre croissant.
Un jeu de tarot contient $78$ cartes --- $21$ atouts, la carte qu'on appelle l'excuse, et $14$ cartes de chacune des $4$ couleurs cœur, pique, trèfle et carreau. Combien de tirages simultanés de $6$ cartes d'un tel jeu peut-on obtenir contenant exactement un atout et au moins $3$ as ?
Un tel tirage se construit en choisissant l'atout, puis les 5 autres cartes.
- L'atout : $\binom{21}{1}$ choix.
- Les 5 autres cartes sont prises parmi les 57 cartes qui ne sont pas des atouts : 4 as et 53 autres cartes.
Il est tentant de choisir 3 as puis 2 cartes quelconques parmi les 54 restantes, mais une main à 4 as serait alors comptée 4 fois (une fois par as laissé de côté). On compte donc selon le nombre exact d'as :
- Exactement 3 as : $\binom{4}{3}$ choix pour les as et $\binom{53}{2}$ pour les deux autres cartes.
- Exactement 4 as : $\binom{4}{4}$ choix pour les as et $\binom{53}{1}$ pour la dernière carte.
Ces deux cas sont disjoints, donc le nombre de tirages cherché est $$ \binom{21}{1}\left[\binom{4}{3}\binom{53}{2} + \binom{4}{4}\binom{53}{1}\right]. \qedhere $$
- Et le complémentaire ? Pour un « au moins », on pense souvent à compter le contraire. Ici, ce n'est pas rentable : le contraire de « au moins 3 as » est « 0, 1 ou 2 as », soit trois cas au lieu de deux : $$ \binom{21}{1}\left[\binom{57}{5} - \binom{4}{0}\binom{53}{5} - \binom{4}{1}\binom{53}{4} - \binom{4}{2}\binom{53}{3}\right]. $$ Le complémentaire vaut le coup quand il a moins de cas que l'événement lui-même, typiquement pour « au moins un » (contraire : « aucun », un seul cas).
- Piège. Il ne faut pas compter « on choisit 3 as, puis 2 cartes quelconques parmi les 54 restantes » : $\binom{4}{3}\binom{54}{2}$ compte plusieurs fois les mains à 4 as (chacune est obtenue 4 fois, selon l'as qu'on considère comme « en plus »).
On appelle anagramme d'un mot tout autre mot composé des mêmes lettres avec multiplicité, mais dans un ordre quelconque. Les mots STAHM et HTMAS sont par exemple deux anagrammes de MATHS. Combien d'anagrammes BANANE possède-t-il ?
Le mot BANANE est composé de $6$ lettres : $B$, $A$, $N$, $A$, $N$, $E$ — la lettre $A$ apparaît $2$ fois, la lettre $N$ apparaît $2$ fois, et $B$, $E$ apparaissent chacune $1$ fois.
- Démonstration avec des coefficients binomiaux. Un anagramme est déterminé par le choix, parmi les $6$ positions disponibles, de celles occupées par chaque lettre. On construit un tel anagramme en :
- choisissant les $2$ positions des $A$ parmi les $6$ positions --- $\dbinom{6}{2}$ choix ;
- choisissant, parmi les $4$ positions restantes, les $2$ positions des $N$ --- $\dbinom{4}{2}$ choix ;
- choisissant, parmi les $2$ positions restantes, celle du $B$ --- $\dbinom{2}{1}$ choix ---,
- puis celle du $E$ parmi la dernière position restante --- $\dbinom{1}{1}$ choix.
- Formule directe avec des factorielles. On peut remarquer que le résultat précédent s'écrit aussi $$ \dbinom{6}{2} \dbinom{4}{2} \dbinom{2}{1} \dbinom{1}{1} = \frac{6!}{2! \, 4!} \times \frac{4!}{2! \, 2!} \times \frac{2!}{1! \, 1!} \times \frac{1!}{1! \, 0!} = \frac{6!}{2! \, 2! \, 1! \, 1!}. $$ Cela s'explique simplement : si les $6$ lettres étaient toutes distinctes, il y aurait $6!$ façons de les ordonner. Mais pour un anagramme donné, on peut permuter entre elles les $2$ occurrences de $A$ ($2!$ façons) et, indépendamment, permuter entre elles les $2$ occurrences de $N$ ($2!$ façons) sans changer le mot obtenu : chaque anagramme réel est donc compté $2! \times 2! \times 1! \times 1! = 4$ fois dans le $6!$. On corrige ce surcomptage en divisant par $2! \, 2! \, 1! \, 1!$, et on retrouve bien $180$.
On pose $n = \abs{E}$.
- Démonstration par dénombrement. Choisir une partie $A$ de $E$ revient à décider, pour chacun des $n$ éléments de $E$, s'il appartient à $A$ ou non : il y a $2$ choix indépendants par élément, donc $$ \abs{\Pr(E)} = \underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ facteurs}} = 2^n. $$
- Démonstration par bijection.
Montrons que l'application $\phi : \fun{\Pr(E)}{\{0,1\}^E}{A}{\one_A}$ est bijective de réciproque $\psi : \fun{\{0,1\}^E}{\Pr(E)}{f}{f^{-1}(\{1\})}$.- Pour tout $A \in \Pr(E)$, $\psi(\phi(A)) = \{x \in E \mid \one_A(x) = 1\} = A$ ;
- Pour tout $f \in \{0,1\}^E$, $\phi(\psi(f)) = \one_{f^{-1}(\{1\})}$.
Or, $\one_{f^{-1}(\{1\})}(x) = 1 \hiffh x \in f^{-1}(\{1\}) \hiffh f(x) = 1$. Donc $\phi(\psi(f)) = f$.
- Démonstration avec le binôme de Newton. On part de l'égalité $\Pr(E) = \bigsqcup_{k=0}^{n} \Pr_k(E)$. En passant au cardinal on obtient : $$ \abs{\Pr(E)} = \sum_{k=0}^{n} \dbinom{n}{k} = (1+1)^n = 2^n. \qedhere $$
Glissez une image, collez-la (Ctrl+V), ou parcourez un fichier — ou collez directement l'énoncé en texte.