Dénombrement

Pourquoi étudier le dénombrement ?

Le problème fondamental

Imagine la situation suivante : tu dois créer un mot de passe de 4 caractères parmi les 26 lettres de l'alphabet. Combien de mots de passe différents peux-tu créer ? La réponse n'est pas évidente, et pourtant c'est une question très concrète. Si on t'autorise à répéter les lettres, ce n'est pas le même problème que si on l'interdit. Et si l'ordre n'a pas d'importance (par exemple, quand on choisit un comité de 4 personnes parmi 26), c'est encore un autre problème.

Dénombrer, c'est compter le nombre d'éléments d'un ensemble fini, sans avoir à les lister un par un. C'est un problème fondamental en mathématiques, et il apparaît dans énormément de domaines. Voyons lesquels :

En probabilités : quand on veut calculer la probabilité d'un événement \(A\) dans une situation d'équiprobabilité, on utilise la formule \(P(A) = \frac{\text{nombre de cas favorables}}{\text{nombre de cas possibles}}\). Pour appliquer cette formule, il faut savoir compter les cas favorables et les cas possibles. Sans dénombrement, pas de probabilités !

En informatique : combien de mots de passe de 8 caractères peut-on former ? Si un pirate teste tous les mots de passe possibles (attaque par force brute), combien de temps cela prendrait-il ? La réponse dépend directement du nombre de mots de passe possibles, donc du dénombrement.

En biologie : une séquence d'ADN est formée de 4 bases (A, T, G, C). Combien de séquences différentes de longueur \(n\) peut-on former ? Pour \(n = 20\), la réponse est \(4^{20} \approx 10^{12}\), soit plus de mille milliards de possibilités. Cela explique la diversité génétique !

En physique statistique : le nombre de configurations microscopiques d'un système détermine son entropie, une grandeur fondamentale de la thermodynamique. Là encore, il faut savoir compter.

L'idée directrice

Bonne nouvelle : même si les applications sont variées, tout le chapitre repose sur une seule question fondamentale que tu dois te poser systématiquement face à chaque problème de dénombrement :

Ces deux questions (oui ou non pour chacune) donnent quatre cas possibles, et à chaque cas correspond un outil mathématique précis. Voici le tableau récapitulatif : apprends-le par cœur, c'est la colonne vertébrale du chapitre.

Ne t'inquiète pas si tu ne comprends pas encore toutes les formules. On va les construire une par une, en partant à chaque fois de l'intuition. À la fin de cette fiche, tu sauras exactement dans quel cas tu te trouves et quelle formule appliquer.

L'idée avant la formule

Avant de plonger dans les définitions formelles, construisons l'intuition avec des exemples très concrets. L'objectif de cette section est que tu comprennes le raisonnement derrière chaque formule, avant même de la voir.

Le principe fondamental : le principe multiplicatif

Le principe multiplicatif est la base absolue de tout le chapitre. Si tu ne devais retenir qu'une seule chose, ce serait celle-ci.

Le principe multiplicatif se généralise naturellement : si on fait \(k\) choix successifs avec \(n_1\) possibilités pour le premier, \(n_2\) pour le deuxième, etc., le nombre total de résultats est \(n_1 \times n_2 \times \cdots \times n_k\).

Avec ou sans répétition : la grande distinction

Maintenant, voyons comment les deux questions (ordre ? répétition ?) donnent des situations très différentes, à travers trois exemples.

Le cours formel

On formalise maintenant rigoureusement tout ce qu'on a vu intuitivement. Chaque notion est définie, démontrée, et illustrée.

Cardinal d'un ensemble fini

Opérations ensemblistes et dénombrement

Quand on dénombre, on travaille souvent avec des réunions, intersections, et complémentaires d'ensembles. Voici les règles de calcul associées.

Produit cartésien

\(p\)-listes (ou \(p\)-uplets)

Permutations et factorielle

Arrangements (sans répétition)

Combinaisons

C'est l'outil le plus important du chapitre, et celui qui tombe le plus souvent au bac. Maîtrise-le parfaitement !

Propriétés fondamentales des combinaisons

Cette formule permet de construire le célèbre triangle de Pascal ligne par ligne, chaque nombre étant la somme des deux nombres au-dessus de lui :

Formule du binôme de Newton

La boîte à outils : Réflexes pour le bac

Cette section est ta check-list avant chaque exercice de dénombrement. Lis-la, relis-la, et apprends-la par cœur.

Exercices

Exercice 1 ★☆☆ : Échauffement : listes et produit cartésien

1. Un mot de passe est formé de 3 lettres majuscules suivies de 2 chiffres. Combien de mots de passe possibles ?

2. On lance 4 dés à 6 faces (distinguables). Combien de résultats possibles ?

3. Combien de nombres de 4 chiffres (de 1000 à 9999) sont pairs ?

4. Un QCM comporte 10 questions, chacune avec 4 réponses possibles (une seule cochée par question). Combien de grilles de réponses possibles ?

Exercice 2 ★☆☆ : Calculs de combinaisons

Calculer sans calculatrice :

1. \(\binom{6}{2}\)
2. \(\binom{8}{3}\)
3. \(\binom{10}{4}\)
4. \(\binom{7}{0}\)
5. \(\binom{12}{11}\)
6. \(\binom{100}{98}\)

Exercice 3 ★☆☆ : Permutations et anagrammes

1. Combien d'anagrammes du mot « LYCEE » peut-on former ? (Attention aux lettres répétées.)

2. De combien de manières peut-on ranger 8 livres tous différents sur une étagère ?

3. 5 personnes s'assoient autour d'une table ronde. De combien de façons ? (Deux dispositions identiques par rotation sont considérées comme une seule.)

