Dénombrement

Première grande partie de R3.08 et le socle de tout le semestre : avant de calculer une probabilité, il faut compter les cas possibles — et les compter sans en oublier ni les compter deux fois. Cette page suit la Leçon 1 : les deux principes, le modèle de l'urne et ses quatre formules, les anagrammes, le binôme de Newton — puis la fiche de TD n°1 corrigée exercice par exercice.

Cours

Le problème : compter sans compter un par un

Imagine que tu dois compter les spectateurs d'un stade. Tu peux compter les personnes une par une… 1, 2, 3, 4… et tu vas y passer l'après-midi, avec une incertitude à la fin. Ou alors tu remarques qu'il y a 40 rangées de 250 sièges : 40 × 250 = 10 000 places, calcul de trois secondes. Le dénombrement, c'est exactement ça : l'art de compter des choses sans les compter une par une, en rusant avec des multiplications et des additions.

Pourquoi c'est important ? Parce qu'à partir de la leçon suivante, on va calculer des probabilités, du genre « quelle chance d'avoir une main avec un roi quand je pioche 8 cartes ? ». Or une probabilité, c'est :

probabilité = nombre de cas qui nous arrangent / nombre total de cas

Le numérateur et le dénominateur sont des comptes de cas : si le comptage est faux, la probabilité est fausse. Tout le semestre repose donc sur cette leçon. Et « compter juste » veut dire : sans oublier de cas, sans compter deux fois le même. Toute la suite n'est qu'une boîte à outils pour faire exactement ça.

Les deux principes : multiplicatif et additif

Le principe multiplicatif : les étapes qui s'enchaînent

C'est le principe le plus important de la leçon. Il répond à la question : « je fais plusieurs choix l'un après l'autre — combien de combinaisons au total ? ». L'image : une pizzeria. Tu choisis une taille (2 choix : petite ou grande), puis une pâte (3 choix : fine, épaisse, fourrée), puis une boisson (2 choix : soda ou jus). Tu peux lister les menus un par un… ou remarquer que chaque taille se combine avec chaque pâte, qui se combine avec chaque boisson :

Nombre de possibilités = n₁ × n₂ × ⋯ × nₚ

où p est le nombre d'étapes, n₁ le nombre de choix à la première étape, n₂ à la deuxième, etc. Ici : 2 × 3 × 2 = 12 menus. Visuellement, chaque étape « multiplie les branches » : chaque chemin déjà construit se dédouble (ou se triple) en autant de nouveaux chemins.

L'exemple du cours : une personne a deux pantalons P₁, P₂, trois chemises C₁, C₂, C₃ et deux vestes V₁, V₂. S'habiller, c'est trois étapes — pantalon, puis chemise, puis veste — soit 2 × 3 × 2 = 12 tenues. Chaque chemin de la racine à une feuille de l'arbre ci-dessous est une tenue, et un chemin complet (« P₁ puis C₁ puis V₁ ») est une et une seule tenue : c'est ça qui garantit qu'on ne compte rien deux fois.

Le principe additif : la distinction de cas

Deuxième situation : tu ne fais pas plusieurs choix à la suite, tu as plusieurs possibilités qui s'excluent. L'image : pour rentrer chez toi, tu peux prendre le train (4 horaires) ou le bus (6 horaires). Tu ne prendras jamais les deux — jamais un « chemin train » ne sera aussi un « chemin bus ». On additionne donc des monceaux de cas qui ne se recouvrent pas :

Nombre de possibilités = m₁ + m₂ + ⋯ + mᵣ

où r est le nombre de cas qu'on distingue et mₖ le nombre de possibilités du cas k. Et à l'intérieur de chaque cas, on peut très bien re-multiplier : le principe multiplicatif sert souvent à compter chaque mₖ.

L'exemple du cours : on reprend pantalons, chemises et vestes, mais avec une restriction — le pantalon P₁ ne va pas du tout avec la chemise C₃. L'arbre des 12 tenues se brise : les deux branches « P₁–C₃–V₁ » et « P₁–C₃–V₂ » n'existent plus. On distingue deux cas :

