Dénombrement

Vue d'ensemble

Le dénombrement est le chapitre fondateur de la combinatoire en MPSI : il fournit le vocabulaire (cardinal, p-listes, arrangements, combinaisons) et les formules clés (principe multiplicatif, formule du crible, coefficients binomiaux, formule du binôme) qui irriguent les probabilités, l'algèbre linéaire (bases finies) et l'arithmétique (groupes finis). Cette fiche regroupe les 4 théorèmes incontournables, les 4 démonstrations à savoir refaire et les formules canoniques qu'on attend de toi à la khôlle comme au DS.

Au programme MPSI (officiel) — Cardinal d'un ensemble fini, parties d'un ensemble fini, principe additif et principe multiplicatif, p-listes (avec ou sans répétition), arrangements, permutations, combinaisons et coefficients binomiaux, formule de Pascal, formule du binôme de Newton, nombre d'applications et nombre d'injections entre deux ensembles finis.

Prérequis

Manipulation des ensembles : réunion ∪, intersection ∩, complémentaire, produit cartésien ×
Notion d'application, d'injection, de surjection, de bijection
Récurrence simple sur ℕ (on l'utilise dans 3 démos sur 4)

🎯 Accompagnement Majorant

Tu confonds arrangement, combinaison et p-liste ? C'est l'erreur n°1 du chapitre : le mauvais choix de formule fait perdre toute la question (et toute la suite, en probabilités). Nos mentors alumni X · Centrale · Mines te dressent en 1 séance le tableau « ordre / répétition » que tu n'oublieras plus jamais.

Trouver un mentor MPSI →

1. Ensembles finis et cardinal

Définition 1.1 — Ensemble fini, cardinal

Un ensemble $E$ est dit fini s'il existe $n \in N$ et une bijection $φ : {1, 2, \dots, n} \to E$ . L'entier $n$ est alors unique : on l'appelle le cardinal de $E$ , noté $Card (E)$ , $∣ E ∣$ ou $# E$ . Par convention, l'ensemble vide est fini et $∣\emptyset∣ = 0$ .

Définition 1.2 — Premiers cardinaux

$∣\emptyset∣ = 0$ , $∣ {a} ∣ = 1$ pour tout singleton, $∣ {a, b} ∣ = 2$ si $a \neq = b$ , et $∣ {1, 2, \dots, n} ∣ = n$ pour tout $n \in N^{*}$ . Dans toute la fiche on utilisera indifféremment $∣ E ∣$ (compact, usage concours) et $Card (E)$ (académique).

Proposition 1.3 — Cardinal et inclusion

Soient $A, B$ deux parties finies d'un ensemble $E$ . Alors :

Si $A \subset B$ , alors $∣ A ∣ \leq ∣ B ∣$ .
Si $A \subset B$ et $∣ A ∣ = ∣ B ∣$ (avec $B$ fini), alors $A = B$ .
$∣ A ∣ = 0 ⟺ A = \emptyset$ .

Théorème 1.4 — Formule du crible (à 2 termes) ★ À savoir démontrer

Pour toutes parties finies $A, B$ d'un ensemble :

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣.

En particulier, si $A \cap B = \emptyset$ (parties disjointes), on a $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ : c'est le principe additif.

Démonstration (par séparation de A∪B en trois morceaux disjoints)

L'idée est de partitionner $A \cup B$ en trois ensembles deux à deux disjoints, puis d'appliquer le principe additif (cas particulier de la formule, déjà acquis : si $X \cap Y = \emptyset$ alors $∣ X \cup Y ∣ = ∣ X ∣ + ∣ Y ∣$ , conséquence immédiate de la définition de cardinal par bijection avec un segment de ℕ).

Posons :

X = A ∖ B, Y = B ∖ A, Z = A \cap B .

Ces trois ensembles sont deux à deux disjoints (immédiat : un élément de $X$ n'est pas dans $B$ , donc pas dans $Y$ ni dans $Z$ ; idem pour $Y$ et $Z$ ). De plus :

A \cup B = X \cup Y \cup Z, A = X \cup Z, B = Y \cup Z .

Par le principe additif appliqué aux deux dernières décompositions :

∣ A ∣ = ∣ X ∣ + ∣ Z ∣, ∣ B ∣ = ∣ Y ∣ + ∣ Z ∣,

donc $∣ X ∣ = ∣ A ∣ - ∣ Z ∣$ et $∣ Y ∣ = ∣ B ∣ - ∣ Z ∣$ . Et pour la première décomposition :

∣ A \cup B ∣ = ∣ X ∣ + ∣ Y ∣ + ∣ Z ∣ = (∣ A ∣ - ∣ Z ∣) + (∣ B ∣ - ∣ Z ∣) + ∣ Z ∣ = ∣ A ∣ + ∣ B ∣ - ∣ Z ∣,

soit $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ . C.Q.F.D.

Théorème 1.5 — Formule du crible (cas général, n termes)

Pour toutes parties finies $A_{1}, \dots, A_{n}$ :

i = 1 ⋃ n A_{i} = k = 1 \sum n (- 1)^{k - 1} 1 \leq i_{1} < \dots < i_{k} \leq n \sum ∣ A_{i_{1}} \cap \dots \cap A_{i_{k}} ∣.

Pour $n = 3$ : $∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣$ .

💡 Exemple — Multiples de 2 ou de 3 dans ⟦1, 100⟧. Soient

A

(multiples de 2) et

B

(multiples de 3) dans

{1, \dots, 100}

∣ A ∣ = 50

∣ B ∣ = 33

(car

⌊ 100/3 ⌋ = 33

∣ A \cap B ∣

= multiples de 6 =

⌊ 100/6 ⌋ = 16

. D'où

∣ A \cup B ∣ = 50 + 33 - 16 = 67

. Le complémentaire (entiers premiers avec 6 dans cette plage) a donc

100 - 67 = 33

éléments.

Définition 1.6 — Produit cartésien et ses cardinaux

Le produit cartésien de deux ensembles $A$ et $B$ est $A \times B = {(a, b), a \in A, b \in B}$ . Si $A, B$ sont finis, alors :

∣ A \times B ∣ = ∣ A ∣ \cdot ∣ B ∣.

Plus généralement, pour $n$ ensembles finis :

∣ A_{1} \times A_{2} \times \dots \times A_{n} ∣ = ∣ A_{1} ∣ \cdot ∣ A_{2} ∣ \dots ∣ A_{n} ∣.

Théorème 1.7 — Principe multiplicatif

Si une construction se décompose en $p$ étapes successives, l'étape $i$ offrant $n_{i}$ choix indépendamment des choix précédents, alors le nombre total de constructions possibles est :

n_{1} \cdot n_{2} \dots n_{p} .

⚠ Piège #1 du chapitre — l'indépendance des étapes. Le principe multiplicatif n'est valable que si le nombre de choix $n_{i}$ à l'étape $i$ ne dépend pas des choix faits avant. Si tu tires une carte puis une seconde sans remise, l'étape 2 a

51

choix quel que soit le résultat de l'étape 1 — l'indépendance en cardinal est vérifiée, et la formule

52 \times 51

marche. En revanche, si l'étape 2 dépend du nombre de choix selon la nature du résultat précédent, il faut séparer en cas.

2. p-listes, arrangements et permutations

2.1 — p-listes (avec répétition)

Définition 2.1 — p-liste

Soit $E$ un ensemble et $p \in N^{*}$ . Une p-liste (ou p-uplet) d'éléments de $E$ est un élément du produit cartésien $E^{p}$ , c'est-à-dire une suite ordonnée $(x_{1}, x_{2}, \dots, x_{p})$ avec $x_{i} \in E$ pour tout $i$ .

Une p-liste est ordonnée (l'ordre compte) et autorise les répétitions (un même élément de $E$ peut apparaître plusieurs fois).

Théorème 2.2 — Nombre de p-listes

Si $∣ E ∣ = n$ , le nombre de p-listes d'éléments de $E$ est :

∣ E^{p} ∣ = n^{p} .

💡 Exemple — Mots de longueur 5 sur l'alphabet. Le nombre de mots (suites ordonnées, lettres pouvant se répéter) de longueur 5 sur l'alphabet à 26 lettres est

2 6^{5} = 11881376

. Si on impose en plus la première lettre majuscule et les 4 suivantes minuscules : c'est

26 \times 2 6^{4} = 2 6^{5}

toujours (le principe multiplicatif sépare les contraintes).

2.2 — Arrangements (p-listes sans répétition)

Définition 2.3 — Arrangement

Un arrangement de $p$ éléments parmi $n$ (avec $0 \leq p \leq n$ ) est une p-liste $(x_{1}, \dots, x_{p})$ d'éléments deux à deux distincts d'un ensemble $E$ de cardinal $n$ . Autrement dit, c'est une injection de ${1, \dots, p}$ dans $E$ .

Théorème 2.4 — Nombre d'arrangements ★ À savoir démontrer

Le nombre d'arrangements de $p$ éléments parmi $n$ est noté $A_{n}^{p}$ et vaut :

A_{n}^{p} = n (n - 1) (n - 2) \dots (n - p + 1) = \frac{n !}{( n - p )!} .

(produit de $p$ facteurs entiers consécutifs décroissants à partir de $n$ ).

Démonstration (par principe multiplicatif)

Pour construire un arrangement $(x_{1}, x_{2}, \dots, x_{p})$ d'éléments distincts de $E$ (avec $∣ E ∣ = n$ ), procédons par étapes successives :

Étape 1 : choisir $x_{1}$ parmi les $n$ éléments de $E$ → $n$ choix.
Étape 2 : choisir $x_{2}$ parmi les $n - 1$ éléments restants (tous sauf $x_{1}$ ) → $n - 1$ choix.
Étape 3 : choisir $x_{3}$ parmi les $n - 2$ restants → $n - 2$ choix.
…
Étape $p$ : choisir $x_{p}$ parmi les $n - (p - 1) = n - p + 1$ restants → $n - p + 1$ choix.

À chaque étape, le nombre de choix est indépendant des choix précédents (seule compte la quantité d'éléments encore disponibles, qui décroît de $1$ à chaque étape). Par le principe multiplicatif, le nombre total d'arrangements est :

A_{n}^{p} = n \cdot (n - 1) \cdot (n - 2) \dots (n - p + 1) = k = 0 \prod p - 1 (n - k) .

En multipliant numérateur et dénominateur par $(n - p)!$ :

A_{n}^{p} = \frac{n ( n - 1 ) \dots ( n - p + 1 ) \cdot ( n - p )!}{( n - p )!} = \frac{n !}{( n - p )!} .

2.3 — Permutations

Définition 2.5 — Factorielle, permutation

Pour $n \in N$ , la factorielle de $n$ est définie par :

0! = 1, n! = 1 \cdot 2 \cdot 3 \dots n = k = 1 \prod n k pour n \geq 1.

Une permutation d'un ensemble fini $E$ est une bijection de $E$ sur lui-même. Le groupe des permutations de $E$ est noté $S_{E}$ ; lorsque $E = {1, \dots, n}$ , on note simplement $S_{n}$ .

Théorème 2.6 — Nombre de permutations

Si $∣ E ∣ = n$ , le nombre de permutations de $E$ est :

∣ S_{E} ∣ = A_{n}^{n} = n! .

Une permutation est un cas particulier d'arrangement : $p = n$ , donc on choisit tous les éléments dans un ordre donné.

💡 Exemple — Anagrammes de « MAJORANT ». Le mot MAJORANT a 8 lettres toutes distinctes (M, A, J, O, R, A, N, T) — attention, il y a deux A. Pour des lettres toutes distinctes on aurait

8! = 40320

anagrammes ; ici, comme deux A sont indiscernables, on divise par

2!

pour obtenir

8! /2! = 20160

anagrammes. La formule générale (mot à

n

lettres dont la lettre

i

apparaît

n_{i}

fois) est

\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}

(coefficient multinomial, hors-prog mais souvent croisé en khôlle).

⚠ Piège — confondre permutation et arrangement. Permutation = arrangement de

n

parmi

n

, donc on prend tous les éléments. Arrangement avec

p < n

= on n'en prend que

p

. Si l'énoncé dit « ordre des 8 candidats » → permutation (

8!

). S'il dit « podium des 3 premiers parmi 8 » → arrangement (

A_{8}^{3} = 8 \cdot 7 \cdot 6 = 336

), pas

8!

🧑‍🏫 Décortique le tableau ordre/répétition

Tu hésites encore entre p-liste, arrangement et combinaison ? Le tableau de décision à 4 cases (ordre oui/non × répétition oui/non) se mémorise en 20 minutes avec un mentor — et te garantit le bon comptage dans toutes les questions de dénombrement et probabilités du DS.

Réserver une séance ciblée →

3. Combinaisons et coefficients binomiaux

Définition 3.1 — Combinaison, coefficient binomial

Soit $E$ un ensemble de cardinal $n$ et $k \in N$ avec $0 \leq k \leq n$ . Une combinaison de $k$ éléments parmi $n$ (ou k-combinaison) est une partie de $E$ à $k$ éléments. L'ordre est indifférent (un ensemble n'a pas d'ordre) et il n'y a pas de répétition (un ensemble n'a pas de doublons).

Leur nombre est le coefficient binomial $(k n)$ (lu « k parmi n »), également noté $C_{n}^{k}$ :

(k n) = \frac{n !}{k ! ( n - k )!} = \frac{A _{n}^{k}}{k !} = \frac{n ( n - 1 ) \dots ( n - k + 1 )}{k !} .

Par convention, $(k n) = 0$ si $k < 0$ ou $k > n$ .

📝 D'où vient la division par $k!$ ? Une combinaison de

k

éléments donne lieu à

k!

arrangements distincts (on permute les

k

éléments choisis). Donc le nombre d'arrangements de

k

parmi

n

vaut

k!

fois le nombre de combinaisons :

A_{n}^{k} = k! \cdot (k n)

, d'où la formule.

Proposition 3.2 — Premières propriétés des coefficients binomiaux

Bornes : $(0 n) = (n n) = 1$ , $(1 n) = (n - 1 n) = n$ .
Symétrie : $(k n) = (n - k n)$ pour tout $0 \leq k \leq n$ . Justification combinatoire : choisir $k$ éléments à inclure équivaut à choisir $n - k$ éléments à exclure.
Formule du facteur : $k \cdot (k n) = n \cdot (k - 1 n - 1)$ (utile en preuves par récurrence).

Théorème 3.3 — Formule de Pascal ★ À savoir démontrer

Pour tous entiers $n, k$ avec $0 \leq k \leq n - 1$ :

(k n) + (k + 1 n) = (k + 1 n + 1) .

Cette relation est le moteur du triangle de Pascal : chaque case est la somme des deux cases « au-dessus à gauche » et « au-dessus à droite ».

Démonstration (par calcul direct sur les factorielles)

Mettons les deux fractions au même dénominateur :

(k n) + (k + 1 n) = \frac{n !}{k ! ( n - k )!} + \frac{n !}{( k + 1 )! ( n - k - 1 )!} .

Le dénominateur commun naturel est $(k + 1)! (n - k)!$ . On a $(k + 1)! = (k + 1) \cdot k!$ et $(n - k)! = (n - k) \cdot (n - k - 1)!$ . On multiplie donc le premier terme par $\frac{k + 1}{k + 1}$ et le second par $\frac{n - k}{n - k}$ :

(k n) + (k + 1 n) = \frac{n ! ( k + 1 )}{( k + 1 )! ( n - k )!} + \frac{n ! ( n - k )}{( k + 1 )! ( n - k )!} .

Le numérateur commun est $n! [(k + 1) + (n - k)] = n! (n + 1) = (n + 1)!$ . D'où :

(k n) + (k + 1 n) = \frac{( n + 1 )!}{( k + 1 )! ( n - k )!} = \frac{( n + 1 )!}{( k + 1 )! ( n + 1 - ( k + 1 ))!} = (k + 1 n + 1) .

Variante combinatoire (à connaître aussi). Soit $F$ un ensemble à $n + 1$ éléments et $a \in F$ fixé. Les parties de $F$ à $k + 1$ éléments se partitionnent en deux : celles qui contiennent $a$ (au nombre de $(k n)$ , il reste à choisir $k$ éléments parmi les $n$ autres) et celles qui ne contiennent pas $a$ (au nombre de $(k + 1 n)$ , on choisit $k + 1$ éléments parmi les $n$ autres). D'où la formule.

📐 Méthode-type — Démontrer une identité sur les $(k n)$ . Tu disposes de trois approches, à essayer dans cet ordre :

Preuve combinatoire (double comptage). Trouve un ensemble qu'on peut compter de deux façons, l'une donnant le membre de gauche, l'autre le membre de droite. C'est la preuve la plus élégante et celle que les correcteurs adorent.
Calcul direct sur les factorielles. Substituer $(k n) = n! / (k! (n - k)!)$ et manipuler les factorielles. Toujours possible, parfois calculatoire.
Récurrence + formule de Pascal. Si l'identité dépend de $n$ , récurrence sur $n$ , pas d'hérédité utilisant Pascal pour scinder $(k + 1 n + 1)$ . Idéal pour les identités sommatoires.

Théorème 3.4 — Formule du binôme de Newton

Pour tous $a, b \in R$ (ou $C$ , ou plus généralement deux éléments qui commutent) et tout $n \in N$ :

(a + b)^{n} = k = 0 \sum n (k n) a^{k} b^{n - k} .

La somme contient $n + 1$ termes ; les coefficients sont les $(n + 1)$ -uplets du triangle de Pascal à la ligne $n$ .

💡 Exemple — Identités usuelles dérivées du binôme. En spécialisant :

$a = b = 1$ : $k = 0 \sum n (k n) = 2^{n}$ (nombre total de parties d'un ensemble à $n$ éléments).
$a = 1, b = - 1$ : $k = 0 \sum n (- 1)^{k} (k n) = 0$ (pour $n \geq 1$ : autant de parties de cardinal pair que de cardinal impair).
$a = 1, b = x$ : $(1 + x)^{n} = k = 0 \sum n (k n) x^{k}$ (utile en dérivation pour produire d'autres identités).

4. Nombre d'applications, d'injections, de bijections

On veut compter, pour $E$ et $F$ finis avec $∣ E ∣ = p$ et $∣ F ∣ = n$ , les applications $E \to F$ , les injections $E \to F$ , et les bijections $E \to F$ (ce dernier cas n'a de sens que si $∣ E ∣ = ∣ F ∣$ ).

Théorème 4.1 — Nombre d'applications E → F ★ À savoir démontrer

Soient $E, F$ finis avec $∣ E ∣ = p$ et $∣ F ∣ = n$ . Le nombre d'applications de $E$ dans $F$ est :

∣ F (E, F) ∣ = n^{p} = ∣ F ∣^{∣ E ∣} .

Démonstration (par récurrence sur p = |E|)

On démontre par récurrence sur $p = ∣ E ∣$ la propriété :

$H (p)$ : « pour tout ensemble fini $F$ de cardinal $n$ et tout ensemble $E$ de cardinal $p$ , le nombre d'applications $E \to F$ vaut $n^{p}$ ».

Initialisation ( $p = 0$ ) : si $E = \emptyset$ , il existe une et une seule application $\emptyset \to F$ (l'application vide, dont le graphe est vide). On a bien $n^{0} = 1$ . Donc $H (0)$ est vraie.

Hérédité. Supposons $H (p)$ vraie pour un $p \geq 0$ , et soit $E$ de cardinal $p + 1$ . Fixons un élément $a \in E$ et posons $E^{'} = E ∖ {a}$ , de sorte que $∣ E^{'} ∣ = p$ . Une application $f : E \to F$ est entièrement déterminée par :

sa restriction $f ∣_{E^{'}} : E^{'} \to F$ — il y en a $n^{p}$ par hypothèse de récurrence,
la valeur $f (a) \in F$ — il y en a $n$ .

Réciproquement, tout couple (restriction à $E^{'}$ , valeur en $a$ ) définit une unique application $f$ . On a donc une bijection entre $F (E, F)$ et $F (E^{'}, F) \times F$ . Par le principe multiplicatif :

∣ F (E, F) ∣ = ∣ F (E^{'}, F) ∣ \cdot ∣ F ∣ = n^{p} \cdot n = n^{p + 1} .

Donc $H (p + 1)$ est vraie. Par récurrence, $H (p)$ est vraie pour tout $p$ . C.Q.F.D.

📝 Notation $∣ F ∣^{∣ E ∣}$ . La notation

F^{E}

désigne l'ensemble des applications de

E

vers

F

(et non un produit cartésien usuel). Le théorème dit donc

∣ F^{E} ∣ = ∣ F ∣^{∣ E ∣}

: c'est cohérent avec la notation

E^{p} = E \times \dots \times E

(qui est l'ensemble des applications

{1, \dots, p} \to E

, exactement les p-listes).

Théorème 4.2 — Nombre d'injections E → F

Soient $E, F$ finis avec $∣ E ∣ = p$ et $∣ F ∣ = n$ . Le nombre d'injections de $E$ dans $F$ est :

nb d’injections = A_{n}^{p} = n (n - 1) \dots (n - p + 1) = \frac{n !}{( n - p )!}

si $p \leq n$ , et $0$ sinon (impossible d'injecter dans plus petit).

Justification. Une injection ${1, \dots, p} \to F$ est exactement la donnée des images $(f (1), \dots, f (p))$ , qui forment une p-liste d'éléments deux à deux distincts de $F$ : c'est un arrangement de $p$ parmi $n$ .

Corollaire 4.3 — Nombre de bijections E → F

Si $∣ E ∣ = ∣ F ∣ = n$ , une application est bijective ssi elle est injective (cardinaux égaux, argument de tiroir). Le nombre de bijections $E \to F$ est donc :

A_{n}^{n} = n! .

En particulier, $∣ S_{n} ∣ = n!$ — on retrouve le théorème 2.6.

Proposition 4.4 — Nombre de surjections (formule du crible)

Le nombre de surjections $E \to F$ avec $∣ E ∣ = p$ et $∣ F ∣ = n$ , souvent noté $S (p, n)$ ou $Surj (p, n)$ , n'a pas de formule simple en général. Il se calcule par crible :

S (p, n) = k = 0 \sum n (- 1)^{k} (k n) (n - k)^{p} .

(en MPSI, on l'admet ou on la fait redémontrer en exercice ; la démo est une application directe de la formule du crible appliquée aux applications dont l'image évite chaque élément de $F$ ).

💡 Exemple récapitulatif — Tirage de 3 objets dans une urne à 8 numérotés. Selon le mode :

Avec remise, ordre compte (p-liste) : $8^{3} = 512$ .
Sans remise, ordre compte (arrangement) : $A_{8}^{3} = 8 \cdot 7 \cdot 6 = 336$ .
Sans remise, ordre indifférent (combinaison) : $(3 8) = \frac{8 \cdot 7 \cdot 6}{3 !} = 56$ .
Avec remise, ordre indifférent (combinaison avec répétition, hors-prog mais classique) : $(p n + p - 1) = (3 10) = 120$ .

(le dernier cas est hors-programme MPSI strict, mais souvent demandé en oral).

5. Parties d'un ensemble fini

Théorème 5.1 — Nombre de parties

Soit $E$ un ensemble fini de cardinal $n$ . Le nombre de parties de $E$ (y compris $\emptyset$ et $E$ ) est :

∣ P (E) ∣ = 2^{n} .

Justification combinatoire. Choisir une partie $A \subset E$ revient à décider, pour chacun des $n$ éléments de $E$ , s'il est dans $A$ ou non : c'est une application $E \to {0, 1}$ (fonction indicatrice). Par le théorème 4.1, leur nombre est $2^{n}$ .

Justification par binôme. On peut aussi sommer le nombre de parties par cardinal :

∣ P (E) ∣ = k = 0 \sum n (k n) = (1 + 1)^{n} = 2^{n} .

💡 Exemple — Tableau récapitulatif des 4 cas canoniques. Soit

∣ E ∣ = n = 5

p = 3

. Combien y a-t-il de…

… p-listes d'éléments de $E$ ? $n^{p} = 125$ (ordre OUI, répétition OUI).
… arrangements de $p$ parmi $n$ ? $A_{n}^{p} = 60$ (ordre OUI, répétition NON).
… combinaisons de $p$ parmi $n$ ? $(p n) = 10$ (ordre NON, répétition NON).
… multi-ensembles de $p$ parmi $n$ ? $(p n + p - 1) = 35$ (ordre NON, répétition OUI — hors-prog strict).

🚀 Stage intensif Majorant

Tu veux verrouiller dénombrement + probabilités avant le DS ? Nos stages intensifs vacances (1 semaine, 25h) reprennent l'intégralité de la combinatoire MPSI avec exos type concours (CCINP, Mines-Ponts, Centrale) et khôlles blanches. Encadrés par des alumni X-ENS, Centrale et Mines.

Voir les stages MPSI →

6. Erreurs classiques en copie (vues par les correcteurs)

Ces erreurs sont relevées chaque année dans les rapports de jury (CCINP, Mines-Ponts, Centrale, X-ENS) sur les épreuves comportant du dénombrement (en algèbre ou en probabilités). Elles coûtent typiquement entre 0,5 et 2 points par occurrence.

⚠ Erreur 1 — Confondre arrangement et combinaison. « Choisir 3 personnes pour le bureau (président, secrétaire, trésorier) parmi 20 » est un arrangement (l'ordre compte : président ≠ trésorier) :

A_{20}^{3} = 6840

. « Choisir 3 délégués (rôles équivalents) parmi 20 » est une combinaison :

(3 20) = 1140

. Lis chaque énoncé en te demandant : l'ordre est-il signifiant ?

⚠ Erreur 2 — Oublier le principe additif pour des cas non-disjoints. Si l'on compte « élèves qui font maths OU physique » sans retirer ceux qui font les deux, on les compte deux fois. Toujours utiliser

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣

(ou le crible général). C'est l'erreur n°1 dans les problèmes de probabilités élémentaires.

⚠ Erreur 3 — Diviser à tort par $k!$ dans un arrangement. On ne divise par

k!

que pour passer d'un arrangement (ordre) à une combinaison (sans ordre). Si l'énoncé impose l'ordre (podiums, classements, mots…), ne divise pas. Symétriquement, si l'énoncé ne distingue pas l'ordre (jurys, mains de cartes, sous-ensembles…), il faut diviser. Le test : « si je permute mes

k

objets choisis, est-ce que le résultat change ? » Si oui → arrangement. Si non → combinaison.

⚠ Erreur 4 — Mauvais usage de la formule de Pascal. La formule s'écrit

(k n) + (k + 1 n) = (k + 1 n + 1)

— pas

(k n + 1)

(erreur d'indice droit). Mnémotechnique : les deux indices supérieurs

n

deviennent

n + 1

dans le résultat ; le plus grand indice inférieur (

k + 1

) est conservé.

⚠ Erreur 5 — Confondre $n^{p}$ (applications) et $p^{n}$ (rien de canonique). Le nombre d'applications de

E

(à

p

éléments) vers

F

(à

n

éléments) est

n^{p} = ∣ F ∣^{∣ E ∣}

— « cardinal de l'arrivée à la puissance cardinal du départ ». Permuter départ et arrivée donne

p^{n}

, qui n'est pas le nombre d'applications dans l'autre sens (ce serait pour

F \to E

). À chaque utilisation, repère qui est

E

(le départ) et qui est

F

(l'arrivée).

7. Pour aller plus loin

Le dénombrement est l'infrastructure de plusieurs chapitres MPSI/MP. Les blocs aval :

Probabilités sur un univers fini — la probabilité d'un événement se calcule comme $∣ A ∣/∣Ω∣$ en cas d'équiprobabilité. Toute la combinatoire du chapitre est mobilisée.
Groupe symétrique $S_{n}$ — étude algébrique des permutations (cycles, signature, transpositions). Le théorème 2.6 ( $∣ S_{n} ∣ = n!$ ) est le point de départ.
Espaces vectoriels de dimension finie — le théorème de la base incomplète, la dimension d'un espace de matrices ou de polynômes, reposent sur des comptages élémentaires.
Arithmétique (PGCD, indicatrice d'Euler) — l'indicatrice d'Euler $φ (n)$ se calcule via la formule du crible appliquée aux multiples de chaque facteur premier.

Récap final — Ce qu'il faut absolument retenir

À la veille d'une khôlle ou d'un DS, parcours cette checklist : tu dois pouvoir répondre « oui, sans hésiter » à chaque question.

Sais-tu écrire la formule du crible à 2 termes — et la généraliser à 3 ensembles ?
Sais-tu énoncer le principe multiplicatif et identifier quand il s'applique (indépendance des étapes) ?
Sais-tu remplir de tête le tableau « ordre × répétition » (p-liste / arrangement / combinaison / multi-ensemble) ?
Sais-tu démontrer que le nombre d'arrangements de $p$ parmi $n$ vaut $A_{n}^{p} = n (n - 1) \dots (n - p + 1)$ ?
Connais-tu par cœur $A_{n}^{p} = \frac{n !}{( n - p )!}$ et $(k n) = \frac{n !}{k ! ( n - k )!}$ ?
Sais-tu démontrer la formule de Pascal de deux façons (factorielles ET combinatoire) ?
Sais-tu énoncer la formule du binôme et l'utiliser pour calculer $\sum_{k} (k n)$ et $\sum_{k} (- 1)^{k} (k n)$ ?
Sais-tu que le nombre d'applications $E \to F$ vaut $∣ F ∣^{∣ E ∣}$ — et démontrer la formule par récurrence sur $∣ E ∣$ ?
Sais-tu que le nombre d'injections $E \to F$ vaut $A_{n}^{p}$ (et celui de bijections $n!$ ) ?
Sais-tu que le nombre de parties d'un ensemble à $n$ éléments est $2^{n}$ — et le justifier par fonctions indicatrices ?
Sais-tu identifier les 5 erreurs classiques en copie et les éviter (arrangement/combinaison, principe additif non-disjoint, division par $k!$ , indice de Pascal, sens d'application) ?

Démonstrations à savoir refaire

Formule du crible à 2 termes — partition de A∪B en X = A\B, Y = B\A, Z = A∩B
Nombre d'arrangements — principe multiplicatif sur $p$ étapes, $n - k$ choix à l'étape $k + 1$
Formule de Pascal — mise au même dénominateur $(k + 1)! (n - k)!$ et factorisation par $n!$
Nombre d'applications $E \to F$ = $∣ F ∣^{∣ E ∣}$ — récurrence sur $∣ E ∣$ , bijection $F (E, F) \leftrightarrow F (E^{'}, F) \times F$

Vue d'ensemble

Prérequis

1. Ensembles finis et cardinal

2. p-listes, arrangements et permutations

2.1 — p-listes (avec répétition)

2.2 — Arrangements (p-listes sans répétition)

2.3 — Permutations

3. Combinaisons et coefficients binomiaux

4. Nombre d'applications, d'injections, de bijections

5. Parties d'un ensemble fini

6. Erreurs classiques en copie (vues par les correcteurs)

7. Pour aller plus loin

Récap final — Ce qu'il faut absolument retenir

Démonstrations à savoir refaire

Fiches associées

Nombres réels

Suites numériques

Généralités sur les fonctions

Limites et continuité

Fonctions dérivables

Logarithmes, exponentielles et puissances

Tu veux aller plus loin sur ce chapitre ?