Le cours

Résumé en cinq points

Deux ensembles en bijection ont même cardinal. C'est le principe de transfert du dénombrement.
Le « ou » disjoint donne une addition, le « et » de choix successifs une multiplication. Quand les cas se recouvrent, on applique la formule du crible.
Choisir $p$ objets parmi $n$ donne $n^p$ avec ordre et répétition, $n(n-1)\cdots(n-p+1)$ avec ordre et sans répétition, $\dbinom{n}{p}$ sans ordre et sans répétition.
Les permutations de $n$ objets sont au nombre de $n!$ , et les parties d'un ensemble à $n$ éléments au nombre de $2^n$ .
En équiprobabilité, une probabilité est un quotient de cardinaux, calculés dans le même modèle.

Pourquoi ce chapitre

Dénombrer, c'est compter sans énumérer. L'objectif du programme est de mettre en place un vocabulaire efficace pour décrire et analyser les problèmes combinatoires, avec quelques résultats fondamentaux. Le programme précise deux choses :

les résultats sont justifiés intuitivement, sans démonstration formelle ;
on évite tout excès de technicité.

La destination est claire : les probabilités sur un univers fini. Dans une situation d'équiprobabilité, la probabilité d'un événement $A$ est le quotient du cardinal de $A$ par le cardinal de l'univers. Toute la difficulté du calcul probabiliste se déplace alors sur le dénombrement.

Les situations concrètes abondent en sciences du vivant :

les séquences d'ADN d'une longueur donnée ;
les échantillons possibles dans une population ;
les génotypes issus d'un croisement ;
les ordres de passage dans un protocole expérimental.

Dans chaque cas, la question n'est pas de calculer, mais de choisir le bon modèle.

1Cardinal d'un ensemble fini

Définition 1.1Cardinal

Un ensemble $E$ est fini quand il possède un nombre fini d'éléments. Ce nombre est son cardinal, noté $\operatorname{card}(E)$ ou $\#E$ . Le cardinal de l'ensemble vide est $0$ .

Le programme définit le cardinal par la notion intuitive de nombre d'éléments.

Propriété 1.2Principe de transfert

Deux ensembles en bijection ont le même cardinal.

Quand on ne sait pas compter directement les objets d'un ensemble, on les met en correspondance un pour un avec des objets qu'on sait compter.

Exemple 1.3Parties contenant l'élément 1

Pour compter les parties à trois éléments de $\intent{1}{10}$ contenant l'élément $1$ , on remarque qu'une telle partie est déterminée par le choix des deux autres éléments dans $\intent{2}{10}$ . La correspondance est bijective, donc le nombre cherché est le nombre de parties à deux éléments d'un ensemble à neuf éléments.

Dans tout ce qui suit, $E$ est un ensemble fini de cardinal $n$ .

2Les deux principes de base

2.1Principe additif

Propriété 2.1Principe additif

Hypothèses

$A$ et $B$ sont finis ;
$A$ et $B$ sont disjoints.

Alors $\operatorname{card}(A \cup B) = \operatorname{card}(A) + \operatorname{card}(B)$ .

Plus généralement, si un ensemble est partitionné en plusieurs parties deux à deux disjointes, son cardinal est la somme des cardinaux. C'est le principe qui traduit un « ou » exclusif, c'est-à-dire une disjonction de cas. On l'utilise dès qu'on découpe un problème en situations qui s'excluent mutuellement.

Propriété 2.2Formule du crible

Pour deux ensembles finis $A$ et $B$ quelconques, disjoints ou non : $\operatorname{card}(A \cup B) = \operatorname{card}(A) + \operatorname{card}(B) - \operatorname{card}(A \cap B).$

Justification intuitive : en additionnant les deux cardinaux, on compte deux fois les éléments communs, il faut donc les retrancher une fois.

Propriété 2.3Passage au complémentaire

Pour $A$ partie de $E$ : $\operatorname{card}(\overline{A}) = \operatorname{card}(E) - \operatorname{card}(A).$

Le passage au complémentaire est souvent la voie la plus courte, en particulier quand l'énoncé contient les mots « au moins un ».

Exemple 2.4Échantillon de plantes

Dans un échantillon de $100$ plantes, $60$ portent le caractère A, $45$ le caractère B et $25$ les deux. Le nombre de plantes portant au moins un des deux caractères est $60 + 45 - 25 = 80$ . Le nombre de plantes n'en portant aucun est $100 - 80 = 20$ .

