Fiche de révision : Combinatoire et dénombrement

📋 Plan du Cours

1. Fondements du dénombrement
2. Principes additif et multiplicatif
3. Listes et k-uplets
4. Factorielle et permutations
5. Parties et combinaisons
6. Propriétés binomiales
7. Mots, chemins et Bernoulli
8. Sommes et méthodes de choix
9. Algorithmique et erreurs fréquentes

📖 1. Fondements du dénombrement

🔑 Notions clés & Définitions

• Cardinal d’un ensemble fini : E est le nombre de ses éléments et se note Card(E) ou |E|.

📝 Points essentiels

★ À maîtriser

⚡ Avant de choisir une formule, il faut déterminer si l’ordre compte, si les répétitions sont autorisées et si l’on choisit tous les éléments ou seulement une partie.

Compléments

• L’ensemble des mots de passe de 4 chiffres avec répétitions autorisées possède 10^4 = 10 000 éléments.

💡 Astuce mémo

Identifier avant de calculer

📖 2. Principes additif et multiplicatif

📝 Points essentiels

★ À maîtriser

🧮 Formule — Si une expérience comporte p étapes offrant respectivement n1, n2, ..., np choix, le nombre total de possibilités est n1 × n2 × ... × np.

📌 Pour des ensembles finis deux à deux disjoints, le cardinal de leur réunion est la somme de leurs cardinaux : Card(A1 ∪ ... ∪ Ap) = Card(A1) + ... + Card(Ap).

Compléments

🧮 Formule — Pour deux ensembles finis A et B, Card(A × B) = Card(A) × Card(B), et plus généralement Card(A1 × ... × Ap) = Card(A1) × ... × Card(Ap).

• Le choix d’une activité parmi 5 sports, 3 clubs artistiques ou 4 clubs scientifiques donne 5 + 3 + 4 = 12 possibilités lorsque les catégories sont disjointes.

• Un menu composé d’une entrée parmi 3, d’un plat parmi 5 et d’un dessert parmi 4 offre 3 × 5 × 4 = 60 possibilités.

💡 Astuce mémo

Cas séparés : addition ; étapes : multiplication

📖 3. Listes et k-uplets

🔑 Notions clés & Définitions

• k-uplet : D’un ensemble E est une liste ordonnée de k éléments de E, les répétitions étant autorisées sauf indication contraire.
• k-uplet d’éléments distincts : Une liste ordonnée de k éléments d’un ensemble dans laquelle aucun élément n’est répété.

📝 Points essentiels

★ À maîtriser

🧮 Formule — Si E contient n éléments, le nombre de k-uplets avec répétition possible est n^k.

🧮 Formule — Le nombre de k-uplets distincts formés dans un ensemble à n éléments est n(n − 1)(n − 2) ... (n − k + 1) = n!/(n − k)! pour 0 ≤ k ≤ n.

Compléments

• Le nombre de codes PIN de 4 chiffres avec répétitions autorisées est 10^4 = 10 000.

• Avec 8 finalistes, le nombre de podiums ordonnés de 3 personnes est 8 × 7 × 6 = 336.

💡 Astuce mémo

Ordre oui, répétition selon le cas

📖 4. Factorielle et permutations

🔑 Notions clés & Définitions

• Factorielle : Pour tout entier n ≥ 1, n! = n × (n − 1) × ... × 2 × 1, et par convention 0! = 1.
• Permutation : D’un ensemble fini à n éléments est une manière d’ordonner tous ses éléments.

📝 Points essentiels

★ À maîtriser

🧮 Formule — Le nombre de permutations d’un ensemble à n éléments est n!.

Compléments

• Le nombre de rangements de 6 livres différents sur une étagère est 6! = 720.

💡 Astuce mémo

Tout ordonner donne n!

📖 5. Parties et combinaisons

🔑 Notions clés & Définitions

• Partie d’un ensemble : E est un sous-ensemble de E.
• Combinaison : De k éléments parmi n est une partie de n éléments contenant exactement k éléments, choisie sans ordre et sans répétition.

📝 Points essentiels

★ À maîtriser

🧮 Formule — Un ensemble à n éléments possède 2^n parties, car chacun de ses éléments peut être pris ou non pris.

🧮 Formule — Le nombre de combinaisons de k éléments parmi n, noté binomiale(n,k), est binomiale(n,k) = n!/[k!(n − k)!].

Compléments

🔄 Processus — La formule des combinaisons provient du fait qu’une liste ordonnée de k éléments distincts peut être obtenue en choisissant une combinaison puis en ordonnant ses k éléments, soit binomiale(n,k) × k!.

