Combinatoire et dénombrement

Une sandwicherie propose $4$ pains, $6$ garnitures et $3$ sauces, tous différents. Elle vend aussi $9$ salades composées.

1. Nombre de sandwichs différents (un pain, une garniture, une sauce) :
   Un sandwich se construit en trois étapes : $4$ choix de pain, $6$ de garniture, $3$ de sauce. Par le principe multiplicatif : $4\times 6\times 3=72$ sandwichs.
2. Un client prend soit un sandwich, soit une salade. Nombre de choix possibles :
   Les sandwichs et les salades forment deux ensembles disjoints : par le principe additif, $72+9=81$ choix.

Compter des $k$-uplets (répétitions permises).

1. Mots de passe de $5$ caractères, chacun choisi parmi les $26$ lettres minuscules :
   Un mot de passe est un $5$-uplet de l’ensemble des $26$ lettres : ${26}^5=11881376$.
2. Suites de résultats obtenues en lançant $8$ fois une pièce (pile ou face) :
   Un résultat est un $8$-uplet de $\{\text{P},\text{F}\}$ : $2^8=256$ suites.
3. Codes de $3$ chiffres tapés sur un clavier dont les touches vont de $1$ à $8$ :
   $3$-uplet d’un ensemble à $8$ éléments : $8^3=512$ codes.

On lance successivement $4$ dés à six faces et on note les résultats dans l’ordre (un résultat est un $4$-uplet).

1. Nombre total de résultats :
   $4$-uplets de $\{1,\dots ,6\}$ : $6^4=1296$ résultats.
2. Nombre de résultats ne contenant aucun $6$ :
   Chaque dé affiche un nombre parmi $1,\dots ,5$ : $5^4=625$ résultats.
3. Justifier le nombre de résultats contenant au moins un $6$ :
   Rédaction attendue. Notons $\Omega$ l’ensemble des résultats et $A$ l’ensemble des résultats contenant au moins un $6$. Le complémentaire $\bar{A}$ est l’ensemble des résultats sans aucun $6$ ; chaque dé a alors $5$ valeurs possibles, donc, par le principe multiplicatif, $\text{card}(\bar{A})=5^4=625$. Ainsi $\text{card}(A)=\text{card}(\Omega )-\text{card}(\bar{A})$, soit $1296-625=671$ résultats contiennent au moins un $6$.

On considère les entiers de $1$ à $600$. On note $A$ ceux qui sont divisibles par $4$ et $B$ ceux qui sont divisibles par $6$.

1. $\text{card}(A)=$
   Les multiples de $4$ entre $1$ et $600$ sont $4\times 1,\dots ,4\times 150$ : $\text{card}(A)=150$.
2. $\text{card}(B)=$
   Les multiples de $6$ sont $6\times 1,\dots ,6\times 100$ : $\text{card}(B)=100$.
3. $A\cap B$ est exactement l’ensemble des multiples de compris entre $1$ et $600$.
   Un entier est divisible par $4$ et par $6$ si et seulement s’il est divisible par leur plus petit multiple commun, $12$. Il y en a $50$ entre $1$ et $600$.
4. Justifier le nombre d’entiers de $1$ à $600$ divisibles par $4$ ou par $6$ :
   Rédaction attendue. Les ensembles $A$ et $B$ ne sont pas disjoints ($12$ est dans les deux) : on ne peut pas simplement additionner. $A\cap B$ est l’ensemble des multiples de $12$, soit ${\displaystyle \frac{600}{12}}=50$ entiers. Donc $\text{card}(A\cup B)$ $=\text{card}(A)+\text{card}(B)-\text{card}(A\cap B)$, soit $150+100-50=200$ entiers.

Calculer sans écrire les factorielles en entier.

1. $6!=$
   $6!=1\times 2\times 3\times 4\times 5\times 6=720$.
2. ${\displaystyle \frac{9!}{7!}}=$
   $9!=9\times 8\times 7!$, donc ${\displaystyle \frac{9!}{7!}}=9\times 8=72$.
3. ${\displaystyle \frac{8!}{4!}}=$
   ${\displaystyle \frac{8!}{4!}}=8\times 7\times 6\times 5=1680$ : c’est le nombre de $4$-uplets d’éléments distincts d’un ensemble à $8$ éléments.

Reconnaître des $k$-uplets d’éléments distincts ou des permutations.

1. Une course compte $12$ chevaux, sans ex æquo. Nombre de tiercés dans l’ordre (trois premiers) :
   Un tiercé dans l’ordre est un $3$-uplet de chevaux distincts : $12\times 11\times 10=1320$.
