Le cours

Résumé en cinq points

Deux principes gouvernent tout : le principe additif pour des cas disjoints et le principe multiplicatif pour des choix successifs.
Quatre formules suffisent : $n^p$ pour les listes avec répétition, le produit des $p$ facteurs décroissants pour les listes sans répétition, $n!$ pour les permutations, $\binom{n}{p}$ pour les parties.
Le nombre d'applications d'un ensemble à $p$ éléments vers un ensemble à $n$ éléments vaut $n^p$ , et le nombre de parties d'un ensemble à $n$ éléments vaut $2^n$ .
La formule de Pascal et la formule du binôme se démontrent par un argument de comptage, en classant selon un élément distingué ou selon les facteurs où l'on choisit $a$ .
Avant toute formule, on décrit l'objet compté et on tranche deux questions : l'ordre et les répétitions.

Pourquoi ce chapitre

Compter est la première étape de toute probabilité finie. Dès qu'une expérience est modélisée par une probabilité uniforme, calculer une probabilité revient à compter des cas favorables et des cas possibles.

Le chapitre fournit les quelques formules qui suffisent :

cardinal d'un produit ;
nombre d'applications ;
nombre de $p$ -listes d'éléments distincts ;
nombre de permutations ;
nombre de parties à $p$ éléments.

Il donne surtout une méthode : décrire précisément l'objet que l'on compte avant de choisir la formule. La confusion entre choix ordonné et choix non ordonné, entre tirage avec remise et tirage sans remise, est la première cause d'erreur en probabilités. Ce chapitre est aussi l'occasion de démontrer autrement, par un argument de comptage, la formule de Pascal et la formule du binôme déjà rencontrées au premier semestre.

1Cardinal d'un ensemble fini

1.1Définition

Définition 1.1Ensemble fini, cardinal

Un ensemble $E$ est fini s'il est vide, ou s'il existe un entier $n$ non nul et une bijection de $\intent{1}{n}$ sur $E$ . Cet entier $n$ est alors unique : c'est le cardinal de $E$ , noté $\abs{E}$ ou $\Card(E)$ . Le cardinal de l'ensemble vide est $0$ .

Autrement dit, compter les éléments de $E$ , c'est les numéroter de $1$ à $n$ sans répétition ni oubli.

1.2Parties d'un ensemble fini

Théorème 1.2Cardinal d'une partie

Hypothèses

$E$ est un ensemble fini ;
$A$ est une partie de $E$ .

Alors $A$ est fini et $\abs{A} \leqslant \abs{E}$ . Il y a égalité si et seulement si $A = E$ .

Ce cas d'égalité est l'analogue exact du cas d'égalité sur les dimensions en algèbre linéaire. Il sert à prouver une égalité d'ensembles à partir d'une inclusion.

1.3Applications entre ensembles finis

Théorème 1.3Injective, surjective, bijective

Hypothèses

$E$ et $F$ sont deux ensembles finis de même cardinal ;
$f$ est une application de $E$ dans $F$ .

Alors $f$ est bijective si et seulement si elle est injective, si et seulement si elle est surjective.

C'est le principe des tiroirs sous une autre forme. Si l'on range $n+1$ objets dans $n$ tiroirs, un tiroir contient au moins deux objets : aucune application d'un ensemble à $n+1$ éléments vers un ensemble à $n$ éléments n'est injective.

Exemple 1.4

Une application de $\intent{1}{5}$ dans lui-même qui prend cinq valeurs distinctes est nécessairement surjective, donc bijective.

1.4Opérations sur les cardinaux

Propriété 1.5Union disjointe (principe additif)

Si $A$ et $B$ sont finis et disjoints, $\abs{A \cup B} = \abs{A} + \abs{B}$ . Plus généralement, si un ensemble fini est réunion de parties deux à deux disjointes, son cardinal est la somme des cardinaux.

C'est le principe additif, utilisé dès qu'on découpe un problème en cas.

Propriété 1.6Union quelconque de deux ensembles

Pour $A$ et $B$ finis : $\abs{A \cup B} = \abs{A} + \abs{B} - \abs{A \cap B}.$

On soustrait l'intersection comptée deux fois. La formule du crible, qui généralise à trois ensembles ou plus, est hors programme.