2.2Principe multiplicatif

Propriété 2.5Principe multiplicatif

Si $E$ et $F$ sont finis, alors $\operatorname{card}(E \times F) = \operatorname{card}(E) \times \operatorname{card}(F)$ . Ce nombre est aussi celui des façons de choisir indépendamment un élément de $E$ et un élément de $F$ .

Ce principe se généralise : quand une construction se fait en $p$ étapes successives, la première offrant $n_1$ possibilités, la deuxième $n_2$ quel que soit le choix précédent, et ainsi de suite, le nombre total de constructions est le produit $n_1 n_2 \cdots n_p$ . C'est le principe qui traduit un « et », c'est-à-dire des choix successifs.

Attention

Le nombre de possibilités à chaque étape ne doit pas dépendre des choix antérieurs, même si les possibilités elles-mêmes en dépendent.

3Les quatre modèles de tirage

Avant de compter, on répond à deux questions : l'ordre compte-t-il, les répétitions sont-elles autorisées ? Les réponses déterminent la formule.

3.1 $p$ -uplets, ordre et répétitions

Définition 3.1 $p$ -uplet

Un élément de $E^p$ est appelé un $p$ -uplet, ou une $p$ -liste, d'éléments de $E$ .

Propriété 3.2Nombre de $p$ -uplets

Il y a $n^p$ $p$ -uplets d'éléments de $E$ .

C'est le nombre de façons de choisir successivement $p$ objets parmi $n$ objets distincts, avec d'éventuelles répétitions. On parle de tirage successif avec remise.

Démonstration

On applique le principe multiplicatif : $n$ choix pour la première coordonnée, $n$ pour la deuxième et ainsi de suite, soit $n \times n \times \cdots \times n$ avec $p$ facteurs.

Exemple 3.3Séquences d'ADN et protéines

Une séquence d'ADN de longueur $10$ est une $10$ -liste sur l'alphabet $\{A, C, G, T\}$ . Il y en a $4^{10}$ , soit $1\,048\,576$ . Une protéine de $100$ acides aminés, construite sur $20$ acides aminés possibles, correspond à $20^{100}$ possibilités, un nombre gigantesque qui illustre l'immensité de l'espace des séquences.

Exemple 3.4Nombre d'applications

Une application d'un ensemble à $p$ éléments dans un ensemble à $n$ éléments est déterminée par la donnée des $p$ images, chacune choisie librement parmi $n$ . Il y a donc $n^p$ applications.

3.2 $p$ -uplets sans répétition

Définition 3.5 $p$ -uplet sans répétition

Un $p$ -uplet est dit sans répétition quand ses éléments sont deux à deux distincts.

Propriété 3.6Nombre de $p$ -uplets sans répétition

Hypothèse : $p \leqslant n$ .

Alors il y a $n(n-1)\cdots(n-p+1) = \frac{n!}{(n-p)!}$ $p$ -uplets sans répétition d'éléments de $E$ . Ce produit compte exactement $p$ facteurs.

C'est le nombre de façons de choisir successivement $p$ objets parmi $n$ objets distincts, sans répétition, autrement dit un tirage successif sans remise.

Démonstration

$n$ choix pour la première coordonnée, puis $n - 1$ pour la deuxième puisqu'on ne peut pas reprendre le premier, et ainsi de suite jusqu'à $n - p + 1$ .

Si $p > n$ , il n'existe aucun $p$ -uplet sans répétition, et le produit est bien nul.

Exemple 3.7Podiums

Dans un concours où $8$ candidats s'affrontent, le nombre de podiums possibles, c'est-à-dire de classements des trois premiers, est $8 \times 7 \times 6 = 336$ . L'ordre compte, un candidat ne peut occuper deux places.

Ces $p$ -uplets sans répétition correspondent aussi aux applications injectives d'un ensemble à $p$ éléments dans un ensemble à $n$ éléments.

3.3Permutations

Définition 3.8Permutation

Une permutation de $E$ est un $n$ -uplet contenant exactement une fois chaque élément de $E$ .

Propriété 3.9Nombre de permutations

Il y a $n!$ permutations de $E$ .

C'est le nombre de façons d'ordonner les $n$ objets d'un ensemble, ou encore de les choisir successivement tous, sans répétition. C'est le cas particulier $p = n$ du paragraphe précédent.