• Le nombre de comités de 3 élèves parmi 12 est binomiale(12,3) = 220.

💡 Astuce mémo

Choisir sans ordonner

📖 6. Propriétés binomiales

📝 Points essentiels

★ À maîtriser

🧮 Formule — Pour tout entier n ≥ 0, binomiale(n,0) = 1, binomiale(n,n) = 1, binomiale(n,1) = n et binomiale(n,2) = n(n − 1)/2.

🧮 Formule — La symétrie des coefficients binomiaux est binomiale(n,k) = binomiale(n,n − k) pour 0 ≤ k ≤ n.

🧮 Formule — La relation de Pascal est binomiale(n+1,k+1) = binomiale(n,k) + binomiale(n,k+1), ou encore binomiale(n,k) = binomiale(n−1,k−1) + binomiale(n−1,k).

Compléments

🔄 Processus — La relation de Pascal se justifie en séparant les parties de taille k+1 selon qu’elles contiennent ou non un élément fixé.

• Dans le triangle de Pascal, chaque nombre intérieur est la somme des deux nombres situés juste au-dessus de lui.

💡 Astuce mémo

Bords, symétrie, Pascal

📖 7. Mots, chemins et Bernoulli

🔑 Notions clés & Définitions

• Épreuve de Bernoulli : Une épreuve qui possède deux issues, appelées succès et échec.

📝 Points essentiels

★ À maîtriser

🧮 Formule — Le nombre de mots de longueur n formés avec les symboles 0 et 1 est 2^n.

🧮 Formule — Le nombre de mots binaires de longueur n contenant exactement k symboles 1 est binomiale(n,k), car il suffit de choisir les k positions des 1.

🧮 Formule — Le nombre de chemins allant de (0,0) à (a,b) avec seulement des pas vers la droite et vers le haut est binomiale(a+b,b), car un chemin comporte a+b pas et se détermine par les positions des b pas vers le haut.

🧮 Formule — Dans une succession de n épreuves de Bernoulli, le nombre de suites contenant exactement k succès est binomiale(n,k).

Compléments

• Le nombre de chemins de (0,0) à (5,3) est binomiale(8,3) = 56.

💡 Astuce mémo

Les positions portent les choix

📖 8. Sommes et méthodes de choix

📝 Points essentiels

★ À maîtriser

🧮 Formule — La somme des coefficients binomiaux d’une ligne du triangle de Pascal vérifie ∑ de k=0 à n binomiale(n,k) = 2^n.

📌 Pour compter des objets satisfaisant au moins une condition, il peut être plus simple de compter le total puis de soustraire les objets qui ne satisfont pas cette condition.

🔄 Processus — Pour résoudre un problème de dénombrement, il faut décrire l’objet compté, déterminer si l’ordre compte, vérifier les répétitions, préciser si tous les éléments ou seulement une partie sont choisis, puis appliquer la formule adaptée.

Compléments

• Le nombre de comités de 4 personnes contenant au moins un homme parmi 9 femmes et 7 hommes est binomiale(16,4) − binomiale(9,4) = 1694.

💡 Astuce mémo

Complément et bonne formule

📖 9. Algorithmique et erreurs fréquentes

📝 Points essentiels

★ À maîtriser

📌 Un code autorisant les répétitions se compte généralement par une puissance, tandis qu’un code imposant des caractères distincts se compte par un produit décroissant.

⚡ Pour un podium de 3 personnes parmi 10, l’ordre compte et le nombre de possibilités est 10 × 9 × 8 = 720, alors qu’un groupe de 3 personnes se compte par binomiale(10,3) = 120.

Compléments

📌 Diviser par k! permet de corriger le comptage multiple d’un groupe lorsque les k éléments ont été ordonnés alors que l’ordre ne compte pas.

🔄 Processus — L’algorithme ligne_pascal(n) construit une ligne du triangle de Pascal en commençant et en terminant chaque nouvelle ligne par 1 et en additionnant deux termes voisins de la ligne précédente.

📊 Tableaux de synthèse

Choisir la formule adaptée

⚠️ Pièges & confusions fréquents

1. Le cardinal mesure le nombre d’éléments, et non le nombre de sous-ensembles.
2. Le principe additif simple ne s’applique pas directement à des ensembles qui se recouvrent.
3. Un k-uplet est ordonné, contrairement à une combinaison.
4. La convention 0! = 1 est nécessaire dans plusieurs formules de dénombrement.
5. Une partie peut contenir n’importe quel nombre d’éléments, de 0 à n.
6. La symétrie échange le nombre d’éléments choisis et le nombre d’éléments exclus.
7. 2^n compte tous les mots, tandis que binomiale(n,k) impose exactement k symboles 1.