2. Nombre de façons de ranger $7$ livres différents sur une étagère :
   Un rangement est une permutation des $7$ livres : $7!=5040$.
3. Un club de $15$ membres élit un président et un secrétaire (deux personnes distinctes). Nombre de choix :
   Les rôles sont distincts, donc l’ordre compte : $15\times 14=210$ couples (président, secrétaire).

Factorielles et équations.

1. Démontrer que, pour tout entier $n⩾1$, $(n+1)!-n!=n\times n!$. Contrôle : $5!-4!=$
   Rédaction attendue. Pour tout entier $n⩾1$, $(n+1)!=(n+1)\times n!$. Donc $(n+1)!-n!=(n+1)\times n!-n!$ $=n!\times (n+1-1)=n\times n!$. Contrôle avec $n=4$ : $5!-4!=120-24=96$ et $4\times 4!=4\times 24=96$.
2. Un ensemble $E$ à $n$ éléments possède $56$ couples d’éléments distincts. Démontrer que $n=$
   Rédaction attendue. Le nombre de $2$-uplets d’éléments distincts de $E$ est $n(n-1)$. On résout $n(n-1)=56$, soit $n^2-n-56=0$. Le discriminant vaut $\Delta =1+224=225={15}^2$ ; les racines sont ${\displaystyle \frac{1+15}{2}}=8$ et ${\displaystyle \frac{1-15}{2}}=-7$. Comme $n$ est un entier naturel, $n=8$ (contrôle : $8\times 7=56$).

On forme des anagrammes (mots, ayant un sens ou non) avec les $8$ lettres, toutes distinctes, du mot TRIANGLE. Ses voyelles sont I, A et E ; ses $5$ consonnes sont T, R, N, G et L.

1. Nombre total d’anagrammes :
   Une anagramme est une permutation des $8$ lettres distinctes : $8!=40320$.
2. Nombre d’anagrammes qui commencent et finissent par une consonne :
   Première lettre : $5$ consonnes ; dernière lettre : $4$ consonnes restantes ; les $6$ lettres du milieu se rangent de $6!$ façons. Par le principe multiplicatif : $5\times 4\times 720=14400$.
3. Justifier le nombre d’anagrammes dans lesquelles les trois voyelles sont côte à côte :
   Rédaction attendue. On regroupe les trois voyelles en un bloc. On range alors $6$ objets (le bloc et les $5$ consonnes), ce qui donne $6!=720$ permutations. Dans le bloc, les trois voyelles se rangent de $3!=6$ façons. Chaque anagramme cherchée est obtenue une seule fois par ces deux choix : par le principe multiplicatif, il y en a $720\times 6=4320$.

Calculer chaque coefficient binomial (la symétrie peut aider).

1. ${\displaystyle \left(\genfrac{}{}{0ex}{}{11}{4}\right)}=$
   ${\displaystyle \left(\genfrac{}{}{0ex}{}{11}{4}\right)}={\displaystyle \frac{11\times 10\times 9\times 8}{4!}}={\displaystyle \frac{7920}{24}}=330$.
2. ${\displaystyle \left(\genfrac{}{}{0ex}{}{20}{2}\right)}=$
   ${\displaystyle \left(\genfrac{}{}{0ex}{}{20}{2}\right)}={\displaystyle \frac{20\times 19}{2}}=190$.
3. ${\displaystyle \left(\genfrac{}{}{0ex}{}{15}{13}\right)}=$
   Par symétrie, ${\displaystyle \left(\genfrac{}{}{0ex}{}{15}{13}\right)}={\displaystyle \left(\genfrac{}{}{0ex}{}{15}{2}\right)}={\displaystyle \frac{15\times 14}{2}}=105$.
4. ${\displaystyle \left(\genfrac{}{}{0ex}{}{9}{0}\right)}=$
   Il y a une seule partie à $0$ élément : la partie vide. ${\displaystyle \left(\genfrac{}{}{0ex}{}{9}{0}\right)}=1$.

Situations sans ordre.

1. Un tournoi aller simple réunit $14$ équipes (chaque paire d’équipes joue une fois). Nombre de matchs :
   Un match est une paire d’équipes : ${\displaystyle \left(\genfrac{}{}{0ex}{}{14}{2}\right)}={\displaystyle \frac{14\times 13}{2}}=91$.
2. Nombre de façons de choisir $4$ livres à emporter parmi $9$ :
   On choisit une partie à $4$ éléments : ${\displaystyle \left(\genfrac{}{}{0ex}{}{9}{4}\right)}={\displaystyle \frac{9\times 8\times 7\times 6}{24}}=126$.
