Cours
1. D’abord : quels objets compte-t-on ?
Le cardinal d’un ensemble fini E, noté \(|E|,\) est son nombre d’éléments. Un couple (A, B), un triplet (A, B, C) ou un k-uplet est une liste ordonnée. Une partie est un sous-ensemble : elle n’a pas d’ordre et ne répète pas ses éléments.
Ainsi, (A, B) et (B, A) sont deux couples différents, mais \(\{A,B\}=\{B,A\}.\) Le couple (A, A) répète A ; l’ensemble \(\{A,A\}\) est simplement \(\{A\}.\)
Le produit cartésien \(A\times B\) contient tous les couples \((a,b)\) avec \(a\in A\) et \(b\in B.\) Plus généralement, \(A_1\times\cdots\times A_k\) contient les listes dont chaque composante appartient à l’ensemble correspondant. \(A^k\) désigne les k-uplets d’éléments de A. Ces notions existent aussi pour des ensembles infinis ; ici, les dénombrements portent sur des ensembles finis.
2. Additionner des cas disjoints
Si les ensembles finis \(A_1,\ldots,A_m\) sont deux à deux disjoints,
\[\left|A_1\cup\cdots\cup A_m\right|=|A_1|+\cdots+|A_m|.\]Exemple : un badge est soit rouge, soit bleu, jamais les deux. Avec 4 badges rouges différents et 3 bleus différents, il existe \(4+3=7\) choix d’un badge.
On peut aussi compter le contraire : si F est inclus dans E, \(|E\setminus F|=|E|-|F|.\) C’est utile pour une contrainte « au moins un ».
3. Multiplier des choix successifs
\[|A_1\times\cdots\times A_k|=|A_1|\times\cdots\times|A_k|.\]Exemple : 3 entrées et 4 plats donnent 12 menus, si toute entrée peut être associée à tout plat. Sur un arbre, on multiplie les nombres de possibilités à chaque étape, quand ces nombres sont fixés quel que soit le choix précédent.
Si A a n éléments, une liste de longueur k avec répétitions autorisées offre n choix à chacune de ses k positions :
Avec 3 lettres, on forme \(3^2=9\) mots de longueur 2, dont AA, AB et BA. Un code peut commencer par 0 ; un nombre à plusieurs chiffres ne le peut pas : lire l’énoncé.
La liste vide est l’unique liste de longueur 0, même si A est vide. Si A est vide et k est strictement positif, aucune liste n’est possible.
4. Ordonner sans répétition et permuter
Pour une liste de k éléments distincts choisis parmi n, avec \(0\leq k\leq n,\) les nombres de choix sont n, puis n−1, etc. :
\[n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.\]Exemple : attribuer or, argent et bronze à trois personnes différentes parmi 5 donne \(5\times4\times3=60\) podiums. Ici, les rôles sont distincts.
Une permutation range tous les n éléments une seule fois. Leur nombre est la factorielle :
\[n!=1\times2\times\cdots\times n\quad(n\geq1),\]\[ 0!=1.\]Quatre livres tous distincts se rangent de \(4!=24\) façons. Pour k = 0, le produit vide vaut 1 ; pour k > n, une liste sans répétition est impossible.
5. Choisir sans ordre : les combinaisons
Une combinaison de k éléments parmi n est une partie à k éléments d’un ensemble à n éléments. Pour \(0\leq k\leq n,\) son nombre est noté \(\binom nk.\)
\[\binom nk=\frac{n!}{k!(n-k)!}.\]Pourquoi diviser par k! ? Chaque groupe de k éléments distincts donne exactement k! listes ordonnées. Le nombre de listes sans répétition vaut donc le nombre de groupes multiplié par k!.
Exemple : choisir 3 personnes sans rôle parmi 5 donne \(\binom53=60/6=10\) équipes, pas 60.
Cas à connaître :
\[\binom n0=\binom nn=1,\]\[\binom n1=n\ (n\geq1).\]\[\binom n2=\frac{n(n-1)}2\ (n\geq2).\]La complémentation associe à chaque partie à k éléments sa partie complémentaire à n−k éléments. C’est une correspondance bijective, d’où la symétrie :
\[\binom nk=\binom n{n-k}.\]6. Toutes les parties et tous les mots binaires
Pour construire une partie d’un ensemble à n éléments, on décide pour chaque élément : dedans (1) ou dehors (0). Il y a deux choix par élément, donc \(2^n\) parties, ensemble vide et ensemble entier compris.
Exemple : avec \(E=\{A,B,C\},\) le mot 101 code \(\{A,C\}.\) Les 8 mots binaires codent exactement les 8 parties. Pour n = 0, il reste une seule partie : l’ensemble vide.
À savoir démontrer — somme des coefficients binomiaux
On regroupe toutes les parties selon leur cardinal k, de 0 à n. Ces groupes sont disjoints et couvrent toutes les parties. Le groupe de taille k contient \(\binom nk\) parties. Le principe additif et le comptage binaire donnent donc
\[\sum_{k=0}^n\binom nk=2^n.\]Par exemple, pour n = 3 : \(1+3+3+1=8.\)
Lien avec 8C : choisir les k positions du succès parmi n revient à former un mot S/E contenant k succès. Il y a donc \(\binom nk\) chemins de ce type. Le chapitre 10 (loi binomiale) utilisera ce comptage pour calculer leurs probabilités.
7. Relation et triangle de Pascal
Pour \(n\geq1\) et \(0\leq k\leq n-1,\)
\[\binom nk+\binom n{k+1}=\binom{n+1}{k+1}.\]Chaque terme intérieur d’une ligne est la somme des deux termes juste au-dessus ; les deux bords valent 1. Les premières lignes sont : 1 ; 1, 1 ; 1, 2, 1 ; 1, 3, 3, 1. Exemple : \(\binom31+\binom32=3+3=6=\binom42.\)
À savoir démontrer — preuve par dénombrement
Dans un ensemble à n+1 éléments, distinguons un élément a. On compte les parties à k+1 éléments en deux cas disjoints.
- Celles contenant a : on choisit leurs k autres éléments parmi les n restants, soit \(\binom nk\) parties.
- Celles ne contenant pas a : on choisit les k+1 éléments parmi les n restants, soit \(\binom n{k+1}\) parties.
Ces deux cas couvrent toutes les \(\binom{n+1}{k+1}\) parties : leur somme donne la relation.
À savoir démontrer — preuve par le calcul
Les hypothèses assurent que toutes les factorielles suivantes sont définies. Posons \(D=(k+1)!(n-k)!.\) En utilisant les formules factorielles :
\[\binom nk=\frac{n!(k+1)}D,\]\[\binom n{k+1}=\frac{n!(n-k)}D.\]La somme a donc pour numérateur
\[\begin{aligned}n!\bigl((k+1)+(n-k)\bigr)\\{}=n!(n+1)=(n+1)!.\end{aligned}\]Comme \((n+1)-(k+1)=n-k,\) le dénominateur D est celui du coefficient \(\binom{n+1}{k+1}.\) Le quotient est donc exactement ce coefficient.
Un algorithme Python — construire la ligne n
def ligne_pascal(n):
ligne = [1]
for _ in range(n):
nouvelle = [1]
m = len(ligne)
for i in range(1, m):
a = ligne[i-1]
b = ligne[i]
nouvelle.append(a+b)
nouvelle.append(1)
ligne = nouvelle
return lignePour un entier n positif ou nul, on part de la ligne 0. Les nouveaux termes intérieurs sont calculés à partir de l’ancienne ligne, puis on ajoute les deux bords.
Méthode
Quatre questions pour choisir le bon calcul
- Décrire un objet : un code ordonné, une attribution de rôles, un groupe sans ordre ?
- Identifier les contraintes : taille fixée, répétition autorisée, objet obligatoire ou interdit ?
- Choisir le modèle : produit de nombres de choix, listes distinctes, permutation ou combinaison.
- Traiter la contrainte : additionner des cas disjoints ou retirer les cas interdits du total.
| Objet compté | Nombre |
|---|---|
| Liste de k positions, n choix à chaque position | \(n^k\) |
| k rôles distincts, sans répétition | \(n!/(n-k)!\) |
| Rangement de tous les n objets distincts | \(n!\) |
| Groupe de k objets distincts, sans ordre | \(\binom nk\) |
Pour les groupes et les listes sans répétition, les formules factorielles supposent \(0\leq k\leq n.\)
Pièges fréquents
- « Choisir » ne suffit pas : choisir un président et un secrétaire n’est pas choisir un groupe de deux personnes.
- Un tirage simultané de k objets distincts, sans rôle, se compte sans ordre.
- Pour « au moins un élève de A », choisir d’abord un élève de A puis compléter peut compter plusieurs fois la même équipe.
- Une équipe vide est un seul choix, pas zéro choix.
- Un dénombrement est un entier positif ou nul : aucune tolérance ni aucun arrondi n’est demandé.
Visualisation
Les mêmes lettres, trois façons de compter
On dispose des n premières lettres A, B, C… Compare les listes ordonnées avec répétitions, les listes sans répétition et les groupes sans ordre.
Dans un groupe, les accolades indiquent que l’ordre ne compte pas. Les listes sont écrites entre parenthèses. Les couleurs repèrent les lettres, pas des probabilités.
Un sous-ensemble, un mot binaire
Les boutons utilisent le même ensemble de n lettres. Active une lettre pour l’inclure : le bit correspondant passe de 0 à 1. Ce choix est libre, indépendamment de la taille k du premier explorateur.
Pascal : retrouver les deux parents
Le triangle commence à la ligne 0 et les positions commencent à 0. Aux bords, le coefficient vaut 1 ; à l’intérieur, les deux parents verts s’additionnent. La somme de la ligne vaut le nombre de parties.
Exercices
Donne le nombre exact demandé : un entier positif ou nul, sans arrondi.
Exercice 1 · Former un identifiant Niveau 1
Exercice 2 · Attribuer des postes distincts Niveau 2
Exercice 3 · Former une équipe sous contrainte Niveau 3
QCM
Quatre questions tirées dans une banque de quinze. Une seule réponse correcte par question.