Exercice 4 ★☆☆ : Triangle de Pascal et formule de Pascal

1. Construire les lignes \(n = 0\) à \(n = 8\) du triangle de Pascal.

2. Vérifier la formule de Pascal sur l'exemple \(\binom{7}{3} = \binom{6}{2}+\binom{6}{3}\).

3. Calculer \(\displaystyle\sum_{k=0}^{6}\binom{6}{k}\) de deux façons (par le triangle, puis par la formule).

4. En déduire \(\displaystyle\sum_{k=0}^{6}(-1)^k\binom{6}{k}\).

Exercice 5 ★★☆ : Binôme de Newton

1. Développer \((2x+1)^4\) à l'aide de la formule du binôme.

2. Quel est le coefficient de \(x^3\) dans le développement de \((1-3x)^6\) ?

3. Montrer que \(\displaystyle\sum_{k=0}^{n}\binom{n}{k}2^k = 3^n\).

4. Montrer que \(\displaystyle\sum_{k=0}^{n}(-1)^k\binom{n}{k}3^k = (-2)^n\).

Exercice 6 ★★☆ : Compter par le complémentaire

1. Combien de nombres entiers de 1 à 1000 ne sont divisibles ni par 3, ni par 5 ?

2. Un mot de passe de 6 caractères est formé de lettres minuscules (26 lettres). Combien de mots de passe contiennent au moins une voyelle ?

Exercice 7 ★★☆ : Comités et équipes

Une classe de 35 élèves comprend 20 filles et 15 garçons.

1. De combien de façons peut-on former un comité de 5 élèves ?

2. De combien de façons si le comité doit comprendre exactement 3 filles et 2 garçons ?

3. De combien de façons si le comité doit comprendre au moins une fille ?

4. De combien de façons si le comité doit comprendre au moins une fille et au moins un garçon ?

Exercice 8 ★★☆ : Chemins sur un quadrillage

On se déplace sur un quadrillage de \((0,0)\) à \((5,3)\) en ne faisant que des pas vers la droite (D) ou vers le haut (H).

1. Justifier qu'un chemin est entièrement déterminé par un mot de 8 lettres formé de 5 D et 3 H.

2. En déduire le nombre total de chemins.

3. Combien de chemins passent par le point \((2,1)\) ?

4. Combien de chemins ne passent pas par le point \((2,1)\) ?

Exercice 9 ★★☆ : Jeu de cartes (32 cartes)

On tire simultanément 5 cartes d'un jeu de 32 cartes (8 cartes par couleur : pique, cœur, carreau, trèfle).

1. Combien de mains de 5 cartes peut-on former ?

2. Combien de mains contiennent exactement 2 piques ?

3. Combien de mains contiennent au moins une carte de chaque couleur ?

4. Combien de mains contiennent exactement un as ?

Exercice 10 ★★☆ : Diagonales d'un polygone

1. Un polygone convexe a \(n\) sommets (\(n\geqslant 3\)). Combien de diagonales possède-t-il ?

2. Combien de diagonales a un décagone (10 côtés) ?

3. Combien de triangles peut-on former en utilisant uniquement des sommets du décagone ?

Exercice 11 ★★★ : Démonstrations de cours

1. Démontrer par récurrence que \(\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n\) pour tout \(n\geqslant 0\).

2. Démontrer l'identité de Vandermonde : \(\displaystyle\sum_{k=0}^{p}\binom{m}{k}\binom{n}{p-k} = \binom{m+n}{p}\).

Exercice 12 ★★★ : Tirage et probabilités

Une urne contient 10 boules numérotées de 1 à 10. On tire 4 boules simultanément.

1. Nombre total de tirages possibles ?

2. Combien de tirages contiennent la boule 1 ?

3. Combien contiennent la boule 1 et la boule 2 ?

4. Combien contiennent la boule 1 ou la boule 2 (ou les deux) ?

5. On note \(E\) l'événement « au moins l'une des boules 1 ou 2 est tirée ». En déduire \(P(E)\).

Problème : Les partitions d'un ensemble ★★★

Soit \(E\) un ensemble fini à \(n\) éléments (\(n\geqslant 1\)). On appelle partition de \(E\) en \(k\) parties tout ensemble \(\{A_1,A_2,\ldots,A_k\}\) tel que :

• les \(A_i\) sont non vides,

• les \(A_i\) sont deux à deux disjoints (\(A_i\cap A_j = \varnothing\) si \(i\neq j\)),

• \(A_1 \cup A_2 \cup \cdots \cup A_k = E\).

On note \(S(n,k)\) le nombre de telles partitions.

Partie A : Cas particuliers et premières valeurs

1. Justifier que \(S(n,1) = 1\) pour tout \(n\geqslant 1\).

2. Justifier que \(S(n,n) = 1\) pour tout \(n\geqslant 1\).

3. Calculer \(S(3,2)\) en listant toutes les partitions de \(\{a,b,c\}\) en 2 parties.

4. Calculer \(S(4,2)\) en utilisant la même méthode.

5. Justifier que \(S(n,2) = 2^{n-1}-1\) pour tout \(n\geqslant 2\).

Partie B : Relation de récurrence

Soit \(n\geqslant 2\) et \(2\leqslant k\leqslant n\). On fixe un élément \(x\in E\).

1. Supposons que \(\{x\}\) forme à lui seul une partie. Montrer que le nombre de telles partitions est \(S(n-1,k-1)\).

2. Supposons que \(x\) est dans une partie avec d'autres éléments. Montrer que le nombre de telles partitions est \(k\cdot S(n-1,k)\).

3. En déduire : \(S(n,k) = S(n-1,k-1) + k\cdot S(n-1,k)\).

4. Construire le tableau de \(S(n,k)\) pour \(1\leqslant n\leqslant 6\) et \(1\leqslant k\leqslant n\).