3. Grilles d’une loterie où l’on coche $6$ numéros parmi $49$ :
   Une grille est une partie à $6$ éléments de $\{1,\dots ,49\}$ : ${\displaystyle \left(\genfrac{}{}{0ex}{}{49}{6}\right)}=13983816$ (calculatrice : 49 nCr 6).

Une urne contient $7$ boules rouges et $5$ boules bleues. On tire simultanément $4$ boules.

1. Nombre de tirages possibles :
   Un tirage est une partie à $4$ éléments des $12$ boules : ${\displaystyle \left(\genfrac{}{}{0ex}{}{12}{4}\right)}=495$.
2. Nombre de tirages contenant exactement $2$ boules rouges :
   $2$ rouges parmi $7$, puis $2$ bleues parmi $5$ : ${\displaystyle \left(\genfrac{}{}{0ex}{}{7}{2}\right)}\times {\displaystyle \left(\genfrac{}{}{0ex}{}{5}{2}\right)}$ $=21\times 10=210$.
3. Justifier le nombre de tirages contenant au moins une boule bleue :
   Rédaction attendue. Le contraire de « au moins une bleue » est « aucune bleue », c’est-à-dire $4$ boules rouges : il y a ${\displaystyle \left(\genfrac{}{}{0ex}{}{7}{4}\right)}=35$ tels tirages. Par passage au complémentaire, le nombre de tirages avec au moins une boule bleue est $495-35=460$.

Dans cet exercice, $n$ est un entier tel que $n⩾2$.

1. Démontrer que ${\displaystyle \left(\genfrac{}{}{0ex}{}{n}{2}\right)}={\displaystyle \frac{n(n-1)}{2}}$. Contrôle : ${\displaystyle \left(\genfrac{}{}{0ex}{}{40}{2}\right)}=$
   Rédaction attendue. D’après la formule du cours, ${\displaystyle \left(\genfrac{}{}{0ex}{}{n}{2}\right)}={\displaystyle \frac{n!}{2!(n-2)!}}$. Or $n!=n(n-1)\times (n-2)!$ ; après simplification par $(n-2)!$, il reste ${\displaystyle \left(\genfrac{}{}{0ex}{}{n}{2}\right)}={\displaystyle \frac{n(n-1)}{2}}$. Contrôle : ${\displaystyle \left(\genfrac{}{}{0ex}{}{40}{2}\right)}={\displaystyle \frac{40\times 39}{2}}=780$.
2. Un tournoi aller simple compte $78$ matchs. Nombre d’équipes :
   On résout ${\displaystyle \frac{n(n-1)}{2}}=78$, soit $n^2-n-156=0$ ; $\Delta =1+624=625={25}^2$, racines $13$ et $-12$. L’entier naturel cherché est $n=13$.
3. Nombre de diagonales d’un polygone convexe qui a autant de sommets que d’équipes dans ce tournoi :
   Un segment joignant deux des $13$ sommets est un côté ou une diagonale. Il y a ${\displaystyle \left(\genfrac{}{}{0ex}{}{13}{2}\right)}=78$ segments, dont $13$ côtés : $78-13=65$ diagonales.

La ligne $7$ du triangle de Pascal est : $1$ ; $7$ ; $21$ ; $35$ ; $35$ ; $21$ ; $7$ ; $1$. Utiliser la relation de Pascal.

1. ${\displaystyle \left(\genfrac{}{}{0ex}{}{8}{2}\right)}=$
   ${\displaystyle \left(\genfrac{}{}{0ex}{}{8}{2}\right)}={\displaystyle \left(\genfrac{}{}{0ex}{}{7}{1}\right)}+{\displaystyle \left(\genfrac{}{}{0ex}{}{7}{2}\right)}=7+21=28$.
2. ${\displaystyle \left(\genfrac{}{}{0ex}{}{8}{3}\right)}=$
   ${\displaystyle \left(\genfrac{}{}{0ex}{}{8}{3}\right)}={\displaystyle \left(\genfrac{}{}{0ex}{}{7}{2}\right)}+{\displaystyle \left(\genfrac{}{}{0ex}{}{7}{3}\right)}=21+35=56$.
3. ${\displaystyle \left(\genfrac{}{}{0ex}{}{8}{4}\right)}=$
   ${\displaystyle \left(\genfrac{}{}{0ex}{}{8}{4}\right)}={\displaystyle \left(\genfrac{}{}{0ex}{}{7}{3}\right)}+{\displaystyle \left(\genfrac{}{}{0ex}{}{7}{4}\right)}=35+35=70$ : c’est le coefficient du milieu de la ligne $8$.