Propriété 1.7Complémentaire

Si $A$ est une partie de $E$ fini, le cardinal du complémentaire de $A$ dans $E$ vaut $\abs{E} - \abs{A}$ .

Passer au complémentaire est souvent bien plus rapide que compter directement, en particulier avec les énoncés du type « au moins un ».

Propriété 1.8Différence

Pour $A$ et $B$ finis : $\abs{A \setminus B} = \abs{A} - \abs{A \cap B}.$

Propriété 1.9Produit cartésien (principe multiplicatif)

$\abs{A \times B} = \abs{A} \times \abs{B}$ . Plus généralement, le cardinal d'un produit de $n$ ensembles finis est le produit des cardinaux.

C'est le principe multiplicatif, qui traduit un choix en plusieurs étapes indépendantes.

1.5Applications et parties

Propriété 1.10Nombre d'applications

Si $E$ a $p$ éléments et $F$ a $n$ éléments, le nombre d'applications de $E$ dans $F$ vaut $n^p$ .

Démonstration

Une application est déterminée par le choix indépendant de l'image de chacun des $p$ éléments, et il y a $n$ possibilités à chaque fois. L'ensemble des applications de $E$ dans $F$ est en bijection avec le produit de $p$ copies de $F$ .

Propriété 1.11Nombre de parties

Si $E$ a $n$ éléments, l'ensemble des parties de $E$ a $2^n$ éléments.

Démonstration

Une partie est déterminée par sa fonction indicatrice, qui est une application de $E$ dans $\{0, 1\}$ . On applique le résultat précédent avec $n = 2$ et $p = \abs{E}$ .

Exemple 1.12

Le nombre de mots de 5 lettres formés avec l'alphabet à 26 lettres, avec répétitions autorisées, est $26^5$ .

2Listes et combinaisons

2.1Vocabulaire

Définition 2.1 $p$ -liste

Une $p$ -liste, ou $p$ -uplet, d'éléments de $E$ est un élément du produit de $p$ copies de $E$ . C'est un choix ordonné de $p$ éléments avec répétitions autorisées. Il y en a $n^p$ si $E$ a $n$ éléments.

Définition 2.2 $p$ -liste d'éléments distincts

Une $p$ -liste d'éléments distincts est un $p$ -uplet dont les composantes sont deux à deux distinctes. C'est un choix ordonné sans répétition, ce qui correspond à un tirage successif sans remise.

Définition 2.3Combinaison

Une partie à $p$ éléments, ou $p$ -combinaison, est un choix non ordonné sans répétition, ce qui correspond à un tirage simultané.

À retenir

Devant tout énoncé, deux questions : l'ordre compte-t-il, les répétitions sont-elles possibles ? Les réponses déterminent la formule.

2.2 $p$ -listes d'éléments distincts et permutations

Théorème 2.4Nombre de $p$ -listes d'éléments distincts

Hypothèses

$E$ a $n$ éléments ;
$p$ est un entier naturel.

Alors le nombre de $p$ -listes d'éléments distincts de $E$ vaut $n(n-1)\cdots(n-p+1),$ produit de $p$ facteurs consécutifs décroissants. Il vaut $0$ si $p > n$ . Pour $p \leqslant n$ , on l'écrit aussi $\dfrac{n!}{(n-p)!}$ .

Démonstration

On choisit la première composante parmi $n$ éléments, la deuxième parmi les $n-1$ restants, et ainsi de suite jusqu'à la $p$ -ième parmi $n-p+1$ . Le principe multiplicatif conclut.

Ce nombre est aussi le nombre d'applications injectives d'un ensemble de cardinal $p$ dans un ensemble de cardinal $n$ .

Définition 2.5Permutation

Dans le cas $p = n$ , une permutation de $E$ est une bijection de $E$ sur lui-même. Le nombre de permutations d'un ensemble à $n$ éléments vaut $n!$ .

Exemple 2.6

Le nombre de podiums possibles (premier, deuxième et troisième) dans une course à 10 coureurs vaut $10 \times 9 \times 8 = 720$ . Le nombre d'ordres d'arrivée complets vaut $10!$ .

2.3Combinaisons

Théorème 2.7Nombre de parties à $p$ éléments

Hypothèses