Exemple 3.10Ordres de passage

Le nombre d'ordres de passage possibles pour $6$ échantillons dans un protocole est $6! = 720$ .

Exemple 3.11Anagrammes de GENOME

Si l'on considérait les six lettres comme distinctes, le nombre d'anagrammes de GENOME serait $6! = 720$ . Comme la lettre E apparaît deux fois, le décompte réel est plus petit. Cet affinement n'est pas un attendu du programme, qui demande d'éviter les dénombrements techniques.

3.4 $p$ -combinaisons

Définition 3.12 $p$ -combinaison

Pour $p \leqslant n$ , une $p$ -combinaison de $E$ est une partie de $E$ à $p$ éléments.

Propriété 3.13Nombre de $p$ -combinaisons

Hypothèse : $p \leqslant n$ .

Alors il y a $\dbinom{n}{p}$ $p$ -combinaisons de $E$ , où $\binom{n}{p} = \frac{n!}{p!\,(n-p)!}.$

C'est le nombre de façons de choisir simultanément $p$ objets parmi $n$ objets distincts, autrement dit un tirage simultané, où l'ordre ne compte pas et où les répétitions sont impossibles.

Justification intuitive, à savoir expliquer. Chaque $p$ -combinaison peut être ordonnée de $p!$ manières différentes, et l'on obtient ainsi tous les $p$ -uplets sans répétition, chacun une seule fois. Donc le nombre de $p$ -uplets sans répétition vaut $p!$ fois le nombre de $p$ -combinaisons, ce qui donne le résultat en divisant.

Exemple 3.14Échantillon de plantes

Le nombre de façons de choisir $3$ plantes parmi $10$ pour constituer un échantillon, sans tenir compte de l'ordre, est $\binom{3}{10}\text{ au sens } \binom{10}{3} = \frac{10 \times 9 \times 8}{6} = 120.$

Exemple 3.15Main de cartes

Une main de $5$ cartes dans un jeu de $32$ correspond à $\dbinom{32}{5} = 201\,376$ possibilités.

Reformulation de la formule du binôme. Développer $(a+b)^n$ revient à choisir, dans chacun des $n$ facteurs, si l'on prend $a$ ou $b$ . Les termes en $a^k b^{n-k}$ proviennent du choix des $k$ facteurs qui fournissent un $a$ , donc il y en a $\dbinom{n}{k}$ . On retrouve ainsi la formule du binôme par un argument combinatoire.

3.5Tableau de décision

Pour choisir $p$ objets parmi $n$ :

ordre, avec répétition : $n^p$ ;
ordre, sans répétition : $n(n-1)\cdots(n-p+1)$ ;
pas d'ordre, sans répétition : $\dbinom{n}{p}$ .

Le quatrième cas, sans ordre et avec répétition, n'est pas au programme.

À retenir

Pour savoir si l'ordre compte, on échange deux des objets choisis : si le résultat est considéré comme différent, l'ordre compte.

4Cardinal de l'ensemble des parties

Propriété 4.1Cardinal de $\mathcal{P}(E)$

Si $\operatorname{card}(E) = n$ , alors $\operatorname{card}(\mathcal{P}(E)) = 2^n$ .

Justification intuitive. Se donner une partie de $E$ , c'est décider pour chaque élément de $E$ s'il appartient ou non à la partie. Il y a donc deux choix indépendants pour chacun des $n$ éléments, soit $2^n$ possibilités. Cela revient à mettre en bijection les parties de $E$ et les $n$ -listes de $\{0, 1\}$ , la liste associée à une partie étant sa fonction indicatrice.

Exemple 4.2Vérification

Pour $E = \{a, b\}$ , les parties sont $\varnothing$ , $\{a\}$ , $\{b\}$ , $\{a, b\}$ , il y en a bien $4 = 2^2$ .

Autre lecture. Une partie de $E$ a un cardinal $p$ compris entre $0$ et $n$ , et il y a $\dbinom{n}{p}$ parties de cardinal $p$ . En sommant sur $p$ : $\sum_{p=0}^{n} \binom{n}{p} = 2^n,$ ce qui est exactement la formule du binôme appliquée avec $a = b = 1$ .

5Lien avec les probabilités