Soit $E$ un ensemble à $9$ éléments.

1. Nombre de parties de $E$ :
   Un ensemble à $9$ éléments possède $2^9=512$ parties.
2. Nombre de parties de $E$ à $2$ éléments :
   ${\displaystyle \left(\genfrac{}{}{0ex}{}{9}{2}\right)}={\displaystyle \frac{9\times 8}{2}}=36$.
3. Nombre de parties de $E$ ayant au moins $2$ éléments :
   On retire de $512$ la partie vide et les $9$ singletons : $512-1-9=502$.

Dans cet exercice, $n$ et $k$ sont des entiers tels que $0⩽k⩽n-2$.

1. Démontrer que ${\displaystyle \left(\genfrac{}{}{0ex}{}{n}{k}\right)}+2{\displaystyle \left(\genfrac{}{}{0ex}{}{n}{k+1}\right)}+{\displaystyle \left(\genfrac{}{}{0ex}{}{n}{k+2}\right)}$ $={\displaystyle \left(\genfrac{}{}{0ex}{}{n+2}{k+2}\right)}$. En déduire ${\displaystyle \left(\genfrac{}{}{0ex}{}{7}{1}\right)}+2{\displaystyle \left(\genfrac{}{}{0ex}{}{7}{2}\right)}$ $+{\displaystyle \left(\genfrac{}{}{0ex}{}{7}{3}\right)}=$
   Rédaction attendue. On regroupe : $[{\displaystyle \left(\genfrac{}{}{0ex}{}{n}{k}\right)}+{\displaystyle \left(\genfrac{}{}{0ex}{}{n}{k+1}\right)}]$ $+[{\displaystyle \left(\genfrac{}{}{0ex}{}{n}{k+1}\right)}+{\displaystyle \left(\genfrac{}{}{0ex}{}{n}{k+2}\right)}]$. Comme $k⩽n-1$ et $k+1⩽n-1$, la relation de Pascal s’applique aux deux crochets : la somme vaut ${\displaystyle \left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)}+{\displaystyle \left(\genfrac{}{}{0ex}{}{n+1}{k+2}\right)}$. On applique encore la relation de Pascal (ligne $n+1$, avec $k+1⩽n$) : on obtient ${\displaystyle \left(\genfrac{}{}{0ex}{}{n+2}{k+2}\right)}$. Avec $n=7$ et $k=1$ : ${\displaystyle \left(\genfrac{}{}{0ex}{}{9}{3}\right)}=84$. Contrôle : $7+2\times 21+35=84$.
2. Avec la même égalité, ${\displaystyle \left(\genfrac{}{}{0ex}{}{10}{4}\right)}+2{\displaystyle \left(\genfrac{}{}{0ex}{}{10}{5}\right)}+{\displaystyle \left(\genfrac{}{}{0ex}{}{10}{6}\right)}$ $={\displaystyle \left(\genfrac{}{}{0ex}{}{12}{m}\right)}$ avec $m=$
   On applique l’égalité avec $n=10$ et $k=4$ : la somme vaut ${\displaystyle \left(\genfrac{}{}{0ex}{}{12}{6}\right)}$, donc $m=6$ (et ${\displaystyle \left(\genfrac{}{}{0ex}{}{12}{6}\right)}=924$).

Un ensemble $E$ possède $2048$ parties.

1. Démontrer que le nombre d’éléments de $E$ est
   Rédaction attendue. Si $E$ a $n$ éléments, il possède $2^n$ parties (cours). On cherche donc $n$ tel que $2^n=2048$. Or $2^{11}=2048$, et la suite $(2^n)$ est strictement croissante, donc une seule valeur convient : $E$ a $11$ éléments.
2. Nombre de parties de $E$ ayant au plus $2$ éléments :
   On additionne les parties à $0$, $1$ et $2$ éléments (familles disjointes) : ${\displaystyle \left(\genfrac{}{}{0ex}{}{11}{0}\right)}+{\displaystyle \left(\genfrac{}{}{0ex}{}{11}{1}\right)}+{\displaystyle \left(\genfrac{}{}{0ex}{}{11}{2}\right)}$ $=1+11+55=67$.
3. Nombre de parties de $E$ ayant au moins $3$ éléments :
   Par passage au complémentaire : $2048-67=1981$.

Mots et chemins.

1. Nombre de mots de $10$ bits (chiffres $0$ ou $1$) contenant exactement deux « 1 » :
   Un tel mot est déterminé par les $2$ positions des « 1 » parmi $10$ : ${\displaystyle \left(\genfrac{}{}{0ex}{}{10}{2}\right)}=45$.
