Dénombrement et combinatoire

• Déterminer le cardinal d'une réunion d'ensembles finis disjoints (principe additif) et utiliser le complémentaire.
• Déterminer le cardinal d'un produit cartésien (principe multiplicatif) et représenter une situation de choix successifs par un arbre.
• Dénombrer les k-uplets (listes ordonnées avec répétition possible) d'un ensemble à n éléments.
• Dénombrer les arrangements (k-uplets d'éléments distincts) et les permutations d'un ensemble fini.
• Calculer une factorielle et simplifier un quotient de factorielles.
• Dénombrer les combinaisons (parties à k éléments) d'un ensemble à n éléments et calculer un coefficient « k parmi n ».
• Démontrer et utiliser les propriétés des combinaisons : symétrie, relation de Pascal, somme égale à 2ⁿ.
• Construire le triangle de Pascal et l'utiliser pour développer une puissance de (a + b) par la formule du binôme.
• Choisir le bon modèle (ordre ou non, répétition ou non) à partir d'un énoncé et l'appliquer au calcul d'une probabilité en situation d'équiprobabilité.

1. Ensembles finis, cardinal et principe additif

Un ensemble E est fini s'il possède un nombre fini d'éléments. Ce nombre est le cardinal de E, noté card(E). Par convention, l'ensemble vide ∅ a pour cardinal 0.

Exemple : E = {a, b, c, d} a pour cardinal 4. L'ensemble des chiffres {0, 1, 2, ..., 9} a pour cardinal 10.

Dénombrer, c'est compter les éléments d'un ensemble sans les écrire tous, en ramenant le comptage à des règles générales. Deux règles portent toute la suite du chapitre : le principe additif et le principe multiplicatif.

Principe additif. Si A et B sont deux ensembles finis disjoints (A ∩ B = ∅), alors :

card(A ∪ B) = card(A) + card(B).

Plus généralement, si A₁, A₂, ..., Aₚ sont deux à deux disjoints, le cardinal de leur réunion est la somme de leurs cardinaux. On dit que les Aᵢ forment une partition de leur réunion quand ils sont non vides et deux à deux disjoints.

Pourquoi ? Chaque élément de la réunion appartient à un et un seul des ensembles : en comptant chaque ensemble séparément puis en additionnant, aucun élément n'est oublié ni compté deux fois.

Si A et B ne sont pas disjoints, les éléments de A ∩ B sont comptés deux fois dans card(A) + card(B). D'où :

card(A ∪ B) = card(A) + card(B) − card(A ∩ B).

Complémentaire. Si A est une partie de E, son complémentaire Ā (éléments de E qui ne sont pas dans A) vérifie A ∪ Ā = E et A ∩ Ā = ∅, donc :

card(Ā) = card(E) − card(A).

Cette égalité est l'outil de base des énoncés « au moins un » : il est souvent bien plus simple de compter les cas où il n'y en a « aucun », puis de les retirer du total.

2. Produit cartésien et principe multiplicatif

Le produit cartésien de deux ensembles A et B, noté A × B, est l'ensemble des couples (a ; b) avec a dans A et b dans B. L'ordre compte : (a ; b) et (b ; a) sont deux couples différents dès que a ≠ b.

Principe multiplicatif. Si A et B sont finis :

card(A × B) = card(A) × card(B).

Plus généralement, card(A₁ × A₂ × ... × Aₚ) = card(A₁) × card(A₂) × ... × card(Aₚ).

Justification : pour chacun des card(A) choix du premier élément, il y a card(B) choix du second. Le nombre total de couples s'obtient en additionnant card(B) autant de fois qu'il y a d'éléments dans A (principe additif appliqué à une partition de A × B selon le premier élément), ce qui donne le produit.

On visualise ce principe par un arbre de choix : chaque niveau correspond à un choix, chaque branche à une option. Si chaque nœud d'un niveau a le même nombre de branches, le nombre de chemins complets est le produit des nombres de branches de chaque niveau.

Exemple : une tenue est formée d'un haut (5 possibilités), d'un bas (3 possibilités) et d'une paire de chaussures (2 possibilités). Le nombre de tenues est 5 × 3 × 2 = 30.

Le principe multiplicatif reste valable quand l'ensemble des options du deuxième choix dépend du premier choix, pourvu que leur nombre n'en dépende pas. C'est ce qui permet de compter les arrangements (paragraphe 4).

3. k-uplets et nombre de parties d'un ensemble

Soit E un ensemble à n éléments et k un entier naturel non nul. Un k-uplet (ou k-liste) d'éléments de E est une suite ordonnée (x₁ ; x₂ ; ... ; xₖ) de k éléments de E, non nécessairement distincts. C'est un élément de E × E × ... × E (k facteurs), noté Eᵏ.

Propriété. Le nombre de k-uplets d'un ensemble à n éléments est nᵏ.

C'est le principe multiplicatif : n choix pour chacune des k positions.

Exemples :

• un code de carte bancaire à 4 chiffres est un 4-uplet de {0, ..., 9} : il y en a 10⁴ = 10 000 ;
• une suite de 3 lancers d'une pièce (P ou F) est un 3-uplet de {P, F} : il y en a 2³ = 8 ;
• un brin d'ADN de 5 nucléotides (A, C, G, T) est un 5-uplet d'un ensemble à 4 éléments : il y en a 4⁵ = 1 024.

Situation type : tirages successifs avec remise de k objets parmi n. L'ordre compte et un même objet peut sortir plusieurs fois.

Nombre de parties d'un ensemble. Une partie (ou sous-ensemble) de E est un ensemble dont tous les éléments appartiennent à E (∅ et E lui-même sont des parties de E). L'ensemble des parties de E est noté P(E).

Théorème. Un ensemble à n éléments possède 2ⁿ parties.

Démonstration. Numérotons les éléments de E : e₁, e₂, ..., eₙ. À toute partie A de E, on associe le n-uplet (c₁ ; ... ; cₙ) de {0 ; 1} défini par cᵢ = 1 si eᵢ appartient à A et cᵢ = 0 sinon. Réciproquement, tout n-uplet de 0 et de 1 définit une unique partie (celle des eᵢ pour lesquels cᵢ = 1). Cette correspondance est donc une bijection entre P(E) et {0 ; 1}ⁿ, qui contient 2ⁿ éléments. Ainsi card(P(E)) = 2ⁿ.

Exemple : E = {a, b, c} a 2³ = 8 parties : ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}.