Dans un univers fini $\Omega$ muni de l'équiprobabilité, la probabilité d'un événement $A$ vaut $\P(A) = \frac{\operatorname{card}(A)}{\operatorname{card}(\Omega)}.$ Tout calcul de probabilité devient alors un double dénombrement, celui de l'événement et celui de l'univers.

Attention

Le modèle choisi doit être le même au numérateur et au dénominateur. Si l'on compte l'univers en tirages ordonnés, il faut compter l'événement en tirages ordonnés aussi. Mélanger les deux points de vue est l'erreur la plus fréquente.

Exemple 5.1Urne de boules

Une urne contient $5$ boules rouges et $3$ boules vertes. On tire simultanément $3$ boules. La probabilité d'obtenir exactement $2$ rouges est le quotient du nombre de façons de choisir $2$ rouges parmi $5$ et $1$ verte parmi $3$ par le nombre total de tirages : $\frac{\dbinom{5}{2}\dbinom{3}{1}}{\dbinom{8}{3}} = \frac{10 \times 3}{56} = \frac{15}{28}.$ Le numérateur combine le principe multiplicatif, pour le « et », et le dénombrement par combinaisons, puisque l'ordre ne compte pas.

Méthodes

MéthodeRéflexes de dénombrement

Avant tout calcul, décrire précisément l'objet que l'on compte, par une phrase du type « un tel objet est la donnée de … ».
Poser les deux questions : l'ordre compte-t-il, les répétitions sont-elles possibles. En déduire la formule.
Quand la construction se fait par étapes, appliquer le principe multiplicatif, en vérifiant que le nombre de possibilités à chaque étape ne dépend pas des choix précédents.
Quand l'énoncé contient « au moins un », passer au complémentaire.
Quand l'énoncé contient « ou », vérifier si les cas sont disjoints. Sinon appliquer la formule du crible.
Quand on hésite, traiter le même problème avec de très petites valeurs, par exemple $n = 3$ et $p = 2$ , et énumérer à la main pour valider la formule.
Vérifier la cohérence de l'ordre de grandeur : un nombre de tirages simultanés doit être inférieur au nombre de tirages ordonnés correspondants.

Ce qu'il faut savoir refaire en khôlle

Énoncer et justifier la formule $\operatorname{card}(A \cup B) = \operatorname{card}(A) + \operatorname{card}(B) - \operatorname{card}(A \cap B)$ et l'appliquer à un échantillon biologique.
Justifier le nombre de $p$ -uplets et de $p$ -uplets sans répétition par le principe multiplicatif.
Expliquer pourquoi le nombre de $p$ -combinaisons s'obtient en divisant par $p!$ le nombre de $p$ -uplets sans répétition.
Dénombrer les applications et les applications injectives d'un ensemble fini dans un autre.
Démontrer que le cardinal de l'ensemble des parties est $2^n$ , par l'argument des choix binaires.
Traiter un calcul de probabilité en situation d'équiprobabilité avec tirage simultané, en gardant le même modèle au numérateur et au dénominateur.
Reconnaître, sur un énoncé rédigé en français, lequel des trois modèles s'applique.

Méthodes et exercices

Les résultats à connaître

Deux ensembles finis en bijection ont même cardinal : admis, usage exigible.
Si A ⊂ E avec E fini, card(A) ≤ card(E), avec égalité si et seulement si A = E : admis, d'usage courant.
Union disjointe : si A et B sont finis et disjoints, card(A ∪ B) = card(A) + card(B), et de même pour une famille finie de parties deux à deux disjointes : exigible, justification intuitive.
Pour A et B finis quelconques, card(A ∪ B) = card(A) + card(B) − card(A ∩ B) : exigible, justification intuitive.
Pour A ⊂ E, card(Ā) = card(E) − card(A) : exigible.
card(E × F) = card(E) × card(F), et de même pour p facteurs : exigible, justification intuitive.
Principe multiplicatif pour des choix successifs dont le nombre ne dépend pas des choix antérieurs : exigible.
Il y a n^p p-uplets d'un ensemble à n éléments : exigible.
Il y a n(n − 1)…(n − p + 1) p-uplets sans répétition pour 1 ≤ p ≤ n, aucun si p > n : exigible.
Il y a n! permutations d'un ensemble à n éléments, avec 0! = 1 : exigible.
Il y a C(n, p) parties à p éléments pour 0 ≤ p ≤ n : exigible, justification par division par p!.
card(P(E)) = 2ⁿ : exigible, justification par choix binaires.
De p éléments vers n éléments, il y a n^p applications et n(n − 1)…(n − p + 1) injections : exigible.
Relecture combinatoire de la formule du binôme : proposée par le programme.
Symétrie C(n, p) = C(n, n − p), relation de Pascal, p C(n, p) = n C(n − 1, p − 1) : établies par le calcul au chapitre des sommes. Leur lecture combinatoire est un bon exercice de khôlle.
Hors programme signalé : combinaisons avec répétition, surjections, crible à trois ensembles ou plus, coefficients multinomiaux. Le principe des tiroirs n'est pas cité, il se justifie en une phrase si besoin.