Partie C : Lien avec les surjections

On note \(\mathrm{Surj}(n,k)\) le nombre de surjections d'un ensemble à \(n\) éléments vers un ensemble à \(k\) éléments.

1. Montrer que \(\mathrm{Surj}(n,k) = k!\cdot S(n,k)\).

2. Vérifier que le nombre total de fonctions est \(k^n\).

3. (Bonus) Montrer par inclusion-exclusion : \(\mathrm{Surj}(n,k) = \sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n\), et en déduire une formule explicite pour \(S(n,k)\).

Corrigés détaillés

Chaque corrigé est entièrement rédigé comme on l'attendrait dans une copie de bac ou de concours.

Corrigé : Exercice 1

1. Analyse de la situation. Un mot de passe est formé de 3 lettres majuscules suivies de 2 chiffres. L'ordre des caractères compte (le mot de passe ABC12 n'est pas le même que BAC12), et les répétitions sont autorisées (on peut avoir AAA11).

   On est dans la situation d'un produit cartésien de 5 ensembles :

   • Les 3 premières positions : chacune choisie dans \(\{A, B, \ldots, Z\}\) (26 possibilités).

   • Les 2 dernières positions : chacune choisie dans \(\{0, 1, \ldots, 9\}\) (10 possibilités).

   Par le principe multiplicatif :

   \[\begin{aligned}26 \times 26 \times 26 \times 10 \times 10 &= 26^3 \times 10^2\\&= 17\,576 \times 100 = \boldsymbol{1\,757\,600}\end{aligned}\]

   Il y a donc 1 757 600 mots de passe possibles.

2. Analyse. Chaque dé peut donner un résultat parmi \(\{1, 2, 3, 4, 5, 6\}\). Les 4 dés étant distinguables (on parle du dé n^o1, du dé n^o2, etc.), le résultat global est un quadruplet \((d_1, d_2, d_3, d_4)\), c'est-à-dire une 4-liste de \(\{1,\ldots,6\}\).

   Le nombre de résultats possibles est :

   \[6^4 = 6 \times 6 \times 6 \times 6 = \boldsymbol{1\,296}\]

3. Analyse. Un nombre de 4 chiffres s'écrit \(\overline{abcd}\) où \(a\) est le chiffre des milliers, \(b\) celui des centaines, \(c\) celui des dizaines, \(d\) celui des unités.

   Pour que ce nombre soit compris entre 1000 et 9999 : \(a \in \{1, 2, \ldots, 9\}\) (9 choix, car \(a \neq 0\)).

   Pour \(b\) et \(c\) : aucune contrainte particulière, donc \(b, c \in \{0, 1, \ldots, 9\}\) (10 choix chacun).

   Pour que le nombre soit pair, il faut que le dernier chiffre soit pair : \(d \in \{0, 2, 4, 6, 8\}\) (5 choix).

   Par le principe multiplicatif :

   \[9 \times 10 \times 10 \times 5 = \boldsymbol{4\,500}\]

   Il y a 4 500 nombres de 4 chiffres qui sont pairs.

4. Analyse. Pour chaque question, l'élève coche exactement une réponse parmi 4. Les 10 questions sont indépendantes. Une grille de réponses est donc une 10-liste de \(\{A, B, C, D\}\) (ou \(\{1, 2, 3, 4\}\), peu importe).

   Le nombre de grilles possibles est :

   \[4^{10} = \boldsymbol{1\,048\,576}\]

   C'est plus d'un million de grilles ! Cela montre qu'en répondant au hasard, la probabilité d'avoir tout juste est \(\frac{1}{1\,048\,576} \approx 0{,}000\,001\), soit quasiment nulle.

Corrigé : Exercice 2

Pour chaque calcul, on utilise la formule \(\binom{n}{p} = \frac{n(n-1)\cdots(n-p+1)}{p!}\) en choisissant le plus petit entre \(p\) et \(n-p\).

1. \(\binom{6}{2} = \dfrac{6 \times 5}{2 \times 1} = \dfrac{30}{2} = \boldsymbol{15}\)

   Vérification : les sous-ensembles à 2 éléments de \(\{1,2,3,4,5,6\}\) sont \(\{1,2\}, \{1,3\}, \ldots, \{5,6\}\). On peut les compter : il y en a bien 15.

2. \(\binom{8}{3} = \dfrac{8 \times 7 \times 6}{3 \times 2 \times 1} = \dfrac{336}{6} = \boldsymbol{56}\)
3. \(\binom{10}{4} = \dfrac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = \dfrac{5\,040}{24} = \boldsymbol{210}\)
4. \(\binom{7}{0} = \boldsymbol{1}\)

   Justification : il n'y a qu'une seule façon de choisir 0 éléments dans un ensemble : ne rien choisir. Par la formule : \(\binom{7}{0} = \frac{7!}{0! \cdot 7!} = \frac{1}{1} = 1\).

5. \(\binom{12}{11} = \binom{12}{1} = \boldsymbol{12}\)

   Justification : par la propriété de symétrie, \(\binom{12}{11} = \binom{12}{12-11} = \binom{12}{1} = 12\). Intuitivement : choisir 11 éléments parmi 12 revient à choisir le seul élément qu'on ne prend pas. Il y a 12 façons de faire.

6. \(\binom{100}{98} = \binom{100}{2} = \dfrac{100 \times 99}{2 \times 1} = \dfrac{9\,900}{2} = \boldsymbol{4\,950}\)

   On a utilisé la symétrie (\(\binom{100}{98} = \binom{100}{2}\)) pour simplifier considérablement le calcul. Sans cette astuce, il aurait fallu manipuler \(\frac{100!}{98! \cdot 2!}\), ce qui est beaucoup plus lourd.