4. Factorielle, arrangements et permutations

Factorielle. Pour tout entier naturel n non nul, on appelle factorielle n le nombre :

n! = 1 × 2 × 3 × ... × n.

Par convention, 0! = 1. On a la relation de récurrence (n + 1)! = (n + 1) × n!, qui permet les simplifications :

8!/6! = 8 × 7 = 56 ; 10!/(9!) = 10.

Valeurs à connaître : 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720, 7! = 5 040, 8! = 40 320, 10! = 3 628 800. La factorielle croît extrêmement vite : 20! dépasse déjà 2 × 10¹⁸.

Arrangements. Soit E un ensemble à n éléments et k un entier avec 1 ≤ k ≤ n. Un arrangement de k éléments de E est un k-uplet d'éléments deux à deux distincts de E.

Propriété. Le nombre d'arrangements de k éléments parmi n est :

n × (n − 1) × ... × (n − k + 1) = n!/(n − k)!.

Ce produit comporte exactement k facteurs. Justification : n choix pour le premier élément, puis n − 1 pour le second (il doit différer du premier), ..., puis n − k + 1 pour le k-ième. Le nombre d'options ne dépend pas des choix précédents, seulement de leur nombre, donc le principe multiplicatif s'applique. Enfin, en multipliant et divisant par (n − k)!, on obtient l'écriture n!/(n − k)!.

Si k > n, il n'existe aucun arrangement (on ne peut pas choisir plus d'éléments distincts qu'il n'y en a).

Situation type : tirages successifs sans remise de k objets parmi n, ou attribution de k rôles distincts à k personnes différentes.

Exemple : dans un club de 12 membres, on élit un président, un trésorier et un secrétaire (trois personnes différentes). Il y a 12 × 11 × 10 = 1 320 bureaux possibles.

Permutations. Une permutation de E est un arrangement de ses n éléments : c'est une façon de les ranger tous dans un ordre.

Propriété. Le nombre de permutations d'un ensemble à n éléments est n!.

Exemple : 6 élèves peuvent s'asseoir sur 6 chaises alignées de 6! = 720 façons. Les anagrammes du mot MATHS (5 lettres distinctes) sont au nombre de 5! = 120. Quand un mot contient des lettres répétées, échanger deux lettres identiques ne crée pas d'anagramme nouvelle : on compte alors en choisissant les places de chaque lettre répétée (voir l'exercice 11).

5. Combinaisons

Soit E un ensemble à n éléments et k un entier naturel avec 0 ≤ k ≤ n. Une combinaison de k éléments de E est une partie de E ayant k éléments. Il n'y a ni ordre ni répétition : {a, b} et {b, a} sont la même partie.

Le nombre de combinaisons de k éléments parmi n se note C(n, k) et se lit « k parmi n ». On l'appelle aussi coefficient binomial. (Dans les manuels, il s'écrit avec n placé au-dessus de k entre grandes parenthèses.)

