Avant de commencer5 questions pour vérifier tes bases
Ton parcours dans ce chapitre
Compter commence par décrire ce qui change entre deux résultats. Tu peux lister un petit cas, dessiner, prendre un indice et recommencer : ces étapes sont du raisonnement mathématique.
Pour repartir des bases. \(\{a,b\}\) désigne un ensemble : l'ordre ne compte pas. \((a,b)\) désigne un couple : sa première et sa deuxième position jouent des rôles distincts. \(3^2\) signifie \(3\times3\) ; \(3!\) signifie \(3\times2\times1\). Ces notations seront construites dans le cours.
Les pauses proposent deux indices et une explication consultables librement. Après une réponse aidée, la variante permet d'essayer à nouveau. Les exercices 1, 2, 4, 6, 7 et 8 prolongent les étapes centrales.
Socle et prolongements. Le dénombrement, les combinaisons et les preuves de Pascal et de la somme des coefficients relèvent du programme de Terminale applicable en 2026–2027. Le binôme de Newton, les coefficients multinomiaux, Vandermonde et les partitions sont des prolongements guidés ; leur mémorisation n'est pas un préalable au cours.
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. Le dénombrement est donc utile dans ce modèle d'équiprobabilité.
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. Ce calcul donne le nombre de suites de bases possibles dans ce modèle ; il ne décrit pas, à lui seul, la diversité génétique réelle.
En physique : on peut compter les différentes répartitions de particules entre des cases dans un modèle discret. C'est une autre application du même raisonnement.
L'idée directrice
Pour choisir une méthode, commence par décrire ce que tu comptes. Deux questions reviennent souvent :
Les réponses orientent vers les outils du tableau. Elles ne suffisent pas toujours : certaines contraintes demandent aussi de distinguer plusieurs cas ou de compter par le complémentaire. Voici le tableau récapitulatif : utilise-le comme un repère, puis justifie le choix de chaque formule avec la situation.
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. Les exemples et les exercices t'aideront à justifier le choix d'une méthode.
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 permet de compter des résultats construits par choix successifs. Pour l'appliquer, il faut préciser le nombre de possibilités à chaque étape.
Plus généralement, supposons que chaque résultat corresponde à une succession de \(k\) choix. À l'étape \(i\), il y a \(n_i\) possibilités, quel que soit le chemin suivi auparavant. Le nombre total de résultats est alors \(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
Une combinaison sert lorsque seul le groupe choisi compte. Nous allons comprendre pourquoi effacer l'ordre conduit à diviser.
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 :
Lire le schéma : la place des chiffres suit l'ordre A, B, C. Par exemple 010 signifie « B seul ». Chaque partie apparaît dans exactement une colonne.
Construire une ligne de Pascal avec un algorithme
Une liste Python conserve un ordre : l'élément de position \(p\) représente \(\binom np\). On commence par la ligne 0 : [1]. Pour fabriquer la suivante, on place 1 aux deux extrémités et on additionne les voisins de l'ancienne ligne.
def ligne_pascal(n):
ligne = [1]
for rang in range(n):
suivante = [1]
for p in range(1, len(ligne)):
suivante.append(ligne[p-1] + ligne[p])
suivante.append(1)
ligne = suivante
return ligneL'entrée est un entier \(n\geqslant0\). On utilise une nouvelle liste pour que tous les calculs lisent l'ancienne ligne, avant son remplacement. Ainsi ligne_pascal(4) renvoie [1, 4, 6, 4, 1].
Pour aller plus loin : binôme de Newton
La boîte à outils : Réflexes pour le bac
Cette section rassemble des repères. Devant un exercice, explique d'abord ce que tu comptes ; le tableau t'aide ensuite à choisir une méthode.
Exercices
Exercice 1 ★☆☆ : Échauffement : listes et produit cartésien
Un mot de passe est formé de 3 lettres majuscules suivies de 2 chiffres. Combien de mots de passe possibles ?
On lance 4 dés à 6 faces (distinguables). Combien de résultats possibles ?
Combien de nombres de 4 chiffres (de 1000 à 9999) sont pairs ?
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 :
- \(\binom{6}{2}\)
- \(\binom{8}{3}\)
- \(\binom{10}{4}\)
- \(\binom{7}{0}\)
- \(\binom{12}{11}\)
- \(\binom{100}{98}\)
Exercice 3 ★☆☆ : Permutations et anagrammes
Combien d'anagrammes du mot « LYCEE » peut-on former ? (Attention aux lettres répétées.)
De combien de manières peut-on ranger 8 livres tous différents sur une étagère ?
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
Construire les lignes \(n = 0\) à \(n = 8\) du triangle de Pascal.
Vérifier la formule de Pascal sur l'exemple \(\binom{7}{3} = \binom{6}{2}+\binom{6}{3}\).
Calculer \(\displaystyle\sum_{k=0}^{6}\binom{6}{k}\) de deux façons (par le triangle, puis par la formule).
En déduire \(\displaystyle\sum_{k=0}^{6}(-1)^k\binom{6}{k}\).
Exercice 5 ★★☆ : Binôme de Newton
Développer \((2x+1)^4\) à l'aide de la formule du binôme.
Quel est le coefficient de \(x^3\) dans le développement de \((1-3x)^6\) ?
Montrer que \(\displaystyle\sum_{k=0}^{n}\binom{n}{k}2^k = 3^n\).
Montrer que \(\displaystyle\sum_{k=0}^{n}(-1)^k\binom{n}{k}3^k = (-2)^n\).
Exercice 6 ★★☆ : Compter par le complémentaire
Combien de nombres entiers de 1 à 1000 ne sont divisibles ni par 3, ni par 5 ?
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.
De combien de façons peut-on former un comité de 5 élèves ?
De combien de façons si le comité doit comprendre exactement 3 filles et 2 garçons ?
De combien de façons si le comité doit comprendre au moins une fille ?
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).
Justifier qu'un chemin est entièrement déterminé par un mot de 8 lettres formé de 5 D et 3 H.
En déduire le nombre total de chemins.
Combien de chemins passent par le point \((2,1)\) ?
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).
Combien de mains de 5 cartes peut-on former ?
Combien de mains contiennent exactement 2 piques ?
Combien de mains contiennent au moins une carte de chaque couleur ?
Combien de mains contiennent exactement un as ?
Exercice 10 ★★☆ : Diagonales d'un polygone
Un polygone convexe a \(n\) sommets (\(n\geqslant 3\)). Combien de diagonales possède-t-il ?
Combien de diagonales a un décagone (10 côtés) ?
Combien de triangles peut-on former en utilisant uniquement des sommets du décagone ?
Exercice 11 ★★★ : Démonstrations de cours
Démontrer par récurrence que \(\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n\) pour tout \(n\geqslant 0\).
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.
Nombre total de tirages possibles ?
Combien de tirages contiennent la boule 1 ?
Combien contiennent la boule 1 et la boule 2 ?
Combien contiennent la boule 1 ou la boule 2 (ou les deux) ?
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
Justifier que \(S(n,1) = 1\) pour tout \(n\geqslant 1\).
Justifier que \(S(n,n) = 1\) pour tout \(n\geqslant 1\).
Calculer \(S(3,2)\) en listant toutes les partitions de \(\{a,b,c\}\) en 2 parties.
Calculer \(S(4,2)\) en utilisant la même méthode.
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\).
Supposons que \(\{x\}\) forme à lui seul une partie. Montrer que le nombre de telles partitions est \(S(n-1,k-1)\).
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)\).
En déduire : \(S(n,k) = S(n-1,k-1) + k\cdot S(n-1,k)\).
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.
Montrer que \(\mathrm{Surj}(n,k) = k!\cdot S(n,k)\).
Vérifier que le nombre total de fonctions est \(k^n\).
(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é explique le choix de la méthode et les étapes du calcul.
Corrigé : Exercice 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
ABC12n'est pas le même queBAC12), et les répétitions sont autorisées (on peut avoirAAA11).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\\[.35em]&= 17\,576 \times 100\\[.35em]&= \boldsymbol{1\,757\,600}\end{aligned}\]Il y a donc 1 757 600 mots de passe possibles.
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é no1, du dé no2, 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 :
\[\begin{aligned}6^4 &= 6 \times 6 \times 6 \times 6\\[.35em]&= \boldsymbol{1\,296}\end{aligned}\]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.
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}\]Si chaque question a une seule bonne réponse et si les réponses sont choisies indépendamment et uniformément parmi les quatre propositions, la probabilité d'avoir tout juste est \(1/4^{10}\), soit environ \(9{,}54\times10^{-7}\). Elle est très petite, mais strictement positive.
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\).
- \[\begin{aligned}\binom{6}{2} &= \dfrac{6 \times 5}{2 \times 1}\\[.35em]&= \dfrac{30}{2}\\[.35em]&= \boldsymbol{15}\end{aligned}\]
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.
- \[\begin{aligned}\binom{8}{3} &= \dfrac{8 \times 7 \times 6}{3 \times 2 \times 1}\\[.35em]&= \dfrac{336}{6}\\[.35em]&= \boldsymbol{56}\end{aligned}\]
- \[\begin{aligned}\binom{10}{4} &= \dfrac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1}\\[.35em]&= \dfrac{5\,040}{24}\\[.35em]&= \boldsymbol{210}\end{aligned}\]
- \(\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 :
\[\begin{aligned}\binom{7}{0} &= \frac{7!}{0! \cdot 7!}\\[.35em]&= \frac{1}{1}\\[.35em]&= 1 .\end{aligned}\] - \[\begin{aligned}\binom{12}{11} &= \binom{12}{1}\\[.35em]&= \boldsymbol{12}\end{aligned}\]
Justification : par la propriété de symétrie,
\[\begin{aligned}\binom{12}{11} &= \binom{12}{12-11}\\[.35em]&= \binom{12}{1}\\[.35em]&= 12 .\end{aligned}\]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.
- \[\begin{aligned}\binom{100}{98} &= \binom{100}{2}\\[.35em]&= \dfrac{100 \times 99}{2 \times 1}\\[.35em]&= \dfrac{9\,900}{2}\\[.35em]&= \boldsymbol{4\,950}\end{aligned}\]
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
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!\) :
\[\begin{aligned}\frac{5!}{2!} &= \frac{120}{2}\\[.35em]&= \boldsymbol{60}\end{aligned}\]Le mot LYCEE admet 60 anagrammes.
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\\[.35em]&= \boldsymbol{40\,320}\end{aligned}\]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 :
\[\begin{aligned}\frac{5!}{5} &= (5-1)!\\[.35em]&= 4!\\[.35em]&= \boldsymbol{24}\end{aligned}\]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
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.
On vérifie :
\[\begin{aligned}\binom{6}{2} + \binom{6}{3} &= 15 + 20\\[.35em]&= 35 .\end{aligned}\]D'autre part,
\[\begin{aligned}\binom{7}{3} &= \frac{7\times 6\times 5}{3\times 2\times 1}\\[.35em]&= \frac{210}{6}\\[.35em]&= 35 .\end{aligned}\]On a bien
\[\begin{aligned}\binom{7}{3} &= \binom{6}{2}+\binom{6}{3}\\[.35em]&= 35 .\end{aligned}\]✓
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.
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\\[.35em]&= \sum_{k=0}^{6}(-1)^k\binom{6}{k}\end{aligned}\]Or
\[\begin{aligned}(1-1)^6 &= 0^6\\[.35em]&= 0 .\end{aligned}\]Donc :
\[\sum_{k=0}^{6}(-1)^k\binom{6}{k} = \boldsymbol{0}\]Cela signifie que la somme des coefficients de rang pair (
\[\begin{aligned}\binom{6}{0}+\binom{6}{2}+\binom{6}{4}+\binom{6}{6} &= 1+15+15+1\\[.35em]&= 32\end{aligned}\]) est égale à la somme des coefficients de rang impair (
\[\begin{aligned}\binom{6}{1}+\binom{6}{3}+\binom{6}{5} &= 6+20+6\\[.35em]&= 32\end{aligned}\]). Leur différence vaut bien 0.
Corrigé : Exercice 5
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\\[.35em]&= \binom{4}{0}(2x)^4 + \binom{4}{1}(2x)^3 + \binom{4}{2}(2x)^2\\[.35em]&\quad {}+ \binom{4}{3}(2x)^1 + \binom{4}{4}(2x)^0\\[.35em]&= 1\cdot 16x^4 + 4\cdot 8x^3 + 6\cdot 4x^2 + 4\cdot 2x + 1\cdot 1\\[.35em]&= \boldsymbol{16x^4 + 32x^3 + 24x^2 + 8x + 1}\end{aligned}\]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\\[.35em]&= \sum_{k=0}^{6}\binom{6}{k}(-3)^k x^k\end{aligned}\]Le coefficient de \(x^3\) correspond au terme \(k = 3\) :
\[\begin{aligned}\binom{6}{3}(-3)^3 &= 20 \times (-27)\\[.35em]&= \boldsymbol{-540}\end{aligned}\]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\) :
\[\begin{aligned}(1+2)^n &= \sum_{k=0}^{n}\binom{n}{k}\cdot 1^{n-k}\cdot 2^k\\[.35em]&= \sum_{k=0}^{n}\binom{n}{k}\,2^k\end{aligned}\]Or \((1+2)^n = 3^n\). Donc \(\displaystyle\sum_{k=0}^{n}\binom{n}{k}\,2^k = 3^n\). \(\square\)
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\\[.35em]&= \sum_{k=0}^{n}\binom{n}{k}(-1)^k\cdot 3^k\\[.35em]&= \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
É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 :
- \[\begin{aligned}\Card(A) &= \lfloor 1000/3 \rfloor\\[.35em]&= 333\end{aligned}\]
(le plus grand multiple de 3 inférieur ou égal à 1000 est \(333\times 3 = 999\)).
- \[\begin{aligned}\Card(B) &= \lfloor 1000/5 \rfloor\\[.35em]&= 200\end{aligned}\]
(le plus grand multiple de 5 est \(200\times 5 = 1000\)).
\(A \cap B\) = multiples de 15 (car \(\mathrm{ppcm}(3,5) = 15\)) :
\[\begin{aligned}\Card(A\cap B) &= \lfloor 1000/15\rfloor\\[.35em]&= 66 .\end{aligned}\]
Application de l'inclusion-exclusion :
\[\begin{aligned}\Card(A\cup B) &= \Card(A) + \Card(B) - \Card(A\cap B)\\[.35em]&= 333 + 200 - 66\\[.35em]&= 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}\]É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\\[.35em]&= \boldsymbol{223\,149\,655}\end{aligned}\]
Corrigé : Exercice 7
Rappel : classe de 35 élèves, 20 filles (F) et 15 garçons (G).
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!}\\[.35em]&= \frac{35\times 34\times 33\times 32\times 31}{120}\\[.35em]&= \boldsymbol{324\,632}\end{aligned}\]On veut exactement 3 filles ET 2 garçons. On décompose en deux choix indépendants :
Choisir 3 filles parmi 20 :
\[\begin{aligned}\binom{20}{3} &= \frac{20\times 19\times 18}{6}\\[.35em]&= 1\,140\end{aligned}\]façons.
Choisir 2 garçons parmi 15 :
\[\begin{aligned}\binom{15}{2} &= \frac{15\times 14}{2}\\[.35em]&= 105\end{aligned}\]façons.
Par le principe multiplicatif (chaque choix du premier groupe peut être associé à chaque choix du second) :
\[\begin{aligned}\binom{20}{3}\times\binom{15}{2} &= 1\,140\times 105\\[.35em]&= \boldsymbol{119\,700}\end{aligned}\]On veut au moins une fille. Le complémentaire est « aucune fille », c'est-à-dire un comité de 5 garçons :
\[\begin{aligned}\binom{15}{5} &= \frac{15\times 14\times 13\times 12\times 11}{120}\\[.35em]&= 3\,003\end{aligned}\]Donc le nombre de comités avec au moins une fille est :
\[\begin{aligned}\binom{35}{5} - \binom{15}{5} &= 324\,632 - 3\,003\\[.35em]&= \boldsymbol{321\,629}\end{aligned}\]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
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 ».
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 :
\[\begin{aligned}\binom{8}{5} &= \binom{8}{3}\\[.35em]&= 56 .\end{aligned}\])
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)\]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
Un tirage simultané de 5 cartes parmi 32 est un sous-ensemble à 5 éléments (l'ordre ne compte pas) :
\[\begin{aligned}\binom{32}{5} &= \frac{32\times 31\times 30\times 29\times 28}{120}\\[.35em]&= \boldsymbol{201\,376}\end{aligned}\]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 :
\[\begin{aligned}\binom{24}{3} &= \frac{24\times 23\times 22}{6}\\[.35em]&= 2\,024\end{aligned}\]façons.
Total : \(28 \times 2\,024 = \boldsymbol{56\,672}\).
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 :
\[\begin{aligned}8 \times 8 \times 8 &= 8^3\\[.35em]&= 512\end{aligned}\]façons.
Total : \(4\times 28\times 512 = \boldsymbol{57\,344}\).
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
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\\[.35em]&= \frac{n(n-1)}{2} - n\\[.35em]&= \frac{n^2 - n - 2n}{2}\\[.35em]&= \boldsymbol{\frac{n(n-3)}{2}}\end{aligned}\]Pour un décagone (\(n = 10\)) :
\[\begin{aligned}\frac{10\times(10-3)}{2} &= \frac{10\times 7}{2}\\[.35em]&= \boldsymbol{35}\end{aligned}\]diagonales.
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) :
\[\begin{aligned}\binom{10}{3} &= \frac{10\times 9\times 8}{6}\\[.35em]&= \boldsymbol{120}\end{aligned}\]
Corrigé : Exercice 11
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\)) :
\[\begin{aligned}\displaystyle\sum_{k=0}^{0}\binom{0}{k} &= \binom{0}{0}\\[.35em]&= 1 .\end{aligned}\]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}\\[.35em]&\quad {}+ \binom{n+1}{n+1}\\[.35em]&= 1 + \sum_{k=1}^{n}\left[\binom{n}{k-1} + \binom{n}{k}\right] + 1\\[.35em]&\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
\[\begin{aligned}\sum_{j=0}^{n-1}\binom{n}{j} &= \sum_{j=0}^{n}\binom{n}{j} - \binom{n}{n}\\[.35em]&= 2^n - 1\end{aligned}\](par HR).
Et
\[\begin{aligned}\sum_{k=1}^{n}\binom{n}{k} &= \sum_{k=0}^{n}\binom{n}{k} - \binom{n}{0}\\[.35em]&= 2^n - 1\end{aligned}\](par HR).
Donc :
\[\begin{aligned}\sum_{k=0}^{n+1}\binom{n+1}{k} &= 1 + (2^n - 1) + (2^n - 1) + 1\\[.35em]&= 2\cdot 2^n\\[.35em]&= 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\)
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
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}\\[.35em]&= \frac{5\,040}{24}\\[.35em]&= \boldsymbol{210}\end{aligned}\]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 :
\[\begin{aligned}\binom{9}{3} &= \frac{9\times 8\times 7}{6}\\[.35em]&= \boldsymbol{84}\end{aligned}\]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 :
\[\begin{aligned}\binom{8}{2} &= \frac{8\times 7}{2}\\[.35em]&= \boldsymbol{28}\end{aligned}\]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)\\[.35em]&= 84 + 84 - 28\\[.35em]&= \boldsymbol{140}\end{aligned}\](Remarque :
\[\begin{aligned}\Card(A) &= \Card(B)\\[.35em]&= 84\end{aligned}\]par symétrie, car les boules 1 et 2 jouent des rôles symétriques.)
On suppose que chaque groupe de quatre boules a la même probabilité d'être tiré (boules indiscernables au toucher, tirage uniforme). Le caractère simultané ne suffit pas, à lui seul, à justifier l'équiprobabilité. 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)}\\[.35em]&= \frac{140}{210}\\[.35em]&= \frac{2}{3}\\[.35em]&\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
(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 :
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 :
✓
✓
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 :
| \(n\backslash k\) | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | |||||
| 2 | 1 | 1 | ||||
| 3 | 1 | 3 | 1 | |||
| 4 | 1 | 7 | 6 | 1 | ||
| 5 | 1 | 15 | 25 | 10 | 1 | |
| 6 | 1 | 31 | 90 | 65 | 15 | 1 |
Vérification :
✓
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 :
Fiche mémoire : compter en expliquant
Maîtrise du chapitre
Validation contrôlée
Réponds aux QCM, sélectionne les bonnes propositions ou remets les étapes dans l'ordre. Le site vérifie chaque réponse avant d'ouvrir la balise suivante.