Rédigé et vérifié par un professeur diplômé de l’École Polytechnique, avec un niveau de rigueur pensé pour le lycée et la prépa. Découvrir le professeur
Tu dois compter le nombre de mots de passe possibles, le nombre de mains au poker, ou le nombre de chemins dans un arbre ? Toutes ces questions relèvent du dénombrement — l’art de compter sans lister. Au programme de Terminale spé maths et omniprésent en prépa scientifique, ce chapitre repose sur quelques principes simples mais exige une méthode rigoureuse. Tu trouveras ici : les définitions fondamentales, les principes de comptage, toutes les formules (permutations, arrangements, combinaisons), des exercices corrigés et les pièges classiques à éviter.
Clarification importante. Cette page traite du dénombrement combinatoire au sens des mathématiques (Terminale spé maths et CPGE). À ne pas confondre avec : la cardinalité en théorie des ensembles infinis (dénombrabilité, niveau Master), la grammaire (noms dénombrables/indénombrables), la didactique de la maternelle, l’électronique numérique (logique combinatoire des circuits), ou l’optimisation combinatoire (recherche opérationnelle).
I. Qu’est-ce que le dénombrement ? Définition et vocabulaire
A. Définition
Définition — Dénombrement
Dénombrer un ensemble fini \(E\), c’est déterminer son cardinal, c’est-à-dire le nombre d’éléments qu’il contient, noté \(\mathrm{card}(E)\) ou \(|E|\).
Plus largement, le dénombrement (ou combinatoire) est la branche des mathématiques qui fournit les outils pour compter les éléments d’un ensemble sans avoir à les lister un par un.
L’idée fondamentale est simple : quand un ensemble contient 3 éléments, tu peux les compter sur les doigts. Mais quand il en contient 2 598 960 (le nombre de mains de 5 cartes au poker), il faut des outils plus puissants. C’est exactement ce que fournit le dénombrement.
B. Vocabulaire de base : ensembles, sous-ensembles, p-uplets
Avant de compter, il faut savoir ce qu’on compte. Voici les objets que tu rencontreras dans tout exercice de dénombrement :
| Terme | Notation | Signification | Exemple |
|---|---|---|---|
| Ensemble fini | \(E\) | Collection d’objets distincts | \(E = \{a, b, c, d\}\) |
| Cardinal | \(\mathrm{card}(E)\) ou \(|E|\) | Nombre d’éléments de \(E\) | \(\mathrm{card}(\{a, b, c, d\}) = 4\) |
| Sous-ensemble (partie) | \(A \subset E\) | Sélection d’éléments de \(E\), sans ordre ni répétition | \(\{a, c\} \subset E\) |
| p-uplet (ou p-liste) | \((x_1, x_2, \ldots, x_p)\) | Suite ordonnée de \(p\) éléments (l’ordre compte, les répétitions sont possibles) | \((a, c, a)\) est un 3-uplet |
| Ensemble des parties | \(\mathcal{P}(E)\) | Ensemble de tous les sous-ensembles de \(E\) | \(\mathcal{P}(\{a,b\}) = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}\) |
p-uplet ≠ sous-ensemble. C’est la confusion la plus fréquente en dénombrement. Dans un p-uplet, l’ordre compte et les répétitions sont possibles : \((a, b)\) et \((b, a)\) sont deux p-uplets différents. Dans un sous-ensemble, l’ordre ne compte pas et les répétitions sont impossibles : \(\{a, b\} = \{b, a\}\). Retiens : p-uplet = liste ordonnée, sous-ensemble = paquet non ordonné.
C. À quoi sert le dénombrement ?
Le dénombrement n’est pas un chapitre isolé : c’est un outil transversal utilisé dans de nombreux domaines :
- Probabilités en univers fini : si toutes les issues sont équiprobables, la probabilité d’un événement vaut \(P(A) = \displaystyle\frac{|A|}{|\Omega|}\). Dénombrer \(|A|\) et \(|\Omega|\) est donc la clé de tout calcul.
- Cryptographie et informatique : combien de mots de passe de 8 caractères peut-on former ? Combien de clés de chiffrement ?
- Jeux de hasard : poker (nombre de mains), loto (nombre de grilles), dés, tirages d’urne.
- Génétique : combinaisons de gènes, croisements mendéliens.
- Optimisation : compter les chemins possibles dans un réseau, les emplois du temps réalisables.
La suite du cours te donne les outils pour répondre à toutes ces questions de manière systématique.
II. Les principes fondamentaux du comptage
Toute la combinatoire repose sur deux principes simples — qui correspondent, en langage courant, aux mots « ou » et « puis ».
A. Le principe additif (ou)
Principe additif. Si une action peut être réalisée de \(a\) façons ou de \(b\) façons, et que ces deux cas sont incompatibles (disjoints), alors le nombre total de façons est :
\(a + b\)
Plus généralement, si \(E_1, E_2, \ldots, E_k\) sont des ensembles finis deux à deux disjoints, alors :
\(\mathrm{card}(E_1 \cup E_2 \cup \cdots \cup E_k) = \mathrm{card}(E_1) + \mathrm{card}(E_2) + \cdots + \mathrm{card}(E_k)\)
Exemple. Un restaurant propose 4 entrées et 3 desserts. Si tu choisis une entrée ou un dessert (pas les deux), tu as \(4 + 3 = 7\) choix possibles.
Attention : le principe additif ne s’applique que si les cas sont disjoints. Si les deux ensembles ont des éléments en commun, tu dois utiliser la formule d’inclusion-exclusion :
\(\mathrm{card}(A \cup B) = \mathrm{card}(A) + \mathrm{card}(B) – \mathrm{card}(A \cap B)\)
B. Le principe multiplicatif (puis)
Principe multiplicatif. Si une action se décompose en étapes successives et indépendantes, la première ayant \(a\) issues et la seconde \(b\) issues quel que soit le résultat de la première, alors le nombre total de résultats est :
\(a \times b\)
Plus généralement, si les étapes successives offrent respectivement \(n_1, n_2, \ldots, n_k\) choix, le nombre total de résultats est :
\(n_1 \times n_2 \times \cdots \times n_k\)
Exemple. Un code PIN se compose de 4 chiffres (de 0 à 9). Chaque position offre 10 choix, et les choix sont indépendants. Le nombre total de codes PIN est :
\(10 \times 10 \times 10 \times 10 = 10^4 = 10\,000\)
Ce principe est l’outil le plus puissant du dénombrement : la plupart des formules (permutations, arrangements, combinaisons) en sont des conséquences directes.
C. Nombre d’applications entre deux ensembles finis
Le principe multiplicatif permet de compter immédiatement le nombre d’applications d’un ensemble \(E\) de cardinal \(p\) dans un ensemble \(F\) de cardinal \(n\) :
Propriété. Le nombre d’applications d’un ensemble à \(p\) éléments dans un ensemble à \(n\) éléments est :
\(n^p\)
Chaque élément de \(E\) a \(n\) images possibles dans \(F\), et les choix sont indépendants. Par le principe multiplicatif : \(\underbrace{n \times n \times \cdots \times n}_{p \text{ fois}} = n^p\).
Application. Combien de mots de 3 lettres peut-on former avec l’alphabet (26 lettres), les répétitions étant autorisées ?
C’est le nombre d’applications de \(\{1,2,3\}\) dans un alphabet de 26 lettres : \(26^3 = 17\,576\) mots possibles.
D. 🔴 Le principe des bergers (prépa)
En prépa scientifique, on formalise un principe supplémentaire qui simplifie de nombreux problèmes :
Lemme des bergers (principe de double comptage). Soit \(f : E \to F\) une application telle que chaque élément de \(F\) possède exactement \(k\) antécédents. Alors :
\(\mathrm{card}(E) = k \times \mathrm{card}(F)\)
Ce principe est l’outil central pour démontrer de nombreuses formules de combinatoire (relation entre arrangements et combinaisons, formule du capitaine, etc.). Tu le retrouveras en détail dans les pages dédiées aux arrangements et au coefficient binomial.
Mémo PDF — Combinatoire et dénombrement
Toutes les formules (permutations, arrangements, combinaisons, binôme de Newton) + l’arbre de décision sur une fiche recto-verso prête à imprimer.
📄 Télécharger la fiche PDFIdéal pour réviser la veille du contrôle ou avant une colle.
III. Permutations, arrangements, combinaisons : les formules clés
Maintenant que tu connais les principes, voici les quatre formules fondamentales du dénombrement. Chacune répond à un type de situation bien précis, selon deux critères : l’ordre compte-t-il ? La répétition est-elle possible ?
A. L’arbre de décision : quelle formule choisir ?
Avant de te lancer dans un calcul, pose-toi toujours trois questions dans cet ordre :
- L’ordre des éléments compte-t-il ? (Le tiercé « A, B, C » est-il différent de « C, A, B » ?)
- La répétition est-elle autorisée ? (Peut-on choisir deux fois le même élément ?)
- Combien d’éléments choisit-on parmi combien ? (\(p\) choix parmi \(n\) objets)
| Situation | Ordre ? | Répétition ? | Formule | Exemple type |
|---|---|---|---|---|
| p-uplets (tirages avec remise) | ✅ Oui | ✅ Oui | \(n^p\) | Codes PIN, mots de passe |
| Arrangements (tirages sans remise, ordonnés) | ✅ Oui | ❌ Non | \(A_n^p = \displaystyle\frac{n!}{(n-p)!}\) | Tiercé, podium, classement |
| Permutations (cas \(p = n\)) | ✅ Oui | ❌ Non | \(n!\) | Anagrammes, ordres de passage |
| Combinaisons (tirages sans remise, non ordonnés) | ❌ Non | ❌ Non | \(\displaystyle{n \choose p} = \displaystyle\frac{n!}{p!(n-p)!}\) | Mains de cartes, comités, loterie |
| 🔴 Combinaisons avec répétition (prépa) | ❌ Non | ✅ Oui | \(\displaystyle{n+p-1 \choose p}\) | Répartition d’objets identiques |
Pour approfondir le choix de la bonne formule dans un exercice concret, consulte la fiche méthode « Permutation, arrangement, combinaison ».
B. La factorielle : l’outil de base
Définition — Factorielle. Pour tout entier naturel \(n \geq 1\), on définit \(n\) factorielle par :
\(n! = 1 \times 2 \times 3 \times \cdots \times n = \displaystyle\prod_{k=1}^{n} k\)
Par convention, \(0! = 1\).
Voici les premières valeurs à connaître par cœur :
| \(n\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| \(n!\) | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5 040 | 40 320 | 3 628 800 |
Pourquoi \(0! = 1\) ? Ce n’est pas un « choix arbitraire ». C’est la seule valeur qui rend les formules cohérentes. Par exemple, le nombre de permutations de 0 objets est 1 (il n’y a qu’une seule façon de « ne rien ranger » : ne rien faire). C’est aussi le produit vide, qui vaut 1 par convention mathématique.
C. Les permutations : tout ranger dans un certain ordre
Définition — Permutation. Une permutation d’un ensemble \(E\) à \(n\) éléments est un arrangement de tous les éléments de \(E\) dans un certain ordre.
Le nombre de permutations de \(n\) éléments est :
\(n!\)
Pourquoi ? Pour la première position, tu as \(n\) choix. Pour la deuxième, il reste \(n – 1\) éléments. Pour la troisième, \(n – 2\), et ainsi de suite. Par le principe multiplicatif :
\(n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 = n!\)
Exemple. Combien d’anagrammes du mot « MATHS » existe-t-il (y compris les « mots » sans signification) ?
Le mot « MATHS » contient 5 lettres distinctes. Chaque anagramme est une permutation de ces 5 lettres : \(5! = 120\) anagrammes.
Pour aller plus loin sur les permutations (avec objets identiques, groupes symétriques en prépa), consulte la page dédiée aux permutations.
D. Les arrangements : choisir p parmi n, dans un certain ordre
Définition — Arrangement. Un arrangement de \(p\) éléments parmi \(n\) (avec \(p \leq n\)) est un choix ordonné de \(p\) éléments distincts pris dans un ensemble à \(n\) éléments.
Le nombre d’arrangements est :
\(A_n^p = \displaystyle\frac{n!}{(n-p)!} = n(n-1)(n-2)\cdots(n-p+1)\)
Pourquoi ? Même raisonnement que pour les permutations, mais on s’arrête après \(p\) choix : \(n\) choix pour le 1er, \(n-1\) pour le 2e, …, \(n-p+1\) pour le \(p\)-ième.
Exemple. Dans une course de 12 chevaux, combien de tiercés ordonnés (1er, 2e, 3e) sont possibles ?
\(A_{12}^3 = 12 \times 11 \times 10 = 1\,320\) tiercés possibles.
Lien permutations ↔ arrangements. Une permutation est un arrangement où \(p = n\) (on choisit tous les éléments). En effet, \(A_n^n = \displaystyle\frac{n!}{0!} = n!\).
Pour approfondir (démonstration, exemples avancés, arrangements avec répétition en prépa), voir la page sur les arrangements.
E. Les combinaisons et le coefficient binomial : choisir p parmi n, sans ordre
Définition — Combinaison (coefficient binomial). Une combinaison de \(p\) éléments parmi \(n\) est un choix non ordonné de \(p\) éléments distincts dans un ensemble à \(n\) éléments. C’est un sous-ensemble de cardinal \(p\).
Le nombre de combinaisons, appelé coefficient binomial « \(p\) parmi \(n\) », est :
\(\displaystyle{n \choose p} = \displaystyle\frac{n!}{p!\,(n-p)!}\)
pour \(0 \leq p \leq n\).
D’où vient cette formule ? Un arrangement de \(p\) parmi \(n\) consiste à choisir \(p\) éléments puis à les ordonner. Comme il y a \(p!\) façons d’ordonner \(p\) éléments, on a la relation fondamentale :
\(A_n^p = \displaystyle{n \choose p} \times p! \qquad \Longrightarrow \qquad \displaystyle{n \choose p} = \displaystyle\frac{A_n^p}{p!} = \displaystyle\frac{n!}{p!(n-p)!}\)
Exemple. Au Loto français, on choisit 5 numéros parmi 49 (l’ordre ne compte pas). Le nombre de grilles possibles est :
\(\displaystyle{49 \choose 5} = \displaystyle\frac{49!}{5! \times 44!} = \displaystyle\frac{49 \times 48 \times 47 \times 46 \times 45}{120} = 1\,906\,884\)
Ta probabilité de gagner avec une seule grille : environ 1 chance sur 1,9 million.
Le coefficient binomial possède de nombreuses propriétés (symétrie, formule de Pascal, triangle de Pascal, formule du binôme de Newton…). Tu les trouveras sur la page dédiée au coefficient binomial.
F. Propriétés essentielles du coefficient binomial
Voici les propriétés à connaître dès la Terminale :
Propriétés du coefficient binomial.
- Symétrie : \(\displaystyle{n \choose p} = \displaystyle{n \choose n-p}\)
- Valeurs aux bords : \(\displaystyle{n \choose 0} = \displaystyle{n \choose n} = 1\)
- Formule de Pascal : \(\displaystyle{n \choose p} = \displaystyle{n-1 \choose p-1} + \displaystyle{n-1 \choose p}\) pour \(1 \leq p \leq n-1\)
- Somme totale : \(\displaystyle\sum_{p=0}^{n} \displaystyle{n \choose p} = 2^n\) (nombre total de parties d’un ensemble à \(n\) éléments)
Interprétation de \(2^n\). Un ensemble à \(n\) éléments possède exactement \(2^n\) sous-ensembles (en comptant l’ensemble vide et l’ensemble entier). C’est aussi le principe multiplicatif appliqué ainsi : pour chaque élément, deux choix (le prendre ou ne pas le prendre), soit \(2 \times 2 \times \cdots \times 2 = 2^n\).
IV. Méthodes de résolution : la stratégie en 4 étapes
Connaître les formules ne suffit pas : encore faut-il savoir laquelle utiliser. Voici une méthode systématique pour aborder tout exercice de dénombrement.
Étape 1 — Identifier clairement l’univers
Avant de compter, définis précisément ce que tu comptes. Décris l’ensemble dont tu cherches le cardinal en une phrase complète :
- « Je compte le nombre de comités de 3 personnes parmi 10. » → sous-ensembles, pas d’ordre → combinaisons.
- « Je compte le nombre de classements des 3 premiers parmi 10. » → liste ordonnée → arrangements.
Étape 2 — Se poser les deux questions clés
- L’ordre intervient-il ? (Si \((A,B,C)\) et \((C,A,B)\) sont deux résultats différents → oui.)
- La répétition est-elle possible ? (Un élément peut-il être choisi plusieurs fois ?)
Ces deux réponses t’orientent directement vers la bonne formule dans le tableau de la section III.
Étape 3 — Appliquer la formule (ou décomposer en étapes)
Si la situation ne correspond pas directement à une formule unique, décompose le problème en étapes successives (principe multiplicatif) ou en cas disjoints (principe additif). Un problème complexe est presque toujours la combinaison de plusieurs sous-problèmes simples.
La stratégie du complémentaire. Parfois, il est plus facile de compter ce qu’on ne veut pas et de le retrancher du total. Par exemple, pour compter les mots de passe contenant au moins un chiffre, calcule :
\(\text{(total des mots de passe)} – \text{(mots de passe sans aucun chiffre)}\)
Étape 4 — Vérifier le résultat
Trois réflexes de vérification :
- Ordre de grandeur : le résultat est-il cohérent avec la taille du problème ?
- Cas particulier : si \(p = 0\) ou \(p = n\), le résultat est-il 1 comme attendu ?
- Petit cas : teste la formule sur un petit exemple que tu peux vérifier en listant à la main.
V. Exercices corrigés
Voici 5 exercices progressifs pour t’entraîner. Les corrections sont détaillées pas à pas. Pour un entraînement intensif, consulte la page exercices corrigés de dénombrement.
Exercice 1 — Codes d’accès ★
Énoncé. Un code d’accès est composé de 4 chiffres (de 0 à 9), suivis de 2 lettres majuscules (parmi 26). Les répétitions sont autorisées.
Combien de codes d’accès différents peut-on former ?
Voir la correction
On décompose en étapes successives (principe multiplicatif) :
- Chiffre 1 : 10 choix
- Chiffre 2 : 10 choix
- Chiffre 3 : 10 choix
- Chiffre 4 : 10 choix
- Lettre 1 : 26 choix
- Lettre 2 : 26 choix
Les répétitions sont autorisées et les choix sont indépendants, donc :
\(10^4 \times 26^2 = 10\,000 \times 676 = 6\,760\,000\)
Il y a 6 760 000 codes d’accès possibles.
Exercice 2 — Délégation ★
Énoncé. Une classe de 30 élèves doit élire une délégation de 3 élèves (sans ordre de préférence). Combien de délégations différentes sont possibles ?
Voir la correction
On choisit 3 élèves parmi 30, sans ordre et sans répétition : c’est une combinaison.
\(\displaystyle{30 \choose 3} = \displaystyle\frac{30!}{3! \times 27!} = \displaystyle\frac{30 \times 29 \times 28}{3 \times 2 \times 1} = \displaystyle\frac{24\,360}{6} = 4\,060\)
Il y a 4 060 délégations possibles.
Exercice 3 — Podium sportif ★★
Énoncé. Lors d’une compétition de 20 nageurs, combien de podiums (1er, 2e, 3e) distincts sont possibles ?
Voir la correction
Le podium est ordonné (le 1er n’est pas le 3e) et sans répétition. C’est un arrangement de 3 parmi 20 :
\(A_{20}^3 = 20 \times 19 \times 18 = 6\,840\)
Il y a 6 840 podiums possibles.
Vérification : si la question avait été « combien d’équipes de 3 nageurs ? » (sans ordre), la réponse aurait été \(\displaystyle{20 \choose 3} = \displaystyle\frac{6\,840}{6} = 1\,140\). On vérifie bien que \(A_{20}^3 = \displaystyle{20 \choose 3} \times 3!\).
Exercice 4 — Mots de passe sécurisés ★★
Énoncé. Un mot de passe de 8 caractères est composé de lettres majuscules (26) et de chiffres (10). On impose qu’il contienne au moins un chiffre. Combien de mots de passe valides existe-t-il ?
Voir la correction
On utilise la stratégie du complémentaire.
Total : chaque caractère peut être une lettre ou un chiffre, soit 36 choix. Nombre total de mots de passe de 8 caractères : \(36^8\).
Cas à exclure : les mots de passe sans aucun chiffre (que des lettres). Chaque caractère est une lettre parmi 26 : \(26^8\).
Résultat :
\(36^8 – 26^8 = 2\,821\,109\,907\,456 – 208\,827\,064\,576 = 2\,612\,282\,842\,880\)
Il y a environ 2 612 milliards de mots de passe valides.
Exercice 5 — Distribution de cartes ★★★
Énoncé. On distribue 5 cartes parmi un jeu de 52 cartes. Combien de mains contiennent exactement 2 as ?
Voir la correction
On décompose en deux étapes indépendantes (principe multiplicatif) :
Étape 1 : choisir 2 as parmi les 4 as du jeu (sans ordre) :
\(\displaystyle{4 \choose 2} = \displaystyle\frac{4!}{2! \times 2!} = 6\)
Étape 2 : choisir les 3 cartes restantes parmi les 48 cartes qui ne sont pas des as :
\(\displaystyle{48 \choose 3} = \displaystyle\frac{48 \times 47 \times 46}{6} = 17\,296\)
Résultat : par le principe multiplicatif :
\(\displaystyle{4 \choose 2} \times \displaystyle{48 \choose 3} = 6 \times 17\,296 = 103\,776\)
Il y a 103 776 mains de 5 cartes contenant exactement 2 as.
VI. Erreurs fréquentes et pièges classiques
Le dénombrement est un chapitre où les erreurs de raisonnement sont plus fréquentes que les erreurs de calcul. Voici les pièges les plus courants.
Piège 1 — Confondre arrangement et combinaison
❌ Copie fautive : « On choisit un comité de 3 personnes parmi 10. Le nombre de comités est \(A_{10}^3 = 720\). »
Diagnostic : un comité est un groupe, pas une liste ordonnée. Le comité {Alice, Bob, Clara} est le même que {Clara, Alice, Bob}. L’ordre ne compte pas.
✅ Correction : \(\displaystyle{10 \choose 3} = \displaystyle\frac{720}{6} = 120\) comités.
Piège 2 — Oublier de vérifier si la répétition est possible
❌ Copie fautive : « Un code de 4 chiffres sans répétition donne \(10^4 = 10\,000\) codes. »
Diagnostic : la formule \(n^p\) suppose que la répétition est autorisée. Si les chiffres doivent être distincts, c’est un arrangement.
✅ Correction : \(A_{10}^4 = 10 \times 9 \times 8 \times 7 = 5\,040\) codes sans répétition.
Piège 3 — Compter deux fois le même objet
Erreur type : « Combien d’équipes mixtes de 4 joueurs (au moins 1 homme et 1 femme) parmi 6 hommes et 5 femmes ? On prend les équipes avec 1 femme + celles avec 2 femmes + celles avec 3 femmes + celles avec 4 femmes. » → Correct ici.
Mais attention : si la décomposition en cas n’est pas disjointe, tu comptes des objets en double. Vérifie toujours que tes cas sont mutuellement exclusifs avant d’additionner.
Piège 4 — Simplifier incorrectement les factorielles
❌ Copie fautive : \(\displaystyle\frac{10!}{7!} = \displaystyle\frac{10}{7} \approx 1{,}43\)
Diagnostic : \(10!\) et \(7!\) ne se simplifient pas comme des fractions ordinaires. Il faut développer.
✅ Correction : \(\displaystyle\frac{10!}{7!} = \displaystyle\frac{10 \times 9 \times 8 \times 7!}{7!} = 10 \times 9 \times 8 = 720\)
Piège 5 — Ne pas penser au complémentaire
Erreur type : face à « au moins un… », lister tous les cas (1, puis 2, puis 3…) au lieu de calculer Total \(–\) « aucun ». La stratégie du complémentaire est presque toujours plus rapide quand l’énoncé contient « au moins ».
VII. 🔴 Approfondissement prépa
Cette section s’adresse aux étudiants de CPGE (MPSI, PCSI, MP2I, BCPST). Les notions ci-dessous prolongent le programme de Terminale avec le niveau de rigueur attendu en classe préparatoire.
A. La formule du binôme de Newton
Théorème — Formule du binôme de Newton. Pour tous \(a, b \in \mathbb{R}\) (ou dans un anneau commutatif) et pour tout \(n \in \mathbb{N}\) :
\((a+b)^n = \displaystyle\sum_{k=0}^{n} \displaystyle{n \choose k}\, a^k\, b^{n-k}\)
Cas particuliers utiles :
- \(a = b = 1\) : \(\displaystyle\sum_{k=0}^{n} \displaystyle{n \choose k} = 2^n\) (somme totale des coefficients binomiaux).
- \(a = 1, b = -1\) : \(\displaystyle\sum_{k=0}^{n} (-1)^k \displaystyle{n \choose k} = 0\) (alternance des coefficients binomiaux).
B. Identité de Vandermonde
Théorème — Identité de Vandermonde. Pour tous entiers \(m, n, p\) avec \(0 \leq p \leq m+n\) :
\(\displaystyle\sum_{k=0}^{p} \displaystyle{m \choose k}\displaystyle{n \choose p-k} = \displaystyle{m+n \choose p}\)
Interprétation combinatoire : on choisit \(p\) éléments dans un ensemble de \(m + n\) objets, partitionné en un groupe de \(m\) et un groupe de \(n\). On « répartit » le choix : \(k\) éléments viennent du premier groupe, \(p – k\) du second. En sommant sur toutes les valeurs possibles de \(k\), on obtient le total.
C. Identité de la crosse de hockey
Propriété — Crosse de hockey (hockey stick identity). Pour \(r \leq n\) :
\(\displaystyle\sum_{k=r}^{n} \displaystyle{k \choose r} = \displaystyle{n+1 \choose r+1}\)
Ce nom provient du motif en forme de crosse dessiné dans le triangle de Pascal lorsqu’on additionne les coefficients le long d’une diagonale.
D. Sommes classiques avec les coefficients binomiaux
Ces résultats apparaissent régulièrement dans les sujets de concours :
| Identité | Résultat | Méthode de preuve classique |
|---|---|---|
| \(\displaystyle\sum_{k=0}^{n} \displaystyle{n \choose k}\) | \(2^n\) | Binôme avec \(a = b = 1\) |
| \(\displaystyle\sum_{k=0}^{n} (-1)^k \displaystyle{n \choose k}\) | \(0\) | Binôme avec \(a = 1, b = -1\) |
| \(\displaystyle\sum_{k=0}^{n} k\displaystyle{n \choose k}\) | \(n \cdot 2^{n-1}\) | Formule du capitaine + binôme |
| \(\displaystyle\sum_{k=0}^{n} k^2 \displaystyle{n \choose k}\) | \(n(n+1) \cdot 2^{n-2}\) | Double dérivation du binôme |
E. Combinaisons avec répétition (méthode étoiles et barres)
Théorème. Le nombre de façons de choisir \(p\) éléments parmi \(n\) catégories avec répétition et sans ordre est :
\(\displaystyle{n+p-1 \choose p}\)
Idée de la preuve (étoiles et barres) : on modélise le choix par une ligne de \(p\) étoiles (les objets choisis) et \(n-1\) barres (les séparations entre catégories). Un tel mot contient \(p + (n-1)\) caractères, et il suffit de choisir la position des \(p\) étoiles (ou des \(n-1\) barres) parmi ces \(p + n – 1\) positions.
Exemple. Combien de façons de répartir 10 bonbons identiques dans 4 boîtes distinctes ?
On choisit \(p = 10\) éléments parmi \(n = 4\) catégories avec répétition :
\(\displaystyle{4+10-1 \choose 10} = \displaystyle{13 \choose 10} = \displaystyle{13 \choose 3} = \displaystyle\frac{13 \times 12 \times 11}{6} = 286\)
F. Dénombrement et programmation (Python)
En prépa, les colles et DS peuvent demander d’écrire un programme calculant des quantités combinatoires. Python offre la bibliothèque itertools pour engendrer les objets et le module math pour les calculer :
Fonctions Python utiles :
math.factorial(n): calcule \(n!\)math.comb(n, k): calcule \(\displaystyle{n \choose k}\) (Python 3.8+)math.perm(n, k): calcule \(A_n^k\) (Python 3.8+)itertools.permutations(E, k): engendre les arrangements de \(k\) parmi \(E\)itertools.combinations(E, k): engendre les combinaisons de \(k\) parmi \(E\)itertools.combinations_with_replacement(E, k): engendre les combinaisons avec répétition
VIII. Questions fréquentes
Qu'est-ce que le dénombrement en maths ?
Le dénombrement (ou combinatoire) est la branche des mathématiques qui permet de compter le nombre d’éléments d’un ensemble fini sans les lister un par un. Il repose sur deux principes fondamentaux (additif et multiplicatif) et fournit des formules pour les permutations (\(n!\)), les arrangements (\(A_n^p\)) et les combinaisons (\(\displaystyle{n \choose p}\)).
Quels sont les principes fondamentaux du dénombrement ?
Les deux principes de base sont :
- Le principe additif : si deux cas sont disjoints, on additionne le nombre de possibilités.
- Le principe multiplicatif : si une action se décompose en étapes indépendantes, on multiplie le nombre de choix de chaque étape.
En CPGE, on ajoute le principe des bergers (lemme de double comptage).
Quelle est la différence entre arrangement et combinaison ?
Un arrangement est un choix ordonné (le tiercé A, B, C est différent de C, A, B), tandis qu’une combinaison est un choix non ordonné (le groupe {A, B, C} est le même que {C, A, B}). Formellement, on passe de l’un à l’autre par : \(\displaystyle{n \choose p} = \displaystyle\frac{A_n^p}{p!}\). Tu peux approfondir cette distinction sur la fiche méthode dédiée.
Comment savoir quelle formule utiliser dans un exercice ?
Pose-toi deux questions : (1) L’ordre compte-t-il ? (2) La répétition est-elle autorisée ? Les réponses t’orientent vers la bonne formule. Ordre + pas de répétition = arrangement. Pas d’ordre + pas de répétition = combinaison. Ordre + répétition = p-uplets (\(n^p\)). Consulte l’arbre de décision complet dans la section III de ce cours.
Comment calculer le coefficient binomial k parmi n ?
On utilise la formule \(\displaystyle{n \choose k} = \displaystyle\frac{n!}{k!(n-k)!}\). En pratique, pour éviter de calculer des factorielles trop grandes, on simplifie directement : \(\displaystyle{n \choose k} = \displaystyle\frac{n(n-1) \cdots (n-k+1)}{k!}\). Sur calculatrice, utilise la touche nCr. Plus de détails sur la page coefficient binomial.
Quelle est la différence entre dénombrement et probabilités ?
Le dénombrement est l’outil, les probabilités sont l’application. Le dénombrement permet de compter (« combien de mains de poker possibles ? »). Les probabilités utilisent ces comptages pour calculer des chances (« quelle probabilité d’obtenir un carré d’as ? »). Dans un univers fini équiprobable, la probabilité se calcule comme un rapport de cardinaux : \(P(A) = \displaystyle\frac{|A|}{|\Omega|}\).
Pourquoi 0! vaut-il 1 ?
Par convention, \(0! = 1\) car c’est la seule valeur qui rend les formules cohérentes. Par exemple, \(\displaystyle{n \choose 0} = \displaystyle\frac{n!}{0! \times n!} = 1\) (il n’y a qu’une façon de ne choisir aucun élément). C’est aussi le produit vide, qui vaut 1 par convention universelle en mathématiques.
Le dénombrement tombe-t-il souvent au bac ?
Oui, le dénombrement est régulièrement évalué au bac de spécialité maths, le plus souvent couplé avec les probabilités. Les exercices types portent sur les tirages dans une urne, les jeux de cartes, les mots de passe ou la loi binomiale, qui utilise directement les coefficients binomiaux.
IX. Pour aller plus loin
Tu maîtrises maintenant les fondamentaux du dénombrement : les principes de comptage, le vocabulaire, et les formules des permutations, arrangements et combinaisons. Pour approfondir chaque outil et t’entraîner sérieusement, voici la suite du parcours :
- Choisir la bonne formule : fiche méthode « Permutation, arrangement, combinaison » — l’arbre de décision complet et 4 problèmes types résolus.
- Maîtriser le coefficient binomial : cours complet sur le coefficient binomial — formule de Pascal, triangle interactif, formule du binôme, démonstrations.
- Les arrangements en détail : cours sur les arrangements — démonstration, tiercé, arrangements avec répétition (prépa).
- Les permutations en détail : cours sur les permutations — formule multinomiale, anagrammes avec lettres identiques.
- S’entraîner : exercices corrigés de dénombrement (Tle et Prépa) — 15+ exercices progressifs, du calcul direct au problème type concours.
- Appliquer à la probabilité : cours sur les probabilités — univers fini, équiprobabilité, calculs exploitant le dénombrement.
- La loi binomiale : cours sur la loi binomiale — modèle fondé directement sur les coefficients binomiaux.
Conforme au programme officiel de mathématiques 2025-2026 (Terminale spé maths — programme Eduscol).