Corrigé : Exercice 3

1. Anagrammes de LYCEE. Le mot LYCEE comporte 5 lettres : L, Y, C, E, E. Toutes les lettres sont distinctes sauf la lettre E qui apparaît 2 fois.

   Si toutes les lettres étaient distinctes, le nombre d'anagrammes serait \(5! = 120\). Mais puisque la lettre E est répétée 2 fois, chaque anagramme est comptée \(2! = 2\) fois (car échanger les deux E entre eux donne le même mot visible). On divise donc par \(2!\) :

   \[\frac{5!}{2!} = \frac{120}{2} = \boldsymbol{60}\]

   Le mot LYCEE admet 60 anagrammes.

2. Ranger 8 livres. Ranger 8 livres tous différents sur une étagère revient à choisir un ordre pour ces 8 livres. C'est une permutation de 8 éléments :

   \[\begin{aligned}8! &= 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1\\&= \boldsymbol{40\,320}\end{aligned}\]

3. Table ronde. Pour 5 personnes autour d'une table ronde, on considère que deux dispositions obtenues l'une de l'autre par rotation sont identiques.

   Méthode : On fixe une personne à une place (par exemple Alice reste en haut de la table). Les 4 personnes restantes occupent les 4 places restantes, d'où \(4!\) dispositions.

   Justification formelle : En ligne, il y aurait \(5! = 120\) dispositions. Mais chaque disposition circulaire correspond à \(5\) dispositions en ligne (une pour chaque rotation). Donc le nombre de dispositions circulaires est :

   \[\frac{5!}{5} = (5-1)! = 4! = \boldsymbol{24}\]

   De manière générale, le nombre de façons de placer \(n\) personnes autour d'une table ronde est \((n-1)!\).

Corrigé : Exercice 4

1. Le triangle de Pascal de \(n=0\) à \(n=8\), construit grâce à la formule de Pascal (\(\binom{n}{p} = \binom{n-1}{p-1}+\binom{n-1}{p}\)) :

   \(n\backslash p\)	0	1	2	3	4	5	6	7	8
   0	1
   1	1	1
   2	1	2	1
   3	1	3	3	1
   4	1	4	6	4	1
   5	1	5	10	10	5	1
   6	1	6	15	20	15	6	1
   7	1	7	21	35	35	21	7	1
   8	1	8	28	56	70	56	28	8	1

   Chaque nombre est la somme des deux nombres situés juste au-dessus de lui (un à gauche, un à droite). Les bords sont toujours égaux à 1.

2. On vérifie : \(\binom{6}{2} + \binom{6}{3} = 15 + 20 = 35\). D'autre part, \(\binom{7}{3} = \frac{7\times 6\times 5}{3\times 2\times 1} = \frac{210}{6} = 35\). On a bien \(\binom{7}{3} = \binom{6}{2}+\binom{6}{3} = 35\). ✓

3. Première méthode (par le triangle) : On lit la ligne \(n=6\) et on additionne :

   \[1 + 6 + 15 + 20 + 15 + 6 + 1 = 64\]

   Deuxième méthode (par la formule) : On sait que \(\sum_{k=0}^{n}\binom{n}{k} = 2^n\). Pour \(n=6\) :

   \[\sum_{k=0}^{6}\binom{6}{k} = 2^6 = 64 \quad ✓\]

   Les deux méthodes donnent bien le même résultat.

4. On utilise le binôme de Newton avec \(a=1\) et \(b=-1\) :

   \[\begin{aligned}(1+(-1))^6 &= \sum_{k=0}^{6}\binom{6}{k}\cdot 1^{6-k}\cdot (-1)^k\\&= \sum_{k=0}^{6}(-1)^k\binom{6}{k}\end{aligned}\]

   Or \((1-1)^6 = 0^6 = 0\). Donc :

   \[\sum_{k=0}^{6}(-1)^k\binom{6}{k} = \boldsymbol{0}\]

   Cela signifie que la somme des coefficients de rang pair (\(\binom{6}{0}+\binom{6}{2}+\binom{6}{4}+\binom{6}{6} = 1+15+15+1 = 32\)) est égale à la somme des coefficients de rang impair (\(\binom{6}{1}+\binom{6}{3}+\binom{6}{5} = 6+20+6 = 32\)). Leur différence vaut bien 0.

Corrigé : Exercice 5

1. On applique la formule du binôme de Newton à \((2x+1)^4\) avec \(a = 2x\) et \(b = 1\) :

   \[\begin{aligned}(2x+1)^4 &= \sum_{k=0}^{4}\binom{4}{k}(2x)^{4-k}\cdot 1^k \\ &= \binom{4}{0}(2x)^4 + \binom{4}{1}(2x)^3 + \binom{4}{2}(2x)^2 + \binom{4}{3}(2x)^1 + \binom{4}{4}(2x)^0 \\ &= 1\cdot 16x^4 + 4\cdot 8x^3 + 6\cdot 4x^2 + 4\cdot 2x + 1\cdot 1 \\ &= \boldsymbol{16x^4 + 32x^3 + 24x^2 + 8x + 1}\end{aligned}\]

2. On développe \((1-3x)^6\) avec \(a=1\) et \(b=-3x\) :

   \[\begin{aligned}(1-3x)^6 &= \sum_{k=0}^{6}\binom{6}{k}\cdot 1^{6-k}\cdot (-3x)^k\\&= \sum_{k=0}^{6}\binom{6}{k}(-3)^k x^k\end{aligned}\]

   Le coefficient de \(x^3\) correspond au terme \(k = 3\) :

   \[\binom{6}{3}(-3)^3 = 20 \times (-27) = \boldsymbol{-540}\]