$E$ a $n$ éléments ;
$p$ est un entier relatif.

Alors le nombre de parties à $p$ éléments de $E$ , noté $\binom{n}{p}$ et lu « $p$ parmi $n$ », vaut $\binom{n}{p} = \frac{n!}{p!\,(n-p)!}$ pour $0 \leqslant p \leqslant n$ . Il vaut $0$ si $p < 0$ ou $p > n$ .

Démonstration

On compte les $p$ -listes d'éléments distincts de deux façons. D'une part elles sont au nombre de $\dfrac{n!}{(n-p)!}$ . D'autre part, se donner une telle liste revient à choisir d'abord la partie à $p$ éléments qui en constitue le support, puis à ordonner ces $p$ éléments, ce qui offre $p!$ possibilités. On en déduit la formule.

Propriété 2.8Propriétés à connaître

Pour $0 \leqslant p \leqslant n$ : $\binom{n}{p} = \binom{n}{n-p}, \qquad \sum_{p=0}^{n} \binom{n}{p} = 2^n.$

La première égalité se voit en associant à une partie son complémentaire. La seconde se voit en classant les parties de $E$ selon leur cardinal.

Exemple 2.9

Le nombre de mains de 5 cartes dans un jeu de 32 cartes vaut $\binom{32}{5}$ . Le nombre de mains contenant exactement deux as vaut $\binom{4}{2}\binom{28}{3}$ , en choisissant d'abord les deux as parmi quatre puis les trois autres cartes parmi les vingt-huit qui ne sont pas des as.

2.4Démonstration combinatoire de la formule de Pascal

Propriété 2.10Formule de Pascal

Pour $1 \leqslant p \leqslant n$ : $\binom{n-1}{p-1} + \binom{n-1}{p} = \binom{n}{p}.$

Démonstration

On fixe un élément particulier $a$ de $E$ , ensemble à $n$ éléments, et on classe les parties à $p$ éléments en deux catégories disjointes.

Celles qui contiennent $a$ s'obtiennent en choisissant les $p-1$ autres éléments parmi les $n-1$ restants : il y en a $\binom{n-1}{p-1}$ .
Celles qui ne contiennent pas $a$ sont des parties à $p$ éléments de l'ensemble à $n-1$ éléments obtenu en retirant $a$ : il y en a $\binom{n-1}{p}$ .

Le principe additif donne la formule.

Cette preuve est à comparer avec le calcul algébrique direct avec les factorielles, qui donne le même résultat mais n'explique rien.

2.5Démonstration combinatoire de la formule du binôme

Propriété 2.11Formule du binôme

Hypothèses

$a$ et $b$ sont des réels ou des complexes ;
$n$ est un entier naturel.

Alors $(a+b)^n = \sum_{p=0}^{n} \binom{n}{p}\, a^p\, b^{n-p}.$

Démonstration

On développe le produit de $n$ facteurs tous égaux à $a + b$ . Chaque terme du développement s'obtient en choisissant dans chaque facteur soit $a$ , soit $b$ . Un terme donné vaut $a^p b^{n-p}$ exactement quand on a choisi $a$ dans $p$ facteurs, c'est-à-dire quand on a choisi la partie à $p$ éléments des facteurs où l'on prend $a$ . Il y a $\binom{n}{p}$ façons de faire ce choix, d'où le coefficient.

Cette preuve explique pourquoi les coefficients binomiaux apparaissent dans le binôme, et c'est elle que le programme demande.

Méthodes

MéthodeDécrire l'objet compté

Écrire une phrase complète qui décrit l'objet : un mot de 5 lettres, une partie à 3 éléments, une application de tel ensemble dans tel autre.
Ne poser aucune formule tant que cette phrase n'est pas écrite.

MéthodeChoisir la formule

Se demander si l'ordre compte.
Se demander si les répétitions sont autorisées.
Conclure :
- ordre et répétitions : $n^p$ ;
- ordre sans répétition : le produit des $p$ facteurs décroissants ;
- ni ordre ni répétition : $\binom{n}{p}$ .

MéthodeDécouper ou décomposer

Si plusieurs situations sont possibles, les découper en cas disjoints, puis additionner.
Si un objet se construit par choix indépendants, le décomposer en étapes successives, puis multiplier.