Théorème. Pour 0 ≤ k ≤ n :

C(n, k) = n!/(k! × (n − k)!) = [n × (n − 1) × ... × (n − k + 1)]/k!.

Démonstration. Comptons les arrangements de k éléments de E de deux manières. D'une part, il y en a n!/(n − k)!. D'autre part, on obtient chaque arrangement en choisissant d'abord la partie formée de ses k éléments (C(n, k) choix), puis l'ordre dans lequel on les range (k! permutations de cette partie). Par le principe multiplicatif, le nombre d'arrangements vaut C(n, k) × k!. Donc C(n, k) × k! = n!/(n − k)!, d'où la formule.

En pratique, on calcule avec la seconde écriture, qui évite les grands nombres : C(10, 3) = (10 × 9 × 8)/(3 × 2 × 1) = 720/6 = 120.

Situation type : tirages simultanés de k objets parmi n (une main de cartes, une délégation, un groupe), ou choix de k positions parmi n.

Valeurs particulières. C(n, 0) = 1 (seule la partie vide a 0 élément), C(n, n) = 1 (seul E a n éléments), C(n, 1) = n, C(n, 2) = n(n − 1)/2.

Propriété de symétrie. Pour 0 ≤ k ≤ n : C(n, k) = C(n, n − k).

Justification par la formule : les deux nombres valent n!/(k!(n − k)!). Justification combinatoire : choisir les k éléments que l'on garde revient à choisir les n − k éléments que l'on laisse. Ainsi C(20, 18) = C(20, 2) = 190.

Relation de Pascal. Pour 1 ≤ k ≤ n − 1 :

C(n, k) = C(n − 1, k − 1) + C(n − 1, k).

Démonstration combinatoire. Fixons un élément particulier a de E. Les parties de E à k éléments se répartissent en deux catégories disjointes :

• celles qui contiennent a : il reste à choisir k − 1 éléments parmi les n − 1 autres, soit C(n − 1, k − 1) parties ;
• celles qui ne contiennent pas a : on choisit les k éléments parmi les n − 1 autres, soit C(n − 1, k) parties.

Le principe additif donne la relation.

Démonstration par le calcul. C(n − 1, k − 1) + C(n − 1, k) = (n − 1)!/((k − 1)!(n − k)!) + (n − 1)!/(k!(n − k − 1)!). On réduit au dénominateur commun k!(n − k)! : on obtient (n − 1)! × [k + (n − k)]/(k!(n − k)!) = n × (n − 1)!/(k!(n − k)!) = n!/(k!(n − k)!) = C(n, k).

Somme des coefficients d'une ligne. Pour tout entier naturel n :

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

Justification : le membre de gauche compte les parties de E en les classant selon leur nombre d'éléments (principe additif) ; le membre de droite est le nombre total de parties (paragraphe 3).

6. Triangle de Pascal

La relation de Pascal permet de calculer les coefficients binomiaux de proche en proche, sans factorielle. On les range dans un tableau : la ligne n contient C(n, 0), C(n, 1), ..., C(n, n). Chaque ligne commence et finit par 1, et chaque coefficient intérieur est la somme du coefficient situé juste au-dessus et de celui situé au-dessus à gauche.

Lectures utiles : chaque ligne est symétrique (propriété de symétrie), la somme de la ligne n vaut 2ⁿ (ligne 5 : 1 + 5 + 10 + 10 + 5 + 1 = 32 = 2⁵), et les coefficients croissent jusqu'au milieu de la ligne puis décroissent.

Exemple : C(7, 3) = C(6, 2) + C(6, 3) = 15 + 20 = 35.

7. Formule du binôme de Newton

Théorème. Pour tous nombres réels a et b et tout entier naturel n :

(a + b)ⁿ = C(n, 0)aⁿ + C(n, 1)aⁿ⁻¹b + C(n, 2)aⁿ⁻²b² + ... + C(n, n)bⁿ,

c'est-à-dire la somme, pour k allant de 0 à n, des termes C(n, k) aⁿ⁻ᵏ bᵏ.