Clés de démonstration

Crible. A ∪ B est la réunion disjointe de A et des éléments de B hors de A. Comme B est la réunion disjointe de A ∩ B et de ces éléments, ceux-ci sont au nombre de card(B) − card(A ∩ B). L'astuce : découper en morceaux disjoints avant d'additionner.

Produit cartésien. On range les couples (x, y) dans un tableau, une ligne par élément de E, une colonne par élément de F. Chaque couple occupe une seule case. L'astuce : l'image du rectangle, puis un facteur à la fois.

p-uplets. On remplit les coordonnées de gauche à droite. Avec répétition, on a n choix par place. Sans répétition, les k valeurs déjà placées sont interdites, il reste n − k choix. L'astuce : le nombre de choix dépend du nombre de valeurs prises, jamais de leur identité, ce qui autorise le principe multiplicatif.

Combinaisons. On regroupe les p-uplets sans répétition selon l'ensemble de leurs valeurs. Chaque paquet correspond à une partie à p éléments et contient ses p! ordres. D'où n(n − 1)…(n − p + 1) = p! C(n, p). L'astuce : le « lemme des bergers », on compte les pattes et on divise par quatre.

Parties. On associe à A la liste (ε₁, …, ε_n), où ε_i vaut 1 si le i-ème élément est dans A et 0 sinon. C'est une bijection vers {0, 1}ⁿ, de cardinal 2ⁿ. L'astuce : transfert par bijection.

Symétrie. Le passage au complémentaire envoie les parties à p éléments sur celles à n − p éléments. Il est sa propre réciproque, donc bijectif.

Pascal. Dans un ensemble à n + 1 éléments, on distingue a. Les parties à k éléments contenant a sont au nombre de C(n, k − 1), les autres de C(n, k). Les cas sont disjoints, d'où C(n + 1, k). L'astuce : disjonction selon un élément distingué.

Comité. On compte les comités de k personnes parmi n munis d'un président. Comité puis président donne k C(n, k). Président puis k − 1 autres membres donne n C(n − 1, k − 1). L'astuce : double comptage.

Exemples et contre-exemples à connaître

Poignées de main : n personnes échangent C(n, 2) = n(n − 1)/2 poignées. Premier réflexe de la division par 2 pour effacer l'ordre.
Diagonales d'un polygone convexe à n sommets : les paires de sommets moins les n côtés, soit n(n − 3)/2, donc 9 pour l'hexagone.
Codons : 16 mots de deux bases, 64 de trois. Un code à doublets ne distingue pas 20 acides aminés, faute d'injection d'un ensemble à 20 éléments dans un ensemble à 16.
Loto : C(49, 5) = 1 906 884 grilles, soit 5! = 120 fois moins que de tirages ordonnés. Contrôle d'ordre de grandeur.
Chemins de grille de (0, 0) à (m, k) par pas unité vers la droite ou le haut : C(m + k, m), car un chemin est la donnée des positions des m pas à droite.
Contre-exemple, somme de deux dés : les 11 sommes ne sont pas équiprobables. Sur les 36 couples, 7 sort 6 fois, 2 une seule fois. L'équiprobabilité se pose sur l'univers.
Contre-exemple, nombres à trois chiffres distincts : en commençant par les centaines, non nulles, on trouve 9 × 9 × 8 = 648. En commençant par les unités, le nombre de choix pour les centaines dépend de la présence de 0. L'ordre de remplissage se choisit.
Contre-exemple, comités de 3 parmi 5 hommes et 4 femmes avec au moins une femme. La réponse est C(9, 3) − C(5, 3) = 84 − 10 = 74. Le calcul « une femme parmi 4 puis 2 personnes parmi 8 » donne 112. Il compte deux fois un comité à deux femmes et trois fois un comité à trois femmes.
Génotypes : pour k allèles chez un diploïde, k homozygotes et C(k, 2) hétérozygotes, soit k(k + 1)/2. Le système ABO donne 6 génotypes.

