Principes et applications de l'analyse combinatoire

Introduction à l'analyse combinatoire

L'analyse combinatoire est la branche des mathématiques qui étudie le comptage des configurations finies. Elle permet de répondre à des questions du type « Combien de façons existe‑t‑il pour organiser, sélectionner ou disposer des objets ? ». Ce cours reprend les notions essentielles à travers des exemples concrets tirés d’un questionnaire.

1. Arrangements (permutations partielles)

Définition

Un arrangement de k objets parmi n distincts, avec des positions distinctes, correspond à une permutation partielle. Le nombre d’arrangements se calcule avec la formule :

n × (n‑1) × … × (n‑k+1) = \frac{n!}{(n‑k)!}

Exemple 1 : Deux postes distincts parmi quatre salariés

On veut placer deux personnes sur deux postes différents (poste 1 et poste 2). Le premier poste peut être occupé par l’une des 4 personnes, le second par l’une des 3 restantes :

• Choix du premier poste : 4 possibilités
• Choix du second poste : 3 possibilités

Le nombre total d’arrangements est donc 4 × 3 = 12. Cette situation illustre la formule n × (n‑1) pour k = 2.

À retenir : n × (n‑1) = arrangements de 2 parmi n

2. Permutations sans remise

Définition

Lorsque l’on tire plusieurs objets successivement sans remise, chaque tirage modifie le nombre d’objets disponibles. Le nombre total de suites possibles correspond à une permutation complète de k objets parmi n :

n × (n‑1) × … × (n‑k+1)

Exemple 2 : Tirage de 3 boules parmi 5 sans remise

Le premier tirage offre 5 possibilités, le deuxième 4, le troisième 3 :

• 1ᵉʳ tirage : 5
• 2ᵉʳ tirage : 4
• 3ᵉʳ tirage : 3

Le total est 5 × 4 × 3 = 60 suites différentes.

À retenir : n × (n‑1) × (n‑2) pour un tirage de 3 sans remise

3. Combinaisons (sans ordre)

Définition

Une combinaison de k éléments parmi n ne tient pas compte de l’ordre. Le nombre de sous‑ensembles de taille k est donné par le coefficient binomial :

C(n, k) = \frac{n!}{k!(n‑k)!}

Exemple 3 : Sous‑ensembles de taille 3 parmi 8 éléments

Appliquons la formule :

• n = 8, k = 3
• C(8,3) = \frac{8!}{3!·5!} = \frac{8×7×6}{3×2×1} = 56

Il existe donc 56 sous‑ensembles différents.

4. Comptage avec répétition autorisée

4.1. Arrangements avec remise

Lorsque la remise est autorisée, chaque position peut être remplie par n’importe quel des n objets, indépendamment des précédents choix. Le nombre total d’arrangements de longueur k est alors n^k.

Exemple 4 : Deux‑uplets avec répétition à partir de {A,B,C}

Chaque position (1 et 2) peut recevoir l’une des 3 lettres, donc le nombre de p‑uplets distincts est 3^2 = 9.

4.2. Plaques d’immatriculation

Une plaque typique comporte 4 lettres suivies de 3 chiffres, chaque caractère pouvant se répéter. Le nombre total de plaques possibles est :

• 26 possibilités pour chaque lettre : 26⁴
• 10 possibilités pour chaque chiffre : 10³

Donc 26⁴ × 10³ = 456 976 000 plaques différentes.

5. Distribution de prix distincts

Définition

Attribuer k prix distincts à n personnes (avec k ≤ n) revient à choisir k personnes puis à ordonner les prix parmi elles. Le nombre d’arrangements est :

n × (n‑1) × … × (n‑k+1) (même formule que pour les arrangements).

Exemple 5 : Trois primes distinctes parmi 8 collaborateurs

On calcule :

• Premier prix : 8 possibilités
• Deuxième prix : 7 possibilités
• Troisième prix : 6 possibilités

Le total est 8 × 7 × 6 = 336 façons d’attribuer les trois primes.

6. Triangle de Pascal et coefficients binomiaux

Rappel du triangle

Le triangle de Pascal organise les coefficients binomiaux C(n, k) en lignes. La ligne n contient les valeurs de C(n, k) pour k = 0 … n.

Exemple 6 : Coefficient de (5, 2)

Dans la 5ᵉ ligne (en partant de 0), le troisième terme correspond à C(5,2) :

• C(5,2) = \frac{5!}{2!·3!} = \frac{5×4}{2×1} = 10

Le coefficient recherché est donc 10.

7. Tirages avec remise

Définition

Lorsque chaque tirage est effectué avec remise, le nombre d’objets disponibles reste constant. Pour k tirages parmi n objets, le nombre de suites possibles est n^k.

Exemple 7 : Deux tirages successifs avec remise parmi 5 boules

Chaque tirage offre 5 possibilités, donc le nombre total de suites est 5² = 25.

8. Synthèse des formules clés

• Arrangements (sans remise) : n × (n‑1) × … × (n‑k+1) = \frac{n!}{(n‑k)!}
• Combinaisons (sans ordre) : C(n, k) = \frac{n!}{k!(n‑k)!}
• Permutations avec remise (p‑uplets) : n^k
• Triangle de Pascal : chaque coefficient C(n, k) apparaît à la position k de la ligne n.

9. Applications pratiques

Les concepts étudiés sont largement utilisés dans la programmation (génération de combinaisons), la cryptographie (espaces de clés), la logistique (planification de tâches) et les jeux de hasard (calcul de probabilités). Maîtriser le comptage permet d’optimiser les solutions et d’évaluer correctement les risques.

10. Exercices d’entraînement

Pour consolider vos connaissances, essayez de résoudre les problèmes suivants :

• Combien d’arrangements de 4 personnes parmi 6 lorsqu’il y a 4 postes distincts ?
• Quel est le nombre de combinaisons de 5 éléments parmi 12 ?
• Combien de mots de 3 lettres (A‑Z) peuvent‑on former si les lettres peuvent se répéter ?
• Dans le triangle de Pascal, quel coefficient correspond à C(8,3) ?

Vérifiez vos réponses à l’aide des formules présentées dans ce cours.