• cas 1, je prends P₁ : 1 seul pantalon, mais plus que 2 chemises (C₃ interdite) et 2 vestes → 1 × 2 × 2 = 4 ;
• cas 2, je ne prends pas P₁ : 1 pantalon (P₂), 3 chemises, 2 vestes → 1 × 3 × 2 = 6.

Au total : 4 + 6 = 10 tenues — et le schéma montre bien les mêmes 10 chemins.

Factorielle et permutations

Nouvelle question : 6 amis veulent s'asseoir sur un banc de 6 places. De combien de façons ? C'est comme une photo de groupe : l'ordre compte (Alice au milieu ou au bout du banc, ce n'est pas la même photo). On compte par étapes — le principe multiplicatif encore :

• la place 1 : n'importe lequel des 6 amis peut la prendre → 6 choix ;
• la place 2 : il ne reste que 5 amis → 5 choix ;
• la place 3 : 4 choix… et ainsi de suite, jusqu'à la dernière place où il ne reste qu'une personne (1 choix).

6 × 5 × 4 × 3 × 2 × 1 = 720 façons d'asseoir les 6 amis

Ce produit qui « descend » de n jusqu'à 1 est si utile qu'il a un nom : la factorielle de n, écrite n! (« factorielle n ») :

n! = n × (n−1) × (n−2) × ⋯ × 3 × 2 × 1        et par convention  0! = 1

Par exemple 3! = 6 et 4! = 24. La convention 0! = 1 n'est pas capricieuse : il y a exactement une façon d'asseoir zéro personne sur un banc (le banc reste vide) — la formule doit le confirmer, donc 0! vaut 1.

Un arrangement de tous les objets s'appelle une permutation : le nombre de permutations de n objets, c'est n!. Et la factorielle simplifie très bien les fractions — réflexe utile au DS : dans 9!/7!, presque tout se raccourcit,

9!/7! = (9 × 8 × 7!)/7! = 9 × 8 = 72

car 9! contient 7! « en queue » : 9! = 9 × 8 × 7 × 6 × ⋯ × 1 = 9 × 8 × 7!. Ne garder que le début du produit, c'est tout le principe des arrangements qui suivent.

Le modèle de l'urne : quatre situations, quatre formules

À partir de là, tout le cours tient dans une seule image : une urne (un grand bocal) contient n boules toutes différentes (numérotées, par exemple), et on tire k boules. C'est le jeu de société de base du dénombrement, et il n'a que deux interrupteurs :

• l'ordre compte-t-il ? Tirer 12 puis 7, est-ce différent de tirer 7 puis 12 ? Pour un code de coffre-fort, oui ; pour une poignée de boules sortie d'un coup, non ;
• remet-on la boule ? Après un tirage, je reverse la boule dans le bocal (elle peut ressortir) ou elle sort du jeu ?

Deux interrupteurs à deux positions : quatre situations, quatre formules. Prenons-les une par une.

Avec ordre, sans remise : les arrangements A(n, k)

Reprends la photo de groupe, mais le banc n'a que 4 places pour 6 amis : 2 amis resteront debout. Compte par étapes, comme tout à l'heure : 6 choix pour la place 1, puis 5, puis 4, puis 3 — le produit s'arrête en route :

6 × 5 × 4 × 3 = 360 façons de placer 4 amis parmi 6

« Sans remise », c'est exactement ça : chaque ami choisi quitte la file, il ne peut pas être rechoisi — à chaque étape il reste un choix de moins, d'où un produit qui descend : n, puis n−1, … jusqu'à n−k+1. Ce coefficient s'appelle le coefficient d'arrangements et se note A(n, k) :

A(n, k) = n × (n−1) × ⋯ × (n−k+1) = n! / (n−k)!      (k ≤ n)