Justification combinatoire. (a + b)ⁿ = (a + b)(a + b)...(a + b), avec n facteurs. En développant, on choisit dans chaque facteur soit a, soit b, et on fait le produit des n termes choisis. Un produit égal à aⁿ⁻ᵏbᵏ s'obtient chaque fois que l'on a choisi b dans exactement k facteurs : il y a autant de tels choix que de parties à k éléments parmi les n facteurs, soit C(n, k). Le coefficient de aⁿ⁻ᵏbᵏ est donc C(n, k).

On peut aussi démontrer la formule par récurrence sur n, en utilisant la relation de Pascal : c'est exactement la règle de construction du triangle.

Développements à connaître :

• (a + b)² = a² + 2ab + b² ;
• (a + b)³ = a³ + 3a²b + 3ab² + b³ ;
• (a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴ ;
• (1 + x)ⁿ = 1 + nx + C(n, 2)x² + ... + xⁿ.

Pour (a − b)ⁿ, on écrit a − b = a + (−b) : les signes alternent, (a − b)³ = a³ − 3a²b + 3ab² − b³.

Conséquences.

• Avec a = b = 1 : la somme des C(n, k) vaut (1 + 1)ⁿ = 2ⁿ (on retrouve le résultat du paragraphe 5).
• Avec a = 1 et b = −1, pour n ≥ 1 : C(n, 0) − C(n, 1) + C(n, 2) − ... + (−1)ⁿC(n, n) = 0ⁿ = 0. Un ensemble non vide a donc autant de parties de cardinal pair que de parties de cardinal impair.
• Pour x ≥ 0 : (1 + x)ⁿ ≥ 1 + nx, car tous les termes négligés sont positifs (inégalité de Bernoulli, déjà rencontrée par récurrence).

8. Choisir le bon modèle

Avant tout calcul, pose-toi deux questions : l'ordre compte-t-il ? Un même élément peut-il être choisi plusieurs fois ?

Lien avec les probabilités. En situation d'équiprobabilité sur un univers Ω fini, la probabilité d'un événement A est :

P(A) = card(A)/card(Ω).

Le dénombrement sert donc à calculer card(A) et card(Ω). Règle d'or : compter A et Ω avec le même modèle (tous deux ordonnés, ou tous deux non ordonnés). Dans un tirage simultané, on peut d'ailleurs raisonner en tirages successifs sans remise : chaque partie correspond à k! arrangements, et ce facteur se simplifie dans le quotient.

Compter avec des contraintes. Les énoncés combinent souvent les principes :

• « exactement 2 as et 3 autres cartes » : on choisit les as, puis les autres cartes, et on multiplie (principe multiplicatif) ;
• « 2 filles ou 3 filles » : on compte chaque cas séparément et on additionne (cas disjoints) ;
• « au moins un » : on passe par le complémentaire.

Exemple 1 : codes à quatre chiffres

Un digicode accepte les codes formés de 4 chiffres pris parmi 0, 1, ..., 9. a) Combien de codes différents existe-t-il ? b) Combien de codes ont leurs 4 chiffres distincts ? c) Combien de codes comportent au moins deux chiffres identiques ? d) On tape un code au hasard. Quelle est la probabilité qu'il ait ses chiffres distincts ?

Résolution. a) Un code est un 4-uplet de l'ensemble {0, ..., 9}, qui a 10 éléments ; l'ordre compte et les répétitions sont permises. Il y a donc 10⁴ = 10 000 codes. b) Un code à chiffres distincts est un arrangement de 4 éléments parmi 10 : 10 × 9 × 8 × 7 = 5 040 codes. c) « Au moins deux chiffres identiques » est le contraire de « chiffres tous distincts ». Par la méthode du complémentaire : 10 000 − 5 040 = 4 960 codes. d) Les 10 000 codes sont équiprobables : P = 5 040/10 000 = 0,504.

Exemple 2 : mains de cinq cartes

On tire simultanément 5 cartes d'un jeu de 32 cartes (4 couleurs, 8 hauteurs dont l'as ; le jeu contient 4 as). a) Combien de mains différentes peut-on obtenir ? b) Combien de mains contiennent exactement 2 as ? c) Combien de mains contiennent au moins un as ? d) En déduire la probabilité d'obtenir exactement 2 as (arrondie à 10⁻³).

