Permutations et combinaisons

Principe fondamental du comptage

Principe de multiplication : si un événement peut se produire de m façons, puis qu'un second événement peut se produire de n façons, alors les deux peuvent se produire l'un après l'autre de m × n façons. Cela s'étend à trois événements ou plus.

Exemple : un cadenas a 3 molettes, chacune avec les chiffres 0 à 9. Codes = 10 × 10 × 10 = 1000.

Principe d'addition : si une tâche peut se faire de m façons ou de n autres façons (pas les deux), elle peut se faire de m + n façons. « Et » veut dire multiplier, « ou » veut dire additionner.

La factorielle

n! (on lit « n factorielle ») = 1 × 2 × 3 × … × n pour un entier naturel n non nul. Donc 3! = 6, 4! = 24, 5! = 120, 6! = 720.

• On définit 0! = 1. Cela garde justes des formules comme ⁿPₙ = n!/0!.
• n! = n × (n − 1)!, donc 7!/5! = 7 × 6 = 42. Simplifie au lieu de tout multiplier.

Permutations : la formule nPr

Une permutation est un rangement dans un ordre précis. Pour ranger r objets pris parmi n objets différents (sans répétition) : la première place a n choix, la deuxième n − 1, …, la r-ième a n − r + 1 choix. Donc

ⁿPᵣ = n(n − 1)(n − 2)…(n − r + 1) = n!/(n − r)!, 0 ≤ r ≤ n.

• ⁿPₙ = n! (on range tout). ⁿP₀ = 1.
• Si la répétition est permise, le nombre de rangements est nʳ.
• Si, parmi n objets, p sont identiques d'une sorte, q identiques d'une autre sorte, etc., les rangements de tous les n objets sont au nombre de n!/(p! q! …). Exemple : MISSISSIPPI a 11 lettres avec I×4, S×4, P×2, donc 11!/(4!·4!·2!) = 34650.

Combinaisons : la formule nCr et son lien avec nPr

Une combinaison est un choix où l'ordre ne compte pas. Chaque choix de r objets peut être rangé de r! façons, et en faisant cela pour chaque choix on obtient tous les ⁿPᵣ rangements. Donc

ⁿPᵣ = ⁿCᵣ × r!, ce qui donne ⁿCᵣ = n!/(r!(n − r)!).

• ⁿC₀ = ⁿCₙ = 1.
• ⁿCᵣ = ⁿCₙ₋ᵣ : choisir r objets à prendre = choisir n − r objets à laisser (étape 5 de la 3D). Donc si ⁿCₐ = ⁿC_b, alors a = b ou a + b = n.
• ⁿCᵣ + ⁿCᵣ₋₁ = ⁿ⁺¹Cᵣ (relation de Pascal, utilisée de nouveau dans le théorème du binôme).

Usages simples : lequel choisir ?

Demande-toi : l'ordre change-t-il le résultat ? Places à table, classements, nombres ou mots à former, mots de passe → permutation. Équipes, comités, poignées de main, choix de questions, groupes de fruits → combinaison.

• Poignées de main entre 10 personnes : ¹⁰C₂ = 45.
• Diagonales d'un polygone à n côtés : ⁿC₂ − n.
• Mots formés avec les lettres d'un mot sous conditions (voyelles ensemble : traite-les comme un seul bloc, puis multiplie par leurs propres arrangements).
• Questions « au moins » / « au plus » : additionne les cas séparés.

Ce qui tombe à l'examen

À prévoir : trouver n dans une équation comme ⁿP₄ = 12 · ⁿP₂ (2 à 3 points), ranger des lettres avec répétition ou avec conditions (3 à 4 points), des comités avec « au moins » (3 à 4 points), et des questions du type ⁿCᵣ = ⁿCₙ₋ᵣ (1 à 2 points). Écris la raison du comptage avec des mots avant les nombres.

Formules et définitions clés

• Principe du comptage : m façons puis n façons → m × n façons
• n! = 1 × 2 × … × n, 0! = 1, n! = n(n − 1)!
• ⁿPᵣ = n!/(n − r)!; avec répétition nʳ
• Objets identiques : n!/(p! q! r! …)
• ⁿCᵣ = n!/(r!(n − r)!), ⁿPᵣ = ⁿCᵣ · r!
• ⁿCᵣ = ⁿCₙ₋ᵣ; ⁿCᵣ + ⁿCᵣ₋₁ = ⁿ⁺¹Cᵣ

Exemples résolus

Erreurs fréquentes

• Utiliser nPr pour des équipes ou des comités. Si échanger deux personnes choisies donne le même groupe, utilise nCr.
• Additionner quand il faut multiplier. « Ceci et puis cela » se multiplie ; « ceci ou cela » s'additionne.
• Oublier de diviser par les factorielles des lettres répétées dans des mots comme POMME ou BANANA.
• Croire que 0! = 0. Par définition 0! = 1.