La version factorielle se lit ainsi : le produit complet n!, coupé après k facteurs — on divise par la « queue » qu'on ne veut pas, (n−k)!. L'urne version : huit boules numérotées de 1 à 8, cinq tirages sans remise en notant l'ordre (« le tirage 6-2-2-5-1 » : d'abord la 6, deux fois la 2, puis la 5 et la 1) — A(8, 5) = 8 × 7 × 6 × 5 × 4 = 6720 tirages.

Avec ordre, avec remise : nᵏ

Maintenant on remet la boule après chaque tirage : à chaque étape, le bocal est complet à nouveau — n choix à chaque coup, k fois de suite. C'est le cadenas à molettes : un cadenas de k molettes, chacune gravée de n chiffres, a exactement nᵏ combinaisons, parce que tourner une molette ne gêne pas les autres — on a le droit de remettre le même chiffre partout.

Nombre de possibilités = nᵏ      (k tirages, avec remise, ordre compté)

Exemples du cours : les mots de 3 lettres formés avec A ou B — 2³ = 8 mots (AAA, BAA, ABA, AAB, ABB, BAB, BBA, BBB) ; et l'urne des 8 boules, 5 tirages avec remise : 8⁵ = 32 768 tirages. Compare avec les 6720 du paragraphe précédent : autoriser la remise fait exploser le compte, puisqu'on ne retire plus personne du jeu.

Sans ordre, sans remise : les combinaisons C(n, k)

Là, on quitte l'ordre une bonne fois : on tire k boules d'un coup, comme une poignée de billes — peu importe l'ordre de sortie, c'est la même poignée. Idem pour une main de poker ou un groupe de 2 délégués : ce sont les mêmes personnes, donc le même groupe, quel que soit l'ordre du vote.

Comment compter ça, nous qui savons compter « avec ordre » ? L'astuce du cours — et c'est LA démonstration à comprendre : comptons les arrangements A(n, k) de deux façons différentes.

1. Directement : il y en a A(n, k), on le sait déjà.
2. Autrement : d'abord je choisis le groupe de k objets — disons C(n, k) façons — puis j'arrange ces k objets dans l'ordre : k! façons. Par le principe multiplicatif : C(n, k) × k! arrangements en tout.

Les deux comptes décrivent la même chose, donc A(n, k) = C(n, k) × k!, et en retournant la formule :

C(n, k) = A(n, k) / k! = n! / (k!(n−k)!)

Intuition de la division par k! : quand tu comptes les groupes avec l'ordre, chaque groupe est compté k! fois — une fois par ordre de passage de ses membres. Pour les délégués Aline et Brahim, tu as compté « Aline puis Brahim » et « Brahim puis Aline » : 2! = 2 comptes pour une seule équipe. On divise donc par k! pour corriger le sur-comptage.

Au loto : 5 boules tirées parmi 49, l'ordre ne compte pas — C(49, 5) = 1 906 884 grilles. Remarque du cours : tirer les boules une par une sans tenir compte de l'ordre revient exactement à les tirer toutes en même temps (simultanément).

Quatre coefficients à connaître par cœur — ils font gagner du temps au DS :

C(n, 0) = C(n, n) = 1        (une seule façon de ne rien choisir, ou de tout choisir)
C(n, 1) = C(n, n−1) = n      (n façons d'en choisir un — ou d'en écarter un)
C(n, n−k) = C(n, k)          (choisir k, c'est écarter n−k : la symétrie)

Sans ordre, avec remise : C(n+k−1, k)

Le dernier cas est le plus retors, mais c'est le plus sympathique : celui des bonbons. Tu distribues k bonbons identiques à n enfants, et un enfant peut recevoir plusieurs bonbons — « avec remise », c'est ça : une personne peut ressortir plusieurs fois.

Comment compter ? Le cours propose un codage génial : mets les enfants en file, et écris ce qui se passe lettre par lettre. B pour « donner un bonbon » (à la personne devant toi), A pour « avancer à la personne suivante ». Distribuer 4 bonbons à 6 enfants, c'est écrire un mot avec 4 B et 5 A — 9 lettres au total, par exemple :

B-B-A-B-A-B-A-B-A-A   →  l'enfant 1 reçoit 2 bonbons, le 2e en a 1,
                         le 3e et le 4e aucun, le 5e un, le 6e aucun

Chaque répartition de bonbons correspond à exactement un mot, et chaque mot à exactement une répartition. Compter les répartitions, c'est donc compter les anagrammes d'un mot de 9 lettres avec 4 B identiques et 5 A identiques — et ça tombe sur un coefficient binomial :

Distribuer k objets identiques dans n boîtes = C(n+k−1, k)

Pour 4 bonbons et 6 enfants : C(9, 4) = 126 façons. Et c'est aussi le dernier cas de l'urne : tirer k boules avec remise en ne tenant pas compte de l'ordre (le tirage 2-2-6-3, c'est le tirage 2-6-2-3), revient exactement à distribuer k « bonbons » aux n boules du jeu.