Résolution. a) Le tirage est simultané : une main est une partie à 5 éléments de l'ensemble des 32 cartes. Le nombre de mains est C(32, 5) = (32 × 31 × 30 × 29 × 28)/(5 × 4 × 3 × 2 × 1) = 24 165 120/120 = 201 376. b) On choisit les 2 as parmi les 4 as : C(4, 2) = 6 façons. On choisit ensuite les 3 autres cartes parmi les 28 cartes qui ne sont pas des as : C(28, 3) = (28 × 27 × 26)/6 = 19 656/6 = 3 276 façons. Par le principe multiplicatif : 6 × 3 276 = 19 656 mains. c) Les mains sans as sont les parties à 5 éléments des 28 cartes qui ne sont pas des as : C(28, 5) = (28 × 27 × 26 × 25 × 24)/120 = 11 793 600/120 = 98 280. Par complémentaire : 201 376 − 98 280 = 103 096 mains. d) Les mains sont équiprobables : P = 19 656/201 376 ≈ 0,098.

Exemple 3 : formule du binôme

a) Développer (x − 2)⁴. b) Déterminer le coefficient de x³ dans le développement de (3x + 1)⁷. c) Montrer que pour tout entier n ≥ 1, C(n, 1) + 2C(n, 2) + 4C(n, 3) + ... + 2ⁿ⁻¹C(n, n) = (3ⁿ − 1)/2.

Résolution. a) On applique la formule avec a = x, b = −2, n = 4 et la ligne 4 du triangle (1, 4, 6, 4, 1) : (x − 2)⁴ = x⁴ + 4x³(−2) + 6x²(−2)² + 4x(−2)³ + (−2)⁴ = x⁴ − 8x³ + 24x² − 32x + 16. Contrôle en x = 1 : 1 − 8 + 24 − 32 + 16 = 1 et (1 − 2)⁴ = 1. Le résultat est cohérent. b) Le terme général est C(7, k)(3x)ᵏ × 1⁷⁻ᵏ = C(7, k) 3ᵏ xᵏ. Pour k = 3 : C(7, 3) × 3³ = 35 × 27 = 945. c) Par le binôme avec a = 1 et b = 2 : 3ⁿ = (1 + 2)ⁿ = somme des C(n, k)2ᵏ pour k de 0 à n = 1 + 2C(n, 1) + 4C(n, 2) + ... + 2ⁿC(n, n). On retire 1 et on divise par 2 : (3ⁿ − 1)/2 = C(n, 1) + 2C(n, 2) + ... + 2ⁿ⁻¹C(n, n), ce qu'il fallait démontrer. Vérification pour n = 2 : C(2, 1) + 2C(2, 2) = 2 + 2 = 4 et (9 − 1)/2 = 4.

• Commence toujours par décrire l'objet compté (« un résultat est un ... de ... ») : cela fixe le modèle et l'ensemble de départ.
• Pose les deux questions dans l'ordre : l'ordre compte-t-il ? la répétition est-elle possible ? Un tirage « simultané » ou la formation d'un « groupe » appelle les combinaisons ; des « rôles différents » ou des « places numérotées » appellent les arrangements.
• Ne confonds pas nᵏ (avec répétition) et n!/(n − k)! (sans répétition) : le premier est toujours supérieur ou égal au second.
• Pour « au moins un », passe par le complémentaire : c'est plus court et moins risqué que d'additionner tous les cas.
• Quand tu multiplies des choix, vérifie qu'ils sont indépendants dans leur nombre ; quand tu additionnes des cas, vérifie qu'ils sont disjoints, sinon tu comptes deux fois les mêmes objets.
• Piège classique : compter les mains « avec au moins un as » en choisissant d'abord un as (4 façons) puis 4 cartes quelconques parmi 31. Une main à 2 as est alors comptée deux fois : le résultat est faux.
• En probabilités, compte l'événement et l'univers avec le même modèle (tous deux ordonnés ou tous deux non ordonnés).
• Calcule C(n, k) avec la forme « k facteurs décroissants sur k! » et utilise la symétrie : C(50, 48) = C(50, 2) = 1 225, sans factorielle géante.
• Dans (a − b)ⁿ, n'oublie pas les signes alternés, et dans (3x + 1)ⁿ, la puissance porte aussi sur le coefficient 3.

En PASS et en LAS, le dénombrement est la base du calcul des probabilités en biostatistique : nombre de génotypes possibles, nombre de séquences de nucléotides ou de peptides (4ⁿ séquences d'ADN de longueur n, 20ⁿ peptides de n acides aminés), tirages de patients dans une population, nombre de façons de répartir des sujets entre groupes d'un essai. Les coefficients C(n, k) sont exactement ceux de la loi binomiale, qui décrit le nombre de succès dans une suite d'épreuves indépendantes (nombre d'enfants atteints dans une fratrie, nombre de répondeurs à un traitement). Les QCM exigent de reconnaître vite le bon modèle et de mener le calcul sans calculatrice, d'où l'intérêt des simplifications de factorielles et de la symétrie.