Techniques du chapitre

Technique 1, décrire l'objet avant de compter. Codes à 4 chiffres : un 4-uplet de {0, …, 9}, soit 10 000. À chiffres distincts : 10 × 9 × 8 × 7 = 5 040. À chiffres strictement croissants : une partie à 4 éléments rangée de façon unique, soit C(10, 4) = 210.

Technique 2, complémentaire pour « au moins ». On lance 4 fois un dé. Les résultats sans 6 sont 5⁴ = 625, donc 6⁴ − 5⁴ = 1 296 − 625 = 671 contiennent au moins un 6.

Technique 3, disjonction de cas. Mots de passe de 1 à 3 lettres minuscules : on découpe selon la longueur, cas disjoints. Total 26 + 676 + 17 576 = 18 278.

Technique 4, choisir les positions puis remplir. Séquences d'ADN de longueur 10 avec exactement 3 bases A : C(10, 3) = 120 choix de positions, puis 3⁷ = 2 187 remplissages des 7 autres places, soit 262 440. Anagrammes de GENOME : C(6, 2) = 15 positions pour les E, puis 4! = 24, soit 360.

Technique 5, crible. Entiers de 1 à 100 divisibles par 2 ou par 3 : 50 + 33 − 16 = 67, où 16 compte les multiples de 6.

Technique 6, construire une bijection. Pour n ≥ 1, autant de parties de cardinal pair que impair. On fixe a dans E. On ajoute a à X s'il est absent, on le retire s'il est présent. Cette application change la parité et est sa propre réciproque. Chaque catégorie compte 2ⁿ⁻¹ parties.

Technique 7, effacer l'ordre par une règle. Répartir 6 élèves en 3 binômes non numérotés : le premier par ordre alphabétique choisit son partenaire (5 choix), puis le premier des 4 restants (3 choix). Total 15. Contrôle : C(6, 2) × C(4, 2)/3! = 90/6 = 15.

Exercices classiques corrigés

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

Exercice 1

Classiques de khôlle et concours · Khôlle

Séquences d'ADN de longueur 6 : combien au total, sans base répétée, avec au moins un G, se lisant de la même façon dans les deux sens ?

Technique p-uplets, complémentaire, bijection.

Voir le corrigé

Une séquence est un 6-uplet de {A, C, G, T} : 4⁶ = 4 096.
Six bases distinctes parmi 4 est impossible : 0. Le produit 4 × 3 × 2 × 1 × 0 × (−1) contient bien un facteur nul.
Sans G : 3⁶ = 729. Avec au moins un G : 3 367.
Une séquence symétrique vérifie x₄ = x₃, x₅ = x₂, x₆ = x₁. Elle est déterminée par ses trois premières bases : 4³ = 64. Ce n'est pas le palindrome biologique, qui fait intervenir le brin complémentaire.

piège : « 6 places pour le G puis 4⁵ », soit 6 144, plus que le total.

Exercice 2

Classiques de khôlle et concours · Khôlle

Soient E = {1, …, p} et F = {1, …, n}. Dénombrer les applications de E dans F, les injections, les bijections si p = n, les applications strictement croissantes.

Technique traduction en p-uplets et en parties.

Voir le corrigé

Une application est la liste (f(1), …, f(p)) : n^p.
Elle est injective si et seulement si la liste est sans répétition : n(n − 1)…(n − p + 1) si p ≤ n, 0 sinon.
Si p = n, l'image d'une injection a n éléments et est incluse dans F, donc égale à F. D'où n! bijections.
Une application strictement croissante est déterminée par son image, partie à p éléments de F, et chaque partie en provient d'une seule, obtenue en rangeant ses éléments : C(n, p).

piège : « injective donc bijective » sans l'hypothèse p = n. Les applications croissantes au sens large sont hors programme.

Exercice 3

Classiques de khôlle et concours · Khôlle

Mains de 5 cartes dans un jeu de 32, qui compte 4 as et 8 hauteurs. Combien avec exactement 2 as, au moins un as, un carré ?

Technique combinaisons, principe multiplicatif, complémentaire.

Voir le corrigé