MéthodePasser au complémentaire

Repérer un énoncé du type « au moins un ».
Compter le contraire : le contraire de « au moins un as » est « aucun as », ce qui se compte immédiatement.
Soustraire au total.

MéthodeVérifier un résultat

Tester la formule sur de petits cas ( $n = 2$ ou $n = 3$ ), où l'on peut énumérer à la main : si elle ne redonne pas le bon résultat, elle est fausse.
Contrôler l'ordre de grandeur : un nombre de parties ne peut pas dépasser $2^n$ , un nombre d'applications ne peut pas dépasser $n^p$ .

Ce qu'il faut savoir refaire en khôlle

Justifier que le nombre d'applications d'un ensemble à $p$ éléments dans un ensemble à $n$ éléments vaut $n^p$ .
Démontrer que l'ensemble des parties d'un ensemble à $n$ éléments a $2^n$ éléments, par les fonctions indicatrices.
Démontrer la formule donnant le nombre de $p$ -listes d'éléments distincts, puis en déduire le nombre de permutations.
Démontrer la formule donnant $\binom{n}{p}$ en comptant les $p$ -listes d'éléments distincts de deux façons.
Donner la preuve combinatoire de la formule de Pascal.
Donner la preuve combinatoire de la formule du binôme.
Compter des mains de cartes avec contraintes, par exemple exactement deux as, ou au moins un as.
Expliquer pourquoi une application injective entre deux ensembles finis de même cardinal est bijective.

Méthodes et exercices

Les résultats à connaître

Cardinal défini par une bijection de {1, …, n} sur E. Le fondement théorique des entiers et des cardinaux est hors programme.
Une partie A d'un ensemble fini E est finie, |A| ≤ |E|, avec égalité si et seulement si A = E. Admis.
Une application entre deux ensembles finis de même cardinal est bijective si et seulement si elle est injective, si et seulement si elle est surjective. Exigible, la justification doit savoir être donnée à l'oral.
Cardinal d'une union disjointe, somme des cardinaux. Admis.
|A ∪ B| = |A| + |B| − |A ∩ B| pour A et B finis quelconques. Exigible, se déduit du cas disjoint.
Complémentaire et différence, |E| − |A| et |A| − |A ∩ B|. Exigibles.
Cardinal d'un produit cartésien fini, produit des cardinaux. Admis.
Si |E| = p et |F| = n, il y a n puissance p applications de E dans F. Exigible avec justification.
Si |E| = n, l'ensemble des parties de E a 2 puissance n éléments. Exigible avec démonstration.
Nombre de p-listes d'éléments distinctes, égal au nombre d'injections d'un ensemble à p éléments dans un ensemble à n éléments, n(n − 1)…(n − p + 1). Exigible avec démonstration.
Nombre de permutations d'un ensemble à n éléments, n!. Exigible, c'est le cas p = n.
C(n, p) = n! / (p! (n − p)!) pour 0 ≤ p ≤ n, et 0 sinon. Exigible avec démonstration.
Symétrie C(n, p) = C(n, n − p) et somme des C(n, p) égale à 2 puissance n. Exigibles.
Formules de Pascal et du binôme. Démonstration combinatoire exigible.
Hors programme, à signaler si un exercice les demande : formule du crible pour trois ensembles ou plus, combinaisons avec répétition, formule générale des surjections, nombres de Stirling. L'usage systématique de bijections pour dénombrer n'est pas un attendu.

Clés de démonstration

Union quelconque. A est la réunion disjointe de A privé de B et de A ∩ B, d'où |A privé de B| = |A| − |A ∩ B|. Puis A ∪ B est la réunion disjointe de A privé de B et de B. Astuce : tout se ramène au cas disjoint.

Injective équivaut à surjective. Si f est injective, f(E) a autant d'éléments que E, donc que F, et le cas d'égalité donne f(E) = F. Si f est surjective, E est la réunion disjointe des n ensembles d'antécédents, tous non vides, donc chacun a exactement un élément, sinon |E| > |F|. Astuce : cas d'égalité dans un sens, principe additif sur les antécédents dans l'autre.

Nombre d'applications. On numérote E de 1 à p. Se donner f revient à se donner la liste (f(x₁), …, f(x_p)), élément de F puissance p. Astuce : identifier une application à la liste de ses valeurs.