Niveau 1 : s'entraîner

1. Calculer sans calculatrice : a) 6! ; b) 8!/6! ; c) C(7, 2) ; d) C(10, 8) ; e) le nombre d'arrangements de 3 éléments parmi 5.

2. Un restaurant propose 4 entrées, 5 plats et 3 desserts.

a) Combien de menus « entrée, plat, dessert » peut-on composer ? b) Un menu léger est soit « entrée et plat », soit « plat et dessert ». Combien de menus légers existe-t-il ?

3. On forme des mots de 5 lettres (ayant un sens ou non) avec les 26 lettres de l'alphabet.

a) Combien de mots peut-on former ? b) Combien de mots ont leurs 5 lettres distinctes ?

4. Huit chevaux participent à une course, sans ex aequo.

a) Combien y a-t-il de tiercés dans l'ordre (les trois premiers avec leur rang) ? b) Combien y a-t-il de tiercés dans le désordre (l'ensemble des trois premiers) ? c) Combien y a-t-il de classements complets de l'arrivée ?

5. Soit E un ensemble à 6 éléments.

a) Combien E a-t-il de parties ? b) Combien de parties à 2 éléments ? c) Combien de parties ayant au moins 2 éléments ?

Niveau 2 : type bac

6. Une classe compte 18 filles et 12 garçons. On forme une délégation de 4 élèves.

a) Combien de délégations différentes peut-on former ? b) Combien de délégations comportent exactement 2 filles et 2 garçons ? c) Combien de délégations comportent au moins une fille ? d) On élit maintenant dans la classe un président, un secrétaire et un trésorier, trois élèves distincts. Combien de bureaux possibles ?

7. Un code d'accès est formé d'une lettre, A ou B, suivie de 4 chiffres (de 0 à 9).

a) Combien de codes existe-t-il ? b) Combien de codes ont leurs 4 chiffres distincts ? c) Combien de codes contiennent au moins un 0 ?

8. a) Écrire les lignes 0 à 6 du triangle de Pascal.

b) En déduire le développement de (1 + x)⁶. c) En déduire une valeur approchée de 1,01⁶ à 10⁻⁵ près, en justifiant que les derniers termes sont négligeables.

9. Soit n un entier naturel non nul.

a) Démontrer par le calcul que C(n, k) = C(n, n − k) pour 0 ≤ k ≤ n. b) Démontrer par le calcul la relation C(n + 1, 2) = C(n, 1) + C(n, 2), puis vérifier pour n = 5. c) À l'aide de la formule du binôme, démontrer que C(n, 0) + C(n, 1) + ... + C(n, n) = 2ⁿ.

10. On tire simultanément 4 cartes d'un jeu de 32 cartes (8 cœurs, 4 rois).

a) Combien de tirages sont possibles ? b) Combien de tirages contiennent exactement un cœur ? c) Combien de tirages contiennent une carte de chacune des 4 couleurs ? d) Combien de tirages contiennent au moins un roi ?

Niveau 3 : vers le PASS

11. Anagrammes.

a) Combien d'anagrammes a le mot LAPIN ? b) Combien d'anagrammes a le mot PASS ? (On pourra choisir d'abord les places des deux S.) c) Combien d'anagrammes a le mot BANANE ?

12. Sur un quadrillage, on se déplace du point O(0 ; 0) au point B(5 ; 3) par des pas d'une unité, uniquement vers la droite (D) ou vers le haut (H).

a) Combien de pas comporte un chemin ? Combien de chemins différents existe-t-il ? b) Combien de ces chemins passent par le point C(2 ; 1) ? c) Combien ne passent pas par C ?

13. Un fragment d'ADN est une suite de 10 nucléotides, chacun pris parmi A, C, G, T.

a) Combien de fragments différents existe-t-il ? b) Combien de fragments contiennent exactement 3 nucléotides G ? c) Un tripeptide est une suite ordonnée de 3 acides aminés pris parmi 20. Combien de tripeptides existe-t-il ? d) Vrai ou faux : environ un quart des fragments de la question a) contiennent exactement 3 G.

14. a) Dans une réunion, chacun serre la main de chacun des autres une seule fois. On compte 66 poignées de main. Combien de personnes sont présentes ?

b) Montrer qu'un polygone convexe à n côtés (n ≥ 4) possède n(n − 3)/2 diagonales, puis calculer ce nombre pour n = 10.