Une main est une partie à 5 éléments : C(32, 5) = 201 376.
Exactement 2 as : C(4, 2) × C(28, 3) = 6 × 3 276 = 19 656.
Sans as : C(28, 5) = 98 280. Au moins un as : 103 096.
Carré : 8 hauteurs, puis la cinquième carte parmi 28 : 224.

piège : 4 × C(31, 4) = 125 860 pour « au moins un as », le surcomptage de l'exemple 8.

Exercice 4

Classiques de khôlle et concours · Khôlle

Sur 200 individus, 80 portent la mutation M1, 60 la mutation M2, 90 aucune. Combien portent les deux ? Exactement une ?

Technique complémentaire puis crible.

Voir le corrigé

card(M1 ∪ M2) = 200 − 90 = 110.
card(M1 ∩ M2) = 80 + 60 − 110 = 30.
Seulement M1 : 50. Seulement M2 : 30. Exactement une : 80.
Contrôle : 50 + 30 + 30 + 90 = 200.

piège : Lire « porte M1 » comme « porte seulement M1 », ce qui donne un total de 230.

Exercice 5

Classiques de khôlle et concours · Khôlle

Six personnes, dont Ana et Basile, s'alignent au hasard. Probabilité qu'ils soient côte à côte ? Qu'Ana soit à gauche de Basile ?

Technique permutations, bloc, bijection par échange.

Voir le corrigé

L'univers compte 6! = 720 permutations équiprobables.
On soude Ana et Basile en un bloc : 5! = 120 rangements de 5 objets, fois 2 ordres dans le bloc, soit 240.
Contrôle : 5 paires de places voisines, 2 ordres, 4! pour les autres, soit 240.
Probabilité : 1/3.
Échanger Ana et Basile met en bijection « Ana à gauche » et « Basile à gauche ». Probabilité : 1/2.

piège : Oublier le facteur 2 dans le bloc.

Exercice 6

Classiques de khôlle et concours · Khôlle vers écrit

Chemins de (0, 0) à (4, 3) par pas unité vers la droite ou le haut. Combien ? Combien passent par (2, 1) ? Combien l'évitent ?

Technique choix des positions, produit de deux étapes.

Voir le corrigé

Un chemin compte 7 pas dont 3 vers le haut, déterminé par leurs positions : C(7, 3) = 35.
De (0, 0) à (2, 1) : C(3, 1) = 3. De (2, 1) à (4, 3) : C(4, 2) = 6.
Un chemin par (2, 1) est un couple de segments : 18.
Évitant (2, 1) : 17.

piège : Additionner les segments au lieu de les multiplier.

Exercice 7

Classiques de khôlle et concours · Écrit, type Agro-Véto

Urne de 6 boules rouges et 4 blanches, on tire 3 boules. Probabilité d'exactement 2 rouges en tirage simultané, successif sans remise, successif avec remise ?

Technique même modèle au numérateur et au dénominateur.

Voir le corrigé

Simultané : C(6, 2) × C(4, 1)/C(10, 3) = 60/120 = 1/2.
Sans remise, univers de 10 × 9 × 8 = 720 triplets. Rang de la blanche (3), rouges dans l'ordre (6 × 5), blanche (4) : 360, donc 1/2.
Avec remise, univers de 10³ triplets : 3 × 6² × 4 = 432, donc 0,432.
Les deux premiers modèles concordent, la remise change la probabilité.

piège : Diviser le nombre ordonné 360 par C(10, 3) = 120, ce qui donne 3, absurde. Ou oublier le rang de la blanche, ce qui donne 1/6.

Exercice 8. Pour n ≥ 1, montrer que la somme des k C(n, k), pour k de 0 à n, vaut n 2ⁿ⁻¹

Classiques de khôlle et concours · Écrit

Technique double comptage.

Voir le corrigé

Soit E à n éléments. On compte les couples (X, x) avec X partie de E et x élément de X.
Selon X : si card(X) = k, k choix de x, et C(n, k) telles parties. On obtient la somme.
Selon x : n choix, puis X est {x} réuni à une partie des n − 1 autres éléments, soit 2ⁿ⁻¹.
D'où l'égalité. En divisant par 2ⁿ, le cardinal moyen d'une partie vaut n/2.

piège : Trouver n × 2ⁿ en oubliant que x doit appartenir à X.

Exercice 9