Nombre de parties. À une partie A on associe son indicatrice, application de E dans {0, 1}, et une telle application détermine réciproquement la partie des points où elle vaut 1. Il y a donc 2 puissance n parties. Astuce : l'indicatrice transforme les parties en applications.

p-listes d'éléments distincts. On choisit la première composante parmi n, la deuxième parmi les n − 1 restantes, et ainsi de suite. Le nombre de choix à chaque étape ne dépend pas des choix précédents. Astuce : si p > n, le facteur 0 apparaît et la formule donne bien 0.

Coefficients binomiaux. On compte les p-listes d'éléments distincts de deux façons, directement n!/(n − p)!, ou en choisissant le support puis un ordre sur ce support, p! façons. Astuce : double comptage, chaque partie est comptée exactement p! fois.

Pascal. On distingue un élément a et on sépare les parties à p éléments selon qu'elles contiennent a ou non. Astuce : l'élément distingué.

Binôme. Dans le produit de n facteurs (a + b), un terme correspond au choix de a ou de b dans chaque facteur. Il vaut a puissance p fois b puissance (n − p) exactement quand la partie des facteurs où l'on prend a a p éléments. Astuce : compter les parties de l'ensemble des facteurs.

Exemples et contre-exemples à connaître

Mains de 5 cartes parmi 32 avec au moins un as. Le bon calcul est C(32, 5) − C(28, 5) = 103 096. Le calcul 4 × C(31, 4) = 125 860 est faux, car une main à deux as est comptée deux fois.
Anagrammes de PAPA. Il y en a 6, pas 4! = 24, car échanger les deux P ou les deux A ne change pas le mot.
Dominos. Paires non ordonnées de valeurs de 0 à 6, éventuellement égales. Il y en a 28, soit 21 paires distinctes plus 7 doubles, et pas 49/2. Choix non ordonné avec répétition, hors des formules du cours.
Conventions. 0! = 1, C(n, 0) = 1 car seule la partie vide a 0 élément, et il y a une seule application de l'ensemble vide dans F. Les formules marchent alors sans exception.
Tiroirs. Parmi 13 personnes, deux sont nées le même mois. Avec 12, ce n'est pas garanti.
L'application n ↦ n + 1 de N dans N est injective et non surjective. L'équivalence exige des ensembles finis de même cardinal.
Anniversaires. Avec 23 personnes et 365 jours, le nombre de listes de dates distinctes, 365 × 364 × … × 343, est inférieur à la moitié de 365 puissance 23. L'intuition sous-estime les coïncidences.
Applications strictement croissantes de {1, …, p} dans {1, …, n}. Il y en a C(n, p), car une telle application est déterminée par son image. Chaque partie à p éléments donne p! injections, dont une seule est croissante.

Techniques du chapitre

Trancher ordre et répétitions. Mini-exercice : codes à 4 chiffres distincts. C'est une 4-liste d'éléments distincts de {0, …, 9}, soit 10 × 9 × 8 × 7 = 5 040.

Choisir des positions pour les répétitions. Mini-exercice : anagrammes de ANANAS. On place les 3 A parmi 6 positions, C(6, 3) = 20, puis les 2 N parmi les 3 restantes, C(3, 2) = 3, le S prend la dernière. Réponse 60, en accord avec 6!/(3! 2!).

Passer au complémentaire. Mini-exercice : mots de 4 lettres sur 26 lettres, dont 6 voyelles, avec au moins une voyelle. Le contraire compte 20 puissance 4 mots. Réponse 26⁴ − 20⁴ = 456 976 − 160 000 = 296 976.

Découper en cas disjoints. Mini-exercice : comités de 3 parmi 5 femmes et 4 hommes, avec au moins deux femmes. Deux femmes, C(5, 2) × 4 = 40. Trois femmes, C(5, 3) = 10. Réponse 50.

Compter de deux façons. Mini-exercice : p C(n, p) = n C(n − 1, p − 1) pour 1 ≤ p ≤ n. On compte les comités de p personnes munis d'un président, en choisissant le comité puis le président, ou le président puis les p − 1 autres parmi n − 1.