Anagrammes : quand les lettres sont des jumeaux

Un anagramme d'un mot, c'est un nouveau mot fabriqué en permutant ses lettres. Si toutes les lettres sont différentes, rien de nouveau : permuter 3 lettres distinctes, c'est les placer sur 3 positions — 3! = 6 anagrammes de BAC.

Les choses se corsent quand le mot contient des lettres identiques. Prends le mot ANA : il n'a que 3 anagrammes (AAN, ANA, NAA) et non 3! = 6. Pourquoi ? Parce qu'il a deux A jumeaux : échanger les deux A entre eux ne change rien du tout — comme échanger deux jumeaux habillés pareil, personne ne s'en aperçoit. Compter 3!, c'est donc compter chaque mot plusieurs fois, une fois par échange invisible des jumeaux.

Le moyen sûr : choisir les emplacements. Dans NANNA (5 lettres : 3 N et 2 A), un anagramme est entièrement déterminé par la place des 2 A — choisir 2 emplacements parmi 5, donc C(5, 2) = 10 anagrammes.

Mot à n lettres dont k lettres identiques (et n−k identiques entre elles) :
nombre d'anagrammes = C(n, k)

Autre exemple du cours : MAMAMMA — 7 lettres, 4 M et 3 A — donne C(7, 4) = 35 anagrammes. Et quand il y a trois groupes de jumeaux (comme ÉTETÉE : É × 3, T × 2, E × 2), on divise 7! par chaque factorielle de groupe : 7!/(3! · 2! · 2!) = 210. C'est exactement le mécanisme de l'exercice 8 — et du codage « bonbons » juste au-dessus.

La formule du binôme de Newton

Dernière notion : développer une puissance comme (a+b)⁵ sans tout multiplier à la main. D'où sortent les coefficients du développement ? D'un comptage de chemins, encore. (a+b)⁵, c'est 5 copies du même choix : chaque facteur (a+b) est un copain qui choisit « a » ou « b » — comme 5 amis qui doivent trancher entre pizza et burger. Dérouler le produit, c'est écrire les choix des 5 copains, par exemple aaabb (les deux premiers ont pris a, les trois autres b). Quel est le coefficient devant a³b² ? Le nombre de mots de 5 lettres avec exactement 3 a et 2 b — tu reconnais une anagramme : C(5, 2) = 10.

(a+b)ⁿ = Σ (k = 0 → n)  C(n, k) · aᵏ · bⁿ⁻ᵏ        (binôme de Newton)

Sur l'exemple complet : (a+b)⁵ = a⁵ + 5a⁴b + 10a³b² + 10a²b³ + 5ab⁴ + b⁵ — les coefficients 1, 5, 10, 10, 5, 1 sont exactement C(5, 0), C(5, 1), …, C(5, 5). Deux remarques du cours :

• les rôles de a et b sont interchangeables : C(n, k) = C(n, n−k) — le coefficient de a⁴b dans (a+b)⁵ est C(5, 4), qui vaut C(5, 1) = 5, pareil ;
• avec a = b = 1, chaque terme vaut C(n, k) et (1+1)ⁿ = 2ⁿ, donc :

C(n, 0) + C(n, 1) + ⋯ + C(n, n) = 2ⁿ