1. a) 6! = 1 × 2 × 3 × 4 × 5 × 6 = 720.

b) 8!/6! = (8 × 7 × 6!)/6! = 8 × 7 = 56. c) C(7, 2) = (7 × 6)/2 = 21. d) Par symétrie, C(10, 8) = C(10, 2) = (10 × 9)/2 = 45. e) 5 × 4 × 3 = 60 arrangements.

2. a) Un menu est un triplet (entrée ; plat ; dessert). Par le principe multiplicatif : 4 × 5 × 3 = 60 menus.

b) Les menus « entrée et plat » sont au nombre de 4 × 5 = 20, les menus « plat et dessert » de 5 × 3 = 15. Ces deux catégories sont disjointes (l'une contient une entrée, l'autre non). Par le principe additif : 20 + 15 = 35 menus légers.

3. a) Un mot est un 5-uplet de l'alphabet (26 lettres, répétitions permises) : 26⁵ = 11 881 376 mots.

b) Un mot à lettres distinctes est un arrangement de 5 lettres parmi 26 : 26 × 25 × 24 × 23 × 22. On calcule : 26 × 25 = 650 ; 650 × 24 = 15 600 ; 15 600 × 23 = 358 800 ; 358 800 × 22 = 7 893 600 mots.

4. a) L'ordre compte et un cheval n'occupe qu'un rang : arrangement de 3 parmi 8, soit 8 × 7 × 6 = 336.

b) Seul l'ensemble des trois premiers compte : C(8, 3) = 336/3! = 336/6 = 56. c) Un classement complet est une permutation des 8 chevaux : 8! = 40 320.

5. a) Un ensemble à 6 éléments a 2⁶ = 64 parties.

b) C(6, 2) = (6 × 5)/2 = 15 parties. c) On retire au total les parties à 0 élément (C(6, 0) = 1) et à 1 élément (C(6, 1) = 6) : 64 − 1 − 6 = 57 parties.

6. a) Une délégation est une partie de 4 élèves parmi 30 : C(30, 4) = (30 × 29 × 28 × 27)/24 = 657 720/24 = 27 405 délégations.

b) On choisit 2 filles parmi 18 : C(18, 2) = (18 × 17)/2 = 153, puis 2 garçons parmi 12 : C(12, 2) = 66. Principe multiplicatif : 153 × 66 = 10 098 délégations. c) Contraire : aucune fille, c'est-à-dire 4 garçons parmi 12 : C(12, 4) = (12 × 11 × 10 × 9)/24 = 11 880/24 = 495. Donc 27 405 − 495 = 26 910 délégations. d) Les postes sont distincts, donc l'ordre compte, sans répétition : 30 × 29 × 28 = 24 360 bureaux.

7. a) 2 choix pour la lettre, puis un 4-uplet de chiffres (10⁴ choix) : 2 × 10 000 = 20 000 codes.

b) 2 choix pour la lettre, puis un arrangement de 4 chiffres parmi 10 (10 × 9 × 8 × 7 = 5 040) : 2 × 5 040 = 10 080 codes. c) Pour une lettre fixée, les codes sans 0 utilisent seulement 9 chiffres : 9⁴ = 6 561. Les codes avec au moins un 0 sont 10 000 − 6 561 = 3 439 par lettre. Au total : 2 × 3 439 = 6 878 codes.

8. a) Lignes 0 à 6 : 1 ; 1 1 ; 1 2 1 ; 1 3 3 1 ; 1 4 6 4 1 ; 1 5 10 10 5 1 ; 1 6 15 20 15 6 1.

b) Avec la ligne 6 : (1 + x)⁶ = 1 + 6x + 15x² + 20x³ + 15x⁴ + 6x⁵ + x⁶. c) Avec x = 0,01 : 1 + 0,06 + 15 × 0,0001 + 20 × 0,000001 + 15 × 10⁻⁸ + 6 × 10⁻¹⁰ + 10⁻¹² = 1 + 0,06 + 0,0015 + 0,00002 + 0,00000015 + ... Les trois derniers termes ont une somme inférieure à 2 × 10⁻⁷, très inférieure à 10⁻⁵. Donc 1,01⁶ ≈ 1,06152 à 10⁻⁵ près.

9. a) C(n, n − k) = n!/((n − k)! × (n − (n − k))!) = n!/((n − k)! × k!) = C(n, k), car n − (n − k) = k. La symétrie est démontrée.