Principe des tiroirs. Mini-exercice : 5 points dans un carré de côté 2. On le découpe en 4 carrés de côté 1. Deux points tombent dans le même, donc sont à distance au plus √2.

Tester sur un petit cas. Mini-exercice : on propose n(n − 1) parties à 2 éléments dans {1, …, n}. Pour n = 3, on énumère {1, 2}, {1, 3}, {2, 3}, soit 3 et non 6. L'ordre a été compté à tort, la réponse est n(n − 1)/2.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

Exercice 1. Mains de cartes

Classiques de khôlle et concours · Niveau khôlle

Dans un jeu de 32 cartes à 4 couleurs, on tire une main de 5 cartes. Compter les mains contenant exactement un as et exactement un cœur.

Technique découpage en cas disjoints autour de la carte commune aux deux contraintes.

Voir le corrigé

Une main est une partie à 5 éléments. L'as de cœur est à la fois as et cœur, on sépare deux cas. 2. Les cartes ni as ni cœur sont 32 − 4 − 8 + 1 = 21. 3. Si la main contient l'as de cœur, les 4 autres cartes sont prises parmi les 21, soit C(21, 4) = 5 985 mains. 4. Sinon, l'as est l'un des 3 autres, le cœur l'un des 7 cœurs non as, et les 3 cartes restantes sont prises parmi les 21, soit 3 × 7 × C(21, 3) = 21 × 1 330 = 27 930. 5. Total 33 915.

piège : Oublier le cas de l'as de cœur, ou le compter dans les deux contraintes à la fois.

Exercice 2. Anagrammes avec contraintes

Classiques de khôlle et concours · Niveau khôlle

Compter les anagrammes de ENSEMBLE, puis celles où les trois E sont consécutifs, puis celles où deux E ne sont jamais voisins.

Technique choix des positions et méthode des intervalles.

Voir le corrigé

Le mot a 8 lettres, trois E et cinq lettres distinctes. On place les E, C(8, 3) = 56 choix, puis les 5 autres lettres, 5! = 120 façons. Total 6 720. 2. Le bloc EEE commence en position 1 à 6, puis 5! pour le reste. Total 720. 3. On écrit d'abord les 5 autres lettres, 120 façons, ce qui crée 6 intervalles, avant, entre et après. On choisit 3 intervalles distincts pour les E, C(6, 3) = 20. Total 2 400.

piège : Répondre 8! en oubliant que les E sont indiscernables.

Exercice 3. Comité et président

Classiques de khôlle et concours · Niveau khôlle

Montrer que p C(n, p) = n C(n − 1, p − 1) pour 1 ≤ p ≤ n, puis calculer la somme des p C(n, p) pour p de 1 à n.

Technique double comptage puis somme binomiale.

Voir le corrigé

On compte les couples formés d'une partie à p éléments et d'un élément distingué de cette partie. 2. Première façon, C(n, p) parties puis p choix, soit p C(n, p). 3. Seconde façon, n choix de l'élément puis C(n − 1, p − 1) choix des autres. 4. La somme vaut donc n fois la somme des C(n − 1, p − 1) pour p de 1 à n, soit n fois 2 puissance (n − 1). 5. Contrôle pour n = 2, 1 × 2 + 2 × 1 = 4 = 2 × 2.

piège : Oublier que le terme p = 0 est nul, et décaler l'indice de travers.

Exercice 4. Parties de cardinal pair

Classiques de khôlle et concours · Niveau khôlle

Soit E à n éléments, n ≥ 1. Montrer que E a autant de parties de cardinal pair que de cardinal impair, et que ce nombre vaut 2 puissance (n − 1).

Technique binôme avec a = −1 et b = 1.

Voir le corrigé

Notons P la somme des C(n, k) pour k pair et I celle pour k impair. 2. Par le binôme, P + I = (1 + 1) puissance n = 2 puissance n. 3. De même, P − I = (1 − 1) puissance n = 0, car n ≥ 1. 4. Donc P = I = 2 puissance (n − 1).

piège : Oublier l'hypothèse n ≥ 1. Pour n = 0, la seule partie est vide, P = 1 et I = 0.

Exercice 5. Formule de Vandermonde

Classiques de khôlle et concours · Niveau écrit CCINP