Classiques de khôlle et concours · Écrit, plus délicat

Paradoxe des anniversaires. Naissances uniformes sur 365 jours, p personnes indépendantes. Montrer que pour p = 23, la probabilité qu'au moins deux personnes partagent un anniversaire dépasse 1/2.

Technique p-uplets sans répétition, complémentaire, inégalité 1 − x ≤ e^−x.

Voir le corrigé

L'univers compte 365^p p-uplets équiprobables.
« Tous distincts » correspond aux p-uplets sans répétition, de probabilité q_p égale au produit des (1 − k/365) pour k de 0 à p − 1.
Pour tout réel x, 1 − x ≤ e^−x, par étude de fonction ou convexité. Les facteurs étant positifs, q_p ≤ exp(−p(p − 1)/730).
Pour p = 23, p(p − 1)/730 = 253/365 ≈ 0,693151, qui dépasse de justesse ln 2 ≈ 0,693147, car 365 ln 2 ≈ 252,999. Donc q₂₃ < 1/2.
La probabilité cherchée 1 − q₂₃ dépasse 1/2. Sa valeur exacte vaut environ 0,507.

piège : Utiliser C(365, p), ce qui perd l'identité des personnes et l'équiprobabilité.

Exercice 10

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

Pour 1 ≤ p ≤ n, dénombrer les parties à p éléments de {1, …, n} sans deux entiers consécutifs. Application au loto.

Technique bijection par décalage.

Voir le corrigé

On range x₁ < … < x_p. La condition s'écrit x_i+1 − x_i ≥ 2.
On pose y_i = x_i − (i − 1). Alors y_i+1 − y_i ≥ 1 et 1 ≤ y₁ < … < y_p ≤ n − p + 1.
Réciproquement, x_i = y_i + i − 1 donne une partie admissible. Les deux constructions sont réciproques.
Réponse : C(n − p + 1, p), nulle si p > n − p + 1. Pour n = 5 et p = 2 : 6 parties, {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}.
Au loto, C(45, 5) = 1 221 759 grilles sur 1 906 884 sont sans consécutifs. Un tirage contient deux numéros consécutifs avec une probabilité d'environ 0,36.

piège : Ne vérifier qu'un sens de la bijection, ou oublier la borne n − p + 1.

Erreurs fréquentes

Mélanger les modèles : univers en tirages simultanés, événement compté en tirages ordonnés, ou l'inverse.
Traiter « au moins un » en fixant un objet puis en complétant librement, ce qui compte plusieurs fois la même configuration. Passer au complémentaire.
Appliquer le principe multiplicatif quand le nombre de choix dépend des choix précédents. Changer l'ordre de remplissage ou découper en cas.
Additionner des cas qui se recouvrent sans crible, ou ne pas contrôler qu'un sous-total reste inférieur au total.
Supposer équiprobables des issues qui ne le sont pas, comme les sommes de deux dés, ou négliger les cas limites : p > n donne zéro, et C(n, 0) = 1.

Fiche de cours rédigée à partir du programme officiel de BCPST 1ère année (2021), partie « Outils 7 – Dénombrement ». Elle couvre le cardinal d'un ensemble fini, les cardinaux d'une union et d'un produit cartésien, les $p$ -uplets avec ou sans répétition, les permutations, les $p$ -combinaisons et le cardinal de l'ensemble des parties.

Dénombrement

Résumé en cinq points

1Cardinal d'un ensemble fini

2Les deux principes de base

2.1Principe additif

2.2Principe multiplicatif

3Les quatre modèles de tirage

3.1ppp-uplets, ordre et répétitions

3.2ppp-uplets sans répétition

3.3Permutations

3.4ppp-combinaisons

3.5Tableau de décision

4Cardinal de l'ensemble des parties

5Lien avec les probabilités

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

Exercice 2

Exercice 3

Exercice 4

Exercice 5

Exercice 6

Exercice 7

Exercice 8. Pour n ≥ 1, montrer que la somme des k C(n, k), pour k de 0 à n, vaut n 2n−1

Exercice 9

Exercice 10

Erreurs fréquentes

3.1 $p$ -uplets, ordre et répétitions

3.2 $p$ -uplets sans répétition

3.4 $p$ -combinaisons

Exercice 8. Pour n ≥ 1, montrer que la somme des k C(n, k), pour k de 0 à n, vaut n 2ⁿ⁻¹