b) C(n, 1) + C(n, 2) = n + n(n − 1)/2 = (2n + n² − n)/2 = (n² + n)/2 = n(n + 1)/2. Or C(n + 1, 2) = (n + 1)n/2. Les deux expressions sont égales. Pour n = 5 : C(5, 1) + C(5, 2) = 5 + 10 = 15 et C(6, 2) = 15. Vérifié. c) La formule du binôme avec a = b = 1 donne (1 + 1)ⁿ = somme des C(n, k) × 1ⁿ⁻ᵏ × 1ᵏ, d'où C(n, 0) + C(n, 1) + ... + C(n, n) = 2ⁿ.

10. a) C(32, 4) = (32 × 31 × 30 × 29)/24 = 863 040/24 = 35 960 tirages.

b) Un cœur parmi 8 : 8 façons ; 3 cartes parmi les 24 non-cœurs : C(24, 3) = (24 × 23 × 22)/6 = 12 144/6 = 2 024. Total : 8 × 2 024 = 16 192 tirages. c) On choisit une carte dans chacune des 4 couleurs, chaque couleur comptant 8 cartes : 8 × 8 × 8 × 8 = 8⁴ = 4 096 tirages. (Chaque main n'est comptée qu'une fois : elle est entièrement décrite par son cœur, son carreau, son trèfle et son pique, sans ordre de tirage à prendre en compte.) d) Sans roi : 4 cartes parmi 28, C(28, 4) = (28 × 27 × 26 × 25)/24 = 491 400/24 = 20 475. Au moins un roi : 35 960 − 20 475 = 15 485 tirages.

11. a) Les 5 lettres de LAPIN sont distinctes : une anagramme est une permutation, soit 5! = 120 anagrammes.

b) Le mot PASS a 4 lettres dont deux S identiques. On choisit les 2 places des S parmi 4 : C(4, 2) = 6 ; on place ensuite P et A dans les 2 places restantes, dans un ordre : 2! = 2. Total : 6 × 2 = 12 anagrammes. (Contrôle : 4!/2! = 24/2 = 12.) c) BANANE : 6 lettres, dont A deux fois et N deux fois. Places des A : C(6, 2) = 15 ; places des N parmi les 4 restantes : C(4, 2) = 6 ; B et E dans les 2 dernières places : 2. Total : 15 × 6 × 2 = 180 anagrammes. (Contrôle : 6!/(2! × 2!) = 720/4 = 180.)

12. a) Il faut 5 pas D et 3 pas H, soit 8 pas. Un chemin est entièrement déterminé par le choix des 3 places des pas H parmi les 8 : C(8, 3) = (8 × 7 × 6)/6 = 56 chemins.

b) De O à C(2 ; 1) : 3 pas dont 1 H, soit C(3, 1) = 3 chemins. De C à B : 3 pas D et 2 pas H, soit 5 pas et C(5, 2) = 10 chemins. Principe multiplicatif : 3 × 10 = 30 chemins. c) Par complémentaire : 56 − 30 = 26 chemins.

13. a) Un fragment est un 10-uplet d'un ensemble à 4 éléments : 4¹⁰ = 1 048 576 fragments.

b) On choisit les 3 positions des G parmi 10 : C(10, 3) = 120. Les 7 autres positions reçoivent chacune A, C ou T : 3⁷ = 2 187. Total : 120 × 2 187 = 262 440 fragments. c) 20³ = 8 000 tripeptides. d) 262 440/1 048 576 ≈ 0,250. Vrai : environ un quart des fragments contiennent exactement 3 G.

14. a) Une poignée de main correspond à une paire de personnes : il y en a C(n, 2) = n(n − 1)/2. On résout n(n − 1)/2 = 66, soit n(n − 1) = 132 = 12 × 11. Comme n(n − 1) est strictement croissant pour n ≥ 1, la seule solution est n = 12 personnes.

b) Un segment joignant deux sommets est déterminé par une paire de sommets : C(n, 2) = n(n − 1)/2 segments. Parmi eux, n sont des côtés, les autres sont des diagonales. Nombre de diagonales : n(n − 1)/2 − n = (n² − n − 2n)/2 = n(n − 3)/2. Pour n = 10 : 10 × 7/2 = 35 diagonales.

Ce chapitre prépare la partie Dénombrement, lois discrètes et calcul probabiliste du cours Probabilités : données, lois et estimation (UE 9 · Probabilités et biostatistiques). Même notion, au niveau du PASS, avec ses exercices corrigés.

Pour retenir les formules et les définitions, dépose ce cours dans Ossik : il en sort des cartes de révision, qu’il te ressort au bon moment. Tester avec ce chapitre