Soient p, q, n des entiers naturels, avec C(m, k) = 0 si k > m. Montrer que la somme des C(p, k) C(q, n − k) pour k de 0 à n vaut C(p + q, n). En déduire la somme des C(n, k)² pour k de 0 à n.

Technique classement selon un paramètre, puis principes additif et multiplicatif.

Voir le corrigé

Dans une urne de p boules rouges et q bleues, il y a C(p + q, n) parties à n boules. 2. On les classe selon le nombre k de rouges, de 0 à n, en classes disjointes. 3. Une partie à k rouges s'obtient en choisissant les k rouges puis les n − k bleues, soit C(p, k) C(q, n − k). La convention traite les cas impossibles. 4. Le principe additif conclut. 5. Avec p = q = n et C(n, n − k) = C(n, k), on obtient C(2n, n).

piège : Croire que la somme des carrés est le carré de la somme, soit 4 puissance n.

Exercice 6. Couples de parties emboîtées

Classiques de khôlle et concours · Niveau écrit CCINP

Soit E à n éléments. Compter de deux façons les couples (A, B) de parties de E tels que A ⊂ B.

Technique classement selon le cardinal puis binôme, et choix élément par élément.

Voir le corrigé

On classe selon le cardinal k de B. Il y a C(n, k) choix de B, puis 2 puissance k choix de A. 2. Le total est la somme des C(n, k) 2 puissance k, qui vaut (2 + 1) puissance n = 3 puissance n par le binôme. 3. Autre façon, chaque élément est dans A, ou dans B sans être dans A, ou hors de B. Trois choix indépendants pour n éléments donnent 3 puissance n. 4. Le même raisonnement donne 3 puissance n couples (A, B) avec A ∩ B vide.

piège : Écrire 2 puissance (n − k) au lieu de 2 puissance k dans la somme.

Exercice 7. Chemins sur un quadrillage

Classiques de khôlle et concours · Niveau écrit CCINP

On va de (0, 0) à (5, 3) par pas unitaires vers la droite ou vers le haut. Compter les chemins, ceux qui passent par (2, 1), et ceux qui évitent ce point.

Technique coder un chemin par un mot et choisir des positions.

Voir le corrigé

Un chemin est une suite de 8 pas dont 5 vers la droite, déterminée par les positions de ces 5 pas, C(8, 5) = 56. 2. Un chemin par (2, 1) est un chemin de (0, 0) à (2, 1), C(3, 1) = 3 choix, suivi d'un chemin de (2, 1) à (5, 3), C(5, 2) = 10 choix. Total 30. 3. Par complémentaire, 26 chemins évitent (2, 1).

piège : Additionner 3 et 10 au lieu de multiplier, alors que les deux morceaux se choisissent successivement.

Exercice 10. Tiroirs et divisibilité

Classiques de khôlle et concours · Niveau oral X

Soit n ≥ 1. On choisit n + 1 entiers distincts dans {1, …, 2n}. Montrer que deux d'entre eux sont consécutifs, puis que l'un d'eux divise un autre.

Technique principe des tiroirs avec des tiroirs bien choisis.

Voir le corrigé

Premiers tiroirs, les n paires {1, 2}, {3, 4}, …, {2n − 1, 2n}. Deux des n + 1 entiers tombent dans la même paire, ils sont consécutifs. 2. Tout entier k ≥ 1 s'écrit de façon unique 2 puissance a fois m avec m impair. 3. Pour k ≤ 2n, la partie impaire m appartient à {1, 3, …, 2n − 1}, qui a n éléments. 4. Deux des entiers ont donc la même partie impaire, disons 2 puissance a fois m et 2 puissance b fois m avec a < b, et le premier divise le second.

piège : Choisir des tiroirs trop nombreux. Il en faut exactement n pour n + 1 objets.

Exercice 8. Diagonales d'un polygone convexe

Approfondissement · Type oral Centrale

Soit un polygone convexe à n sommets, n ≥ 4, où trois diagonales ne sont jamais concourantes en un point intérieur. Compter les diagonales, puis leurs points d'intersection intérieurs.

Technique identifier l'objet compté à une partie de l'ensemble des sommets.

Voir le corrigé