3. On veut montrer que \(\sum_{k=0}^{n}\binom{n}{k}2^k = 3^n\).

   On applique le binôme de Newton à \((1+2)^n\) avec \(a=1\) et \(b=2\) :

   \[(1+2)^n = \sum_{k=0}^{n}\binom{n}{k}\cdot 1^{n-k}\cdot 2^k = \sum_{k=0}^{n}\binom{n}{k}\,2^k\]

   Or \((1+2)^n = 3^n\). Donc \(\displaystyle\sum_{k=0}^{n}\binom{n}{k}\,2^k = 3^n\). \(\square\)

4. On veut montrer que \(\sum_{k=0}^{n}(-1)^k\binom{n}{k}3^k = (-2)^n\).

   On applique le binôme à \((1+(-3))^n\) avec \(a=1\) et \(b=-3\) :

   \[\begin{aligned}(1-3)^n &= \sum_{k=0}^{n}\binom{n}{k}\cdot 1^{n-k}\cdot(-3)^k\\&= \sum_{k=0}^{n}\binom{n}{k}(-1)^k\cdot 3^k\\&= \sum_{k=0}^{n}(-1)^k\binom{n}{k}\,3^k\end{aligned}\]

   Or \((1-3)^n = (-2)^n\). D'où le résultat. \(\square\)

Corrigé : Exercice 6

1. Énoncé : combien d'entiers de 1 à 1000 ne sont divisibles ni par 3, ni par 5 ?

   On note \(A\) l'ensemble des multiples de 3 dans \(\{1,\ldots,1000\}\) et \(B\) l'ensemble des multiples de 5.

   Calcul des cardinaux :

   • \(\Card(A) = \lfloor 1000/3 \rfloor = 333\) (le plus grand multiple de 3 inférieur ou égal à 1000 est \(333\times 3 = 999\)).

   • \(\Card(B) = \lfloor 1000/5 \rfloor = 200\) (le plus grand multiple de 5 est \(200\times 5 = 1000\)).

   • \(A \cap B\) = multiples de 15 (car \(\mathrm{ppcm}(3,5) = 15\)) : \(\Card(A\cap B) = \lfloor 1000/15\rfloor = 66\).

   Application de l'inclusion-exclusion :

   \[\begin{aligned}\Card(A\cup B) &= \Card(A) + \Card(B) - \Card(A\cap B)\\&= 333 + 200 - 66 = 467\end{aligned}\]

   \(A\cup B\) est l'ensemble des entiers divisibles par 3 ou par 5 (ou les deux). Le complémentaire de \(A\cup B\) est l'ensemble des entiers qui ne sont divisibles ni par 3, ni par 5 :

   \[1000 - 467 = \boldsymbol{533}\]