Interprétation : 2ⁿ, c'est le nombre de sous-ensembles d'un ensemble à n éléments — pour chaque objet, deux choix : « je le prends » ou « je le laisse » (comme faire ses valises : n objets, chacun dans la valise ou dehors, ça fait 2ⁿ valises possibles). Et additionner les C(n, k), c'est compter les sous-ensembles par taille : 1 vide, n à un élément, etc.

La table de correspondance à savoir refaire

Le résumé de la Leçon 1 : à chaque action, sa formule. C'est LA table à savoir reconstruire le jour J — les exercices ci-dessous la parcourent dans tous les sens. Pour la retrouver sans l'apprendre par cœur, redescends les deux interrupteurs : ordre ? remise ?

Exercices

Les neuf exercices de la fiche de TD n°1, énoncés en condensé. Cherchez avant d'ouvrir chaque solution — le premier est LE réflexe à entretenir pour le DS, et à la fin, la somme des résultats de l'exercice 6 doit faire tilt.

Exercice 1 — Reconnaître le bon modèle (le réflexe n°1 du DS)

Dix situations, et pour chacune les deux mêmes questions : un élément peut-il être choisi plusieurs fois (remise ?), l'ordre de choix a-t-il une influence sur le résultat (ordre ?) — puis quel modèle : nᵏ, A(n, k), C(n+k−1, k) ou C(n, k) ?