Un segment joignant deux sommets est une partie à 2 sommets, C(n, 2). On retire les n côtés, il reste n(n − 3)/2 diagonales. 2. Deux diagonales se coupent à l'intérieur si et seulement si leurs quatre extrémités sont distinctes et alternent sur le polygone. 3. Quatre sommets forment un quadrilatère convexe, dont les diagonales se coupent en un seul point intérieur. 4. Réciproquement, grâce à l'hypothèse de non concours, un point d'intersection intérieur provient d'un unique quadruplet de sommets. Il y a donc C(n, 4) points. 5. Contrôle, le pentagone régulier donne 5 diagonales et 5 points.

piège : Oublier l'hypothèse de non concours. Dans l'hexagone régulier, trois grandes diagonales se coupent au centre et la formule surestime.

Exercice 9. Surjections de n + 1 éléments sur n éléments

Approfondissement · Niveau écrit Mines

Soit n ≥ 1. Compter les surjections de {1, …, n + 1} sur {1, …, n}.

Technique structure des antécédents puis construction en deux étapes. La formule générale des surjections, hors programme, n'est pas utilisée.

Voir le corrigé

Pour une surjection f, les n ensembles d'antécédents sont non vides, disjoints, de cardinaux de somme n + 1. Exactement l'un a 2 éléments, les autres en ont 1. 2. On choisit la paire d'éléments de même image, C(n + 1, 2) choix. 3. Les n blocs, cette paire et n − 1 singletons, sont envoyés bijectivement sur {1, …, n}, soit n! façons. 4. Chaque surjection est obtenue une seule fois. Total n! × n(n + 1)/2. 5. Contrôle pour n = 2, on trouve 6, et les 8 applications de {1, 2, 3} dans {1, 2} moins les 2 constantes donnent bien 6.

piège : Choisir l'image double puis ses deux antécédents en les ordonnant, ce qui compte chaque surjection deux fois.

Erreurs fréquentes

Pour un énoncé « au moins un », choisir un élément vérifiant la condition puis le reste au hasard. On compte plusieurs fois les mêmes objets. Passer au complémentaire.
Confondre p-liste et partie, par exemple compter 10 × 9 × 8 un tirage simultané de 3 boules parmi 10, au lieu de C(10, 3) = 120.
Oublier que des lettres ou objets répétés sont indiscernables, et répondre n! pour des anagrammes.
Additionner des étapes successives ou multiplier des cas disjoints. On additionne pour « ou » entre cas disjoints, on multiplie pour « puis » entre choix successifs.
Utiliser la formule du crible à trois ensembles ou les combinaisons avec répétition sans les redémontrer, alors qu'elles sont hors programme en PCSI. Un découpage en cas disjoints suffit dans les exercices au programme.

Fiche de cours rédigée à partir du programme officiel de PCSI (2021), deuxième semestre, section « Dénombrement ». Cette section est introduite essentiellement en vue des probabilités. Toute formalisation excessive est exclue, et les propriétés les plus intuitives sur les cardinaux sont admises. Tout fondement théorique des notions d'entier naturel et de cardinal est hors programme.

Dénombrement

Résumé en cinq points

1Cardinal d'un ensemble fini

1.1Définition

1.2Parties d'un ensemble fini

1.3Applications entre ensembles finis

1.4Opérations sur les cardinaux

1.5Applications et parties

2Listes et combinaisons

2.1Vocabulaire

2.2ppp-listes d'éléments distincts et permutations

2.3Combinaisons

2.4Démonstration combinatoire de la formule de Pascal

2.5Démonstration combinatoire de la formule du binôme

Méthodes

Ce qu'il faut savoir refaire en khôlle

Les résultats à connaître

Clés de démonstration

Exemples et contre-exemples à connaître

Techniques du chapitre

Exercices classiques corrigés

Exercice 1. Mains de cartes

Exercice 2. Anagrammes avec contraintes

Exercice 3. Comité et président

Exercice 4. Parties de cardinal pair

Exercice 5. Formule de Vandermonde

Exercice 6. Couples de parties emboîtées

Exercice 7. Chemins sur un quadrillage

Exercice 10. Tiroirs et divisibilité

Exercice 8. Diagonales d'un polygone convexe

Exercice 9. Surjections de n + 1 éléments sur n éléments

Erreurs fréquentes

Au concours

2.2 $p$ -listes d'éléments distincts et permutations