2. Énoncé : mot de passe de 6 lettres minuscules, combien contiennent au moins une voyelle ?

   Stratégie : on utilise le complémentaire. « Au moins une voyelle » est le complémentaire de « aucune voyelle » (c'est-à-dire uniquement des consonnes).

   Calculs :

   • Nombre total de mots de passe de 6 lettres : \(26^6 = 308\,915\,776\).

   • Nombre de mots de passe sans aucune voyelle : les 5 voyelles (a, e, i, o, u) étant exclues, il reste 21 consonnes. Chaque position a 21 choix : \(21^6 = 85\,766\,121\).

   Résultat :

   \[\begin{aligned}26^6 - 21^6 &= 308\,915\,776 - 85\,766\,121\\&= \boldsymbol{223\,149\,655}\end{aligned}\]

Corrigé : Exercice 7

Rappel : classe de 35 élèves, 20 filles (F) et 15 garçons (G).

1. On forme un comité de 5 élèves. Un comité est un sous-ensemble de la classe (l'ordre ne compte pas, pas de répétition). C'est une combinaison :

   \[\begin{aligned}\binom{35}{5} &= \frac{35\times 34\times 33\times 32\times 31}{5!}\\&= \frac{35\times 34\times 33\times 32\times 31}{120} = \boldsymbol{324\,632}\end{aligned}\]

2. On veut exactement 3 filles ET 2 garçons. On décompose en deux choix indépendants :

   • Choisir 3 filles parmi 20 : \(\binom{20}{3} = \frac{20\times 19\times 18}{6} = 1\,140\) façons.

   • Choisir 2 garçons parmi 15 : \(\binom{15}{2} = \frac{15\times 14}{2} = 105\) façons.

   Par le principe multiplicatif (les deux choix sont indépendants) :

   \[\binom{20}{3}\times\binom{15}{2} = 1\,140\times 105 = \boldsymbol{119\,700}\]

3. On veut au moins une fille. Le complémentaire est « aucune fille », c'est-à-dire un comité de 5 garçons :

   \[\binom{15}{5} = \frac{15\times 14\times 13\times 12\times 11}{120} = 3\,003\]

   Donc le nombre de comités avec au moins une fille est :

   \[\binom{35}{5} - \binom{15}{5} = 324\,632 - 3\,003 = \boldsymbol{321\,629}\]

4. On veut au moins une fille ET au moins un garçon. On retire du total les comités « que des filles » et « que des garçons » :

   • Comités de 5 filles : \(\binom{20}{5} = 15\,504\).

   • Comités de 5 garçons : \(\binom{15}{5} = 3\,003\).

   Ces deux cas sont disjoints (un comité ne peut pas être « que des filles » et « que des garçons » en même temps). Donc :

   \[324\,632 - 15\,504 - 3\,003 = \boldsymbol{306\,125}\]

Corrigé : Exercice 8

1. Pour aller de \((0,0)\) à \((5,3)\) en ne se déplaçant que vers la droite (D) ou vers le haut (H), on doit effectuer exactement 5 pas vers la droite (pour passer de l'abscisse 0 à l'abscisse 5) et 3 pas vers le haut (pour passer de l'ordonnée 0 à l'ordonnée 3), soit 8 pas au total.

   Un chemin est entièrement déterminé par l'ordre dans lequel on effectue ces 8 pas. C'est donc un mot de 8 lettres composé de 5 lettres D et 3 lettres H.

   Exemple : DDHDDHHD signifie « droite, droite, haut, droite, droite, haut, haut, droite ».

2. Le nombre de tels mots est le nombre de façons de choisir les 3 positions des H parmi les 8 positions (les positions restantes seront automatiquement des D). C'est une combinaison :

   \[\begin{aligned}\binom{8}{3} &= \frac{8\times 7\times 6}{3\times 2\times 1} = \frac{336}{6}\\&= \boldsymbol{56} \text{ chemins}\end{aligned}\]

   (On aurait également pu choisir les 5 positions des D : \(\binom{8}{5} = \binom{8}{3} = 56\).)

3. Un chemin passant par \((2,1)\) se décompose en :

   • Un chemin de \((0,0)\) à \((2,1)\) : il faut 2 pas D et 1 pas H, soit 3 pas. Nombre de chemins : \(\binom{3}{1} = 3\).

   • Un chemin de \((2,1)\) à \((5,3)\) : il faut 3 pas D et 2 pas H, soit 5 pas. Nombre de chemins : \(\binom{5}{2} = 10\).

   Par le principe multiplicatif (les deux portions sont indépendantes) :

   \[3 \times 10 = \boldsymbol{30} \text{ chemins passant par }(2,1)\]

4. Les chemins ne passant pas par \((2,1)\) sont les chemins totaux moins ceux passant par \((2,1)\) :

   \[56 - 30 = \boldsymbol{26} \text{ chemins}\]

Corrigé : Exercice 9

1. Un tirage simultané de 5 cartes parmi 32 est un sous-ensemble à 5 éléments (l'ordre ne compte pas) :

   \[\binom{32}{5} = \frac{32\times 31\times 30\times 29\times 28}{120} = \boldsymbol{201\,376}\]

2. On veut exactement 2 piques. On décompose le choix :

   • 2 cartes parmi les 8 piques : \(\binom{8}{2} = 28\) façons.

   • 3 cartes parmi les \(32 - 8 = 24\) non-piques : \(\binom{24}{3} = \frac{24\times 23\times 22}{6} = 2\,024\) façons.

   Total : \(28 \times 2\,024 = \boldsymbol{56\,672}\).

3. Au moins une carte de chaque couleur. Avec 5 cartes et 4 couleurs, cela signifie qu'exactement une couleur est représentée par 2 cartes et les trois autres par 1 carte chacune.

   • Choix de la couleur « doublée » : 4 façons.

   • 2 cartes dans cette couleur : \(\binom{8}{2} = 28\) façons.

   • 1 carte dans chacune des 3 autres couleurs : \(8 \times 8 \times 8 = 8^3 = 512\) façons.

   Total : \(4\times 28\times 512 = \boldsymbol{57\,344}\).

4. Exactement un as. Il y a 4 as dans le jeu de 32 cartes (un par couleur).

   • 1 as parmi 4 : \(\binom{4}{1} = 4\) façons.

   • 4 cartes parmi les \(32 - 4 = 28\) non-as : \(\binom{28}{4} = 20\,475\) façons.

   Total : \(4 \times 20\,475 = \boldsymbol{81\,900}\).

Corrigé : Exercice 10

1. Un polygone convexe à \(n\) sommets possède des diagonales (segments reliant deux sommets non consécutifs) et des côtés (segments reliant deux sommets consécutifs).

   Le nombre total de segments reliant 2 sommets quelconques parmi \(n\) est \(\binom{n}{2}\) (on choisit 2 sommets, l'ordre ne compte pas).

   Parmi ces segments, \(n\) sont des côtés du polygone. Les autres sont des diagonales. Donc :

   \[\begin{aligned}\text{Nombre de diagonales} &= \binom{n}{2} - n\\&= \frac{n(n-1)}{2} - n = \frac{n^2 - n - 2n}{2}\\&= \boldsymbol{\frac{n(n-3)}{2}}\end{aligned}\]

2. Pour un décagone (\(n = 10\)) : \(\frac{10\times(10-3)}{2} = \frac{10\times 7}{2} = \boldsymbol{35}\) diagonales.

3. Le nombre de triangles dont les sommets sont des sommets du décagone est le nombre de façons de choisir 3 sommets parmi 10 (trois points non alignés d'un polygone convexe forment toujours un triangle) :

   \[\binom{10}{3} = \frac{10\times 9\times 8}{6} = \boldsymbol{120}\]

Corrigé : Exercice 11

1. Démontrons par récurrence sur \(n\) que \(\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n\) pour tout \(n\geqslant 0\).

   Initialisation (\(n = 0\)) : \(\displaystyle\sum_{k=0}^{0}\binom{0}{k} = \binom{0}{0} = 1\). D'autre part, \(2^0 = 1\). Donc la propriété est vraie au rang 0. ✓

   Hérédité : Soit \(n\geqslant 0\). Supposons que \(\sum_{k=0}^{n}\binom{n}{k} = 2^n\) (hypothèse de récurrence). Montrons que \(\sum_{k=0}^{n+1}\binom{n+1}{k} = 2^{n+1}\).

   On sépare le premier et le dernier terme, puis on applique la formule de Pascal aux termes centraux :

   \[\begin{aligned}\sum_{k=0}^{n+1}\binom{n+1}{k} &= \binom{n+1}{0} + \sum_{k=1}^{n}\binom{n+1}{k} + \binom{n+1}{n+1} \\ &= 1 + \sum_{k=1}^{n}\left[\binom{n}{k-1} + \binom{n}{k}\right] + 1 \quad\text{(formule de Pascal)}\end{aligned}\]

   On développe la somme en séparant les deux termes :

   \[\begin{aligned}&= 1 + \sum_{k=1}^{n}\binom{n}{k-1} + \sum_{k=1}^{n}\binom{n}{k} + 1\end{aligned}\]

   Dans la première somme, on pose \(j = k-1\) (quand \(k\) va de 1 à \(n\), \(j\) va de 0 à \(n-1\)) :

   \[\begin{aligned}&= 1 + \sum_{j=0}^{n-1}\binom{n}{j} + \sum_{k=1}^{n}\binom{n}{k} + 1\end{aligned}\]

   Or \(\sum_{j=0}^{n-1}\binom{n}{j} = \sum_{j=0}^{n}\binom{n}{j} - \binom{n}{n} = 2^n - 1\) (par HR).

   Et \(\sum_{k=1}^{n}\binom{n}{k} = \sum_{k=0}^{n}\binom{n}{k} - \binom{n}{0} = 2^n - 1\) (par HR).

   Donc :

   \[\begin{aligned}\sum_{k=0}^{n+1}\binom{n+1}{k} &= 1 + (2^n - 1)\\&\quad {}+ (2^n - 1) + 1 = 2\cdot 2^n = 2^{n+1}\end{aligned}\]

   La propriété est vraie au rang \(n+1\).

   Conclusion : par le principe de récurrence, \(\sum_{k=0}^{n}\binom{n}{k} = 2^n\) pour tout \(n\geqslant 0\). \(\square\)

2. Identité de Vandermonde : Preuve combinatoire.

   Considérons un ensemble \(E\) de \(m+n\) éléments, partitionné en deux sous-ensembles disjoints : \(A\) contenant \(m\) éléments et \(B\) contenant \(n\) éléments.

   On veut choisir \(p\) éléments dans \(E\). Le nombre de façons de le faire est \(\binom{m+n}{p}\).

   Comptons autrement, en distinguant selon le nombre \(k\) d'éléments pris dans \(A\) :

   • Si on prend \(k\) éléments dans \(A\) : \(\binom{m}{k}\) façons.

   • Il faut alors prendre \(p-k\) éléments dans \(B\) : \(\binom{n}{p-k}\) façons.

   • Le nombre de choix avec exactement \(k\) éléments dans \(A\) est \(\binom{m}{k}\binom{n}{p-k}\).

   En sommant sur toutes les valeurs possibles de \(k\) (de 0 à \(p\)), et comme ces cas sont disjoints :

   \[\binom{m+n}{p} = \sum_{k=0}^{p}\binom{m}{k}\binom{n}{p-k} \qquad \square\]

   (Convention : \(\binom{m}{k} = 0\) si \(k > m\), et \(\binom{n}{p-k} = 0\) si \(p-k > n\), ce qui gère automatiquement les cas où \(k\) serait trop grand ou trop petit.)

Corrigé : Exercice 12

1. Un tirage simultané de 4 boules parmi 10 est un sous-ensemble de \(\{1,\ldots,10\}\) à 4 éléments :

   \[\begin{aligned}\binom{10}{4} &= \frac{10\times 9\times 8\times 7}{4\times 3\times 2\times 1}\\&= \frac{5\,040}{24} = \boldsymbol{210}\end{aligned}\]

2. On veut les tirages contenant la boule 1. Si la boule 1 est dans le tirage, il reste à choisir 3 boules parmi les 9 restantes :

   \[\binom{9}{3} = \frac{9\times 8\times 7}{6} = \boldsymbol{84}\]

3. On veut les tirages contenant les boules 1 et 2. Si les boules 1 et 2 sont fixées, il reste à choisir 2 boules parmi les 8 restantes :

   \[\binom{8}{2} = \frac{8\times 7}{2} = \boldsymbol{28}\]

4. On note \(A\) = « la boule 1 est tirée » et \(B\) = « la boule 2 est tirée ». On cherche \(\Card(A\cup B)\).

   Par la formule d'inclusion-exclusion :

   \[\begin{aligned}\Card(A\cup B) &= \Card(A) + \Card(B) - \Card(A\cap B)\\&= 84 + 84 - 28 = \boldsymbol{140}\end{aligned}\]

   (Remarque : \(\Card(A) = \Card(B) = 84\) par symétrie, car les boules 1 et 2 jouent des rôles symétriques.)

5. On est en situation d'équiprobabilité (tirage simultané). La probabilité de l'événement « au moins l'une des boules 1 ou 2 est tirée » est :

   \[\begin{aligned}P(A\cup B) &= \frac{\Card(A\cup B)}{\Card(\Omega)} = \frac{140}{210}\\&= \frac{2}{3}\\&\approx \boldsymbol{0{,}667}\end{aligned}\]

   Il y a donc environ 2 chances sur 3 de tirer au moins l'une des deux boules.

Corrigé : Problème (Les partitions d'un ensemble)

Partie A : Cas particuliers

1. \(S(n,1)\) est le nombre de partitions de \(E\) en 1 seule partie non vide. La seule possibilité est de prendre \(E\) tout entier : la partition est \(\{E\}\). Donc \(S(n,1) = 1\) pour tout \(n\geqslant 1\).

2. \(S(n,n)\) est le nombre de partitions de \(E\) en \(n\) parties non vides. Comme \(|E| = n\), chaque partie doit contenir exactement 1 élément (sinon on ne pourrait pas avoir \(n\) parties non vides). La seule partition possible est \(\bigl\{\{x_1\},\{x_2\},\ldots,\{x_n\}\bigr\}\). Donc \(S(n,n) = 1\) pour tout \(n\geqslant 1\).

3. On liste toutes les partitions de \(E = \{a,b,c\}\) en 2 parties non vides :

• \(\bigl\{\{a\},\{b,c\}\bigr\}\)
• \(\bigl\{\{b\},\{a,c\}\bigr\}\)
• \(\bigl\{\{c\},\{a,b\}\bigr\}\)

Il y en a exactement 3, donc \(S(3,2) = \boldsymbol{3}\).

4. Partitions de \(\{a,b,c,d\}\) en 2 parties non vides. Classons par tailles :

Type 1+3 : une partie à 1 élément, l'autre à 3. On choisit l'élément isolé : 4 choix. Partitions : \(\bigl\{\{a\},\{b,c,d\}\bigr\}\), \(\bigl\{\{b\},\{a,c,d\}\bigr\}\), \(\bigl\{\{c\},\{a,b,d\}\bigr\}\), \(\bigl\{\{d\},\{a,b,c\}\bigr\}\).

Type 2+2 : deux parties à 2 éléments. Le nombre de façons de partitionner en deux paires est \(\frac{1}{2}\binom{4}{2} = \frac{6}{2} = 3\) (on divise par 2 car les deux parties ne sont pas ordonnées). Partitions : \(\bigl\{\{a,b\},\{c,d\}\bigr\}\), \(\bigl\{\{a,c\},\{b,d\}\bigr\}\), \(\bigl\{\{a,d\},\{b,c\}\bigr\}\).

Total : \(S(4,2) = 4 + 3 = \boldsymbol{7}\).

5. Une partition de \(E\) en 2 parties est de la forme \(\{A, E\setminus A\}\) avec \(A\neq\varnothing\) et \(A\neq E\). Le nombre de sous-ensembles \(A\) vérifiant ces conditions est \(2^n - 2\) (on retire l'ensemble vide et \(E\) lui-même des \(2^n\) sous-ensembles de \(E\)). Mais chaque partition est comptée deux fois car \(\{A, E\setminus A\} = \{E\setminus A, A\}\). On divise par 2 :

Vérification : \(S(3,2) = 2^2 - 1 = 3\) ✓ \(S(4,2) = 2^3 - 1 = 7\) ✓

Partie B : Relation de récurrence

6. On fixe \(x\in E\) et on suppose que \(\{x\}\) forme à lui seul une des \(k\) parties de la partition. Les \(n-1\) éléments restants (\(E\setminus\{x\}\)) doivent alors être partitionnés en \(k-1\) parties non vides. Le nombre de façons de le faire est, par définition, \(S(n-1,k-1)\).

7. Supposons que \(x\) appartient à une partie contenant au moins un autre élément. Si on retire \(x\) de cette partie, la partie reste non vide (elle avait au moins 2 éléments), et on obtient une partition de \(E\setminus\{x\}\) (\(n-1\) éléments) en \(k\) parties non vides. Il y a \(S(n-1,k)\) telles partitions.

Réciproquement, à chaque partition de \(E\setminus\{x\}\) en \(k\) parties, on peut réinsérer \(x\) dans l'une des \(k\) parties. Il y a donc \(k\) façons de le réinsérer, ce qui donne \(k\cdot S(n-1,k)\) partitions de ce type.

8. Les deux cas (question 6 et question 7) sont disjoints (soit \(\{x\}\) est une partie, soit \(x\) est avec d'autres éléments) et exhaustifs (il n'y a pas d'autre possibilité). En les additionnant :

9. Tableau construit ligne par ligne grâce à la récurrence, avec \(S(n,1)=1\) et \(S(n,n)=1\) comme conditions initiales :

Vérification : \(S(5,3) = S(4,2) + 3\cdot S(4,3) = 7 + 3\times 6 = 25\) ✓

Partie C : Lien avec les surjections

10. Une surjection \(f: E\to\{1,\ldots,k\}\) définit une partition de \(E\) en \(k\) parties étiquetées : \(A_i = f^{-1}(\{i\})\). Les \(A_i\) sont non vides (car \(f\) est surjective), disjoints, et recouvrent \(E\). Réciproquement, toute partition \(\{A_1,\ldots,A_k\}\) non ordonnée peut être étiquetée de \(k!\) façons (une par bijection de \(\{A_1,\ldots,A_k\}\) vers \(\{1,\ldots,k\}\)), donnant \(k!\) surjections distinctes. Donc :

11. Le nombre total de fonctions de \(E\) (\(n\) éléments) vers \(F\) (\(k\) éléments) est \(k^n\). En effet, pour chaque élément de \(E\), on choisit son image parmi les \(k\) éléments de \(F\) : c'est une \(n\)-liste de \(F\), il y en a \(k^n\). ✓

12. Soit \(B_i\) l'ensemble des fonctions \(f: E\to\{1,\ldots,k\}\) telles que \(i\notin\mathrm{Im}(f)\) (la valeur \(i\) n'est jamais atteinte). Les fonctions non surjectives sont exactement celles de \(B_1\cup\cdots\cup B_k\).

Par inclusion-exclusion, pour calculer \(\Card(B_{i_1}\cap\cdots\cap B_{i_j})\) : ce sont les fonctions dont l'image évite les valeurs \(i_1,\ldots,i_j\), donc l'image est dans un ensemble à \(k-j\) éléments. Le nombre de telles fonctions est \((k-j)^n\). Il y a \(\binom{k}{j}\) façons de choisir les \(j\) valeurs évitées.

Par la formule d'inclusion-exclusion généralisée :

Donc :

(Le terme \(j=0\) donne \(\binom{k}{0}k^n = k^n\), qui correspond au total.)

En combinant avec la question 10 :