a. un mot de passe de 6 caractères parmi 26 lettres minuscules, répétitions autorisées ; b. parmi 10 nœuds disponibles, désigner lequel sera maître, lequel secours et lequel logs (trois rôles distincts, un nœud n'a qu'un rôle) ; c. sélectionner 4 bibliothèques parmi 15 compatibles pour un projet (aucune notion de rôle ni d'ordre, on veut juste savoir lesquelles) ; d. un algorithme de hachage attribue une valeur (parmi 256 possibles) à chacune des 5 clés d'une entrée, indépendamment ; e. distribuer 6 tickets de support identiques à 4 techniciens, un technicien pouvant recevoir plusieurs tickets ; f. tirer au sort l'ordre de passage de 8 équipes sur un même terrain (chaque équipe passe une seule fois) ; g. former une équipe de 3 personnes parmi 12 candidats pour un hackathon, sans distinction de rôle au sein de l'équipe ; h. générer une adresse IPv4 en tirant successivement 4 octets, chaque octet valant ce qu'il veut entre 0 et 255, indépendamment des autres ; i. répartir 5 bugs identiques entre 3 développeurs, un développeur pouvant en avoir plusieurs ou aucun ; j. choisir 2 étudiants parmi 30 pour passer au tableau, le premier interrogé en premier, le second en second (deux moments distincts, deux questions différentes).

Exercice 2 — S'habiller (principes multiplicatif et additif)

On dispose de 4 slips, 3 pantalons, 2 tee-shirts et 5 paires de chaussures ; on ne porte pas plusieurs vêtements du même type, et jamais une chaussure gauche au pied droit (ni l'inverse).

1. De combien de manières peut-on s'habiller ?
2. On n'est pas obligé de s'habiller complètement : on peut sortir sans tee-shirt ou avec une seule chaussure — mais le pantalon est obligatoire si l'on ne porte pas de slip. Combien de manières maintenant ?

4 × 3 × 2 × 5 = 120 manières

1728 + 324 = 2052 tenues

Exercice 3 — Le menu étudiant (le prix de l'affiche)

Une affiche de fast-food annonce le menu étudiant au prix :

A = − Σ (i = 1 → 461)  (−1)ⁱ · [ (5! × 5) / 4! ]^(1/2)  +  0,95 €

Quel est ce prix ?

A = −5 × (−1) + 0,95 = 5,95 €

Exercice 4 — Le digicode

Un digicode est composé d'une lettre A ou B suivie de trois chiffres (exemples : A334, B210).

1. Combien existe-t-il de digicodes ?
2. Combien si tous les caractères sont distincts ?
3. Combien n'ayant pas deux caractères consécutifs identiques ?

2 × 10³ = 2000 digicodes

2 × 10 × 9 × 8 = 1440 = 2 × A(10, 3) digicodes

2 × 10 × 9 × 9 = 1620 digicodes

Exercice 5 — Poker : les mains de 8 cartes sur 32

On pioche 8 cartes (une « main ») dans un jeu de 32 cartes — 4 rois, 8 cœurs, l'ordre de tirage ne compte pas.

1. Combien peut-on former de mains ?
2. Combien de mains contenant exactement un roi ?
3. Combien de mains contenant exactement trois cœurs ?
4. Combien de mains contenant au moins trois cœurs ?

C(32, 8) = 10 518 300 mains

C(4, 1) × C(28, 7) = 4 × 1 184 040 = 4 736 160 mains

C(8, 3) × C(24, 5) = 56 × 42 504 = 2 380 224 mains

|cœurs ≥ 3| = C(32,8) − C(24,8) − C(8,1)·C(24,7) − C(8,2)·C(24,6)
            = 10 518 300 − 735 471 − 2 768 832 − 3 768 688
            = 3 245 309 mains

Exercice 6 — Les codes PIN à quatre chiffres

Combien de codes PIN à 4 chiffres ont :

1. tous leurs chiffres identiques ?
2. tous leurs chiffres distincts ?
3. deux doublons (comme 1331 ou 2020) ?
4. exactement un doublon (comme 2625) ?
5. exactement trois fois un même chiffre ?
6. Et que vaut la somme de tous ces résultats ?

A(10, 4) = 10 × 9 × 8 × 7 = 5040 codes

C(10, 2) × 4!/(2!·2!) = 45 × 6 = 270 codes

C(10, 3) × 3 × 4!/2! = 120 × 3 × 12 = 4320 codes

10 × 9 × 4 = 360 codes

10 + 5040 + 270 + 4320 + 360 = 10 000 = 10⁴

Exercice 7 — Distribuer des billets

On distribue 10 billets de 100 € (indiscernables) à 6 personnes différentes.

1. De combien de manières, si une personne peut recevoir plusieurs billets ?
2. Combien si l'on veut donner au moins 100 € à chaque personne ?

C(15, 5) = 3003 manières

C(9, 4) = 126 manières

Exercice 8 — Anagrammes

Combien d'anagrammes peut-on former avec les lettres de : BUTINFO, ÉTETÉE, PROBABILITÉS, PAPAPÉETE ?

7! = 5040 anagrammes

7! / (3! · 2! · 2!) = 5040 / 24 = 210 anagrammes

12! / (2! · 2!) = 479 001 600 / 4 = 119 750 400 anagrammes

9! / (3! · 2! · 2!) = 362 880 / 24 = 15 120 anagrammes

Exercice 9 — Binôme de Newton

Quel est le coefficient de x⁴y⁵ dans le développement de (x + y)⁹ ?

C(9, 4) = 126

A retenir

• deux principes : multiplicatif pour les étapes qui s'enchaînent (n₁ × n₂ × ⋯ × nₚ), additif pour des cas disjoints (m₁ + ⋯ + mᵣ) — l'arbre de choix les visualise tous les deux ;
• factorielle : n! = n × (n−1) × ⋯ × 1, 0! = 1 ; permuter n objets : n! ;
• le modèle de l'urne, quatre formules : ordre + sans remise → A(n, k) ; ordre + remise → nᵏ ; sans ordre + sans remise → C(n, k) ; sans ordre + remise → C(n+k−1, k) ;
• anagrammes d'un mot à n lettres dont k identiques : C(n, k) — et plus généralement on divise par la factorielle de chaque groupe de doublons ;
• binôme de Newton : le coefficient de aᵏbⁿ⁻ᵏ dans (a+b)ⁿ vaut C(n, k), et Σ C(n, k) = 2ⁿ ;
• réflexes d'examen : « au moins » → événement contraire ; découpage en cas → vérifier que la somme des cas redonne le total.