2. Nombre de chemins de $(0;0)$ à $(5;5)$ par pas unitaires vers la droite ou vers le haut :
   Un chemin est un mot de $10$ pas contenant $5$ lettres H : ${\displaystyle \left(\genfrac{}{}{0ex}{}{10}{5}\right)}=252$.
3. Nombre d’anagrammes du mot BOBO :
   On choisit les $2$ places des B parmi $4$ ; les O occupent les autres : ${\displaystyle \left(\genfrac{}{}{0ex}{}{4}{2}\right)}=6$ (BBOO, BOBO, BOOB, OBBO, OBOB, OOBB).

Une urne contient $10$ boules numérotées de $1$ à $10$. On tire $3$ boules. Nombre de tirages possibles :

1. successivement avec remise (on note les numéros dans l’ordre) :
   L’ordre compte et les répétitions sont possibles : $3$-uplets, ${10}^3=1000$.
2. successivement sans remise :
   L’ordre compte, sans répétition : $10\times 9\times 8=720$.
3. simultanément :
   Ni ordre ni répétition : ${\displaystyle \left(\genfrac{}{}{0ex}{}{10}{3}\right)}={\displaystyle \frac{720}{3!}}=120$. Chaque tirage simultané correspond à $3!=6$ tirages successifs sans remise.

Dans un quadrillage, on va de $A(0;0)$ à $B(6;4)$ par pas unitaires vers la droite ou vers le haut. On note $C(2;3)$.

1. Nombre de chemins de $A$ à $B$ :
   $10$ pas dont $4$ vers le haut : ${\displaystyle \left(\genfrac{}{}{0ex}{}{10}{4}\right)}=210$.
2. Justifier le nombre de chemins de $A$ à $B$ qui passent par $C$ :
   Rédaction attendue. Un chemin passant par $C$ est formé d’un chemin de $A$ à $C$ suivi d’un chemin de $C$ à $B$, et ces deux morceaux se choisissent indépendamment. De $A$ à $C$ : $5$ pas dont $3$ vers le haut, soit ${\displaystyle \left(\genfrac{}{}{0ex}{}{5}{3}\right)}=10$ chemins. De $C$ à $B$ : $4$ pas vers la droite et $1$ vers le haut, soit ${\displaystyle \left(\genfrac{}{}{0ex}{}{5}{1}\right)}=5$ chemins. Par le principe multiplicatif : $10\times 5=50$ chemins passent par $C$.
3. Nombre de chemins de $A$ à $B$ qui évitent $C$ :
   Par passage au complémentaire : $210-50=160$.

Lettres répétées et double dénombrement.

1. Le mot PAPAYE compte deux P, deux A, un Y et un E. Nombre d’anagrammes :
   Places des P : ${\displaystyle \left(\genfrac{}{}{0ex}{}{6}{2}\right)}=15$ ; places des A parmi les $4$ restantes : ${\displaystyle \left(\genfrac{}{}{0ex}{}{4}{2}\right)}=6$ ; Y et E occupent les $2$ dernières places dans un ordre quelconque : $2$. Total : $15\times 6\times 2=180$.
2. Une classe compte $n$ filles et $n$ garçons. Démontrer, en comptant de deux façons les paires d’élèves, que ${\displaystyle \left(\genfrac{}{}{0ex}{}{2n}{2}\right)}$ $=2{\displaystyle \left(\genfrac{}{}{0ex}{}{n}{2}\right)}+n^2$. Contrôle pour $n=6$ : ${\displaystyle \left(\genfrac{}{}{0ex}{}{12}{2}\right)}=$
   Rédaction attendue. Une paire d’élèves est une partie à $2$ éléments des $2n$ élèves : il y en a ${\displaystyle \left(\genfrac{}{}{0ex}{}{2n}{2}\right)}$. Comptons-les autrement, en trois familles disjointes : deux filles (${\displaystyle \left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ paires), deux garçons (${\displaystyle \left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ paires), une fille et un garçon ($n\times n=n^2$ paires, principe multiplicatif). Par le principe additif, ${\displaystyle \left(\genfrac{}{}{0ex}{}{2n}{2}\right)}$ $=2{\displaystyle \left(\genfrac{}{}{0ex}{}{n}{2}\right)}+n^2$. Contrôle pour $n=6$ : ${\displaystyle \left(\genfrac{}{}{0ex}{}{12}{2}\right)}=66$ et $2\times 15+36=66$.