Cours et Exercices de Dénombrement et Combinatoire avec Contrôle Corrigé

Cardinal d'ensemble et réunions

Compter des éléments, ça paraît simple, mais il y a des règles à respecter ! Le cardinal d'un ensemble E, noté Card(E), c'est tout simplement le nombre d'éléments qu'il contient.

Quand tu as plusieurs ensembles disjoints (qui n'ont aucun élément en commun), tu peux additionner leurs cardinaux sans problème. C'est comme compter les élèves de différentes classes : Card(E₁ ∪ E₂ ∪ ... ∪ Eₙ) = Card(E₁) + Card(E₂) + ... + Card(Eₙ).

Le produit cartésien E × F, c'est l'ensemble de tous les couples possibles entre les éléments de E et ceux de F. Par exemple, si E = {u, v} et F = {45, 8}, alors E × F = {(u,45), (u,8), (v,45), (v,8)}. La formule est ultra-pratique : Card(E × F) = Card(E) × Card(F).

💡 Astuce : Pour visualiser le produit cartésien, imagine un tableau où E représente les lignes et F les colonnes !

Produits cartésiens et k-uplets

Les k-uplets, c'est quand tu prends k éléments dans un ensemble E en tenant compte de l'ordre ET en autorisant les répétitions. Un k-uplet, c'est comme un mot de k lettres où chaque lettre vient de l'ensemble E.

La formule est redoutablement efficace : Card(Eᵏ) = [Card(E)]ᵏ. Si ton ensemble E a 10 éléments et que tu veux former des mots de 4 lettres, tu auras 10⁴ = 10 000 possibilités !

L'exemple du digicode illustre parfaitement cette notion. Pour un code de 4 chiffres (0 à 9) suivi d'une lettre (A, B ou C), tu as 10⁴ × 3 = 30 000 codes possibles. Pour 5 chiffres : 10⁵ × 3 = 300 000. Pour 6 chiffres : 10⁶ × 3 = 3 000 000.

💡 Remarque : Au total, ce système offre 3 330 000 codes différents. Plutôt sécurisé !

Arrangements et permutations

Les arrangements, c'est quand l'ordre compte et qu'on ne peut pas répéter ! Un k-arrangement de l'ensemble E, c'est choisir k éléments différents de E en tenant compte de leur ordre.

D'abord, maîtrise la factorielle : n! = 1 × 2 × 3 × ... × n. Par convention, 0! = 1. C'est l'outil de base pour tous les calculs qui suivent.

La formule des arrangements est Aₙᵏ = n!/$n-k$! = n × $n-1$ × ... × $n-k+1$. Pour construire un k-arrangement, tu as n choix pour le premier élément, n-1 pour le second, et ainsi de suite.

Une permutation, c'est un arrangement complet : tous les éléments de l'ensemble dans un certain ordre. Pour un ensemble à n éléments, il y a n! permutations possibles. Par exemple, 5 élèves peuvent passer à l'oral dans 5! = 120 ordres différents.

💡 Exemple concret : Si tu n'interroges que 3 élèves sur 5, tu as A₅³ = 5!/$5-3$! = 60 possibilités.

Parties d'un ensemble et combinaisons

Une partie d'un ensemble E, c'est un sous-ensemble de E (certains éléments de E, éventuellement tous ou aucun). Un ensemble à n éléments possède exactement 2ⁿ parties - chaque élément peut être inclus ou exclu, d'où les 2 choix par élément.

Les combinaisons, c'est quand l'ordre ne compte pas ! Une combinaison de k éléments parmi n, notée C(n,k) ou (n k), c'est choisir k éléments sans se soucier de leur ordre.

La formule fondamentale est C(n,k) = n!/$k!(n-k)!$. Tu as aussi des propriétés super utiles : C(n,k) = C$n,n-k$ (symétrie) et C(n,k) = C$n-1,k-1$ + C$n-1,k$ (relation de Pascal).

Quelques valeurs à retenir : C(n,0) = C(n,n) = 1, C(n,1) = n, et C(n,2) = n$n-1$/2.

💡 Triangle de Pascal : Chaque nombre est la somme des deux nombres situés au-dessus de lui !

Triangle de Pascal et propriétés des combinaisons

Le triangle de Pascal te permet de calculer rapidement les premières valeurs de combinaisons. Chaque ligne correspond à une valeur de n, et tu obtiens les valeurs suivantes en additionnant les nombres de la ligne précédente.

La propriété la plus spectaculaire est ∑$k=0 to n$ C(n,k) = 2ⁿ. Cela signifie que si tu additionnes tous les nombres d'une ligne du triangle de Pascal, tu obtiens une puissance de 2 !

Cette formule s'explique facilement : le membre de gauche compte toutes les parties possibles d'un ensemble à n éléments (classées par taille), tandis que 2ⁿ les compte directement.

Dans l'exemple des grilles avec 10 chiffres et 4 lettres, où il faut choisir 3 chiffres et 2 lettres, tu calcules C(10,3) × C(4,2) = 120 × 6 = 720 grilles différentes.

💡 Astuce : Pour vérifier tes calculs, utilise la symétrie C(n,k) = C$n,n-k$ !

Exercices d'application - Cardinaux et produits

Les exercices concrets te montrent comment appliquer les formules ! Pour l'exercice 8, avec 114 inscrits au total répartis dans différentes activités, tu utilises les propriétés des réunions d'ensembles.

L'exercice 7 illustre le principe d'inclusion-exclusion : Card(C ∪ M) = Card(C) + Card(M) - Card(C ∩ M) = 75 + 112 - 50 = 137. Quand deux ensembles se chevauchent, il faut soustraire l'intersection pour éviter de compter deux fois les mêmes éléments.

Pour l'exercice 10, avec E = {0,1,2,3,4,5,6} et F = {0,1,2,...,12}, le produit cartésien E × F a pour cardinal 7 × 13 = 91. C'est le nombre total de couples possibles.

L'exercice 11 avec trois dés (Rouge, Vert, Bleu) donne 6³ = 216 résultats possibles, car chaque dé peut afficher 6 valeurs indépendamment des autres.

💡 Méthode : Pour les produits cartésiens, multiplie simplement les cardinaux !

Codes et arrangements - Applications pratiques

L'exemple des codes de sécurité montre la puissance des k-uplets ! Pour des codes composés de chiffres (0 à 9) suivis d'une lettre (A, B, C) :

• Codes à 4 chiffres : 10⁴ × 3 = 30 000 possibilités
• Codes à 5 chiffres : 10⁵ × 3 = 300 000 possibilités
• Codes à 6 chiffres : 10⁶ × 3 = 3 000 000 possibilités

Au total, le système offre 3 330 000 codes différents, ce qui représente une sécurité robuste.

L'exercice 17 présente un problème de trajets avec 7 étapes et 3 choix à chaque étape, donnant 3⁷ = 2 187 trajets différents. C'est un exemple parfait de k-uplet où k = 7 et l'ensemble de base a 3 éléments.

💡 Conseil : Dans les problèmes de codes, identifie d'abord si les répétitions sont autorisées et si l'ordre compte !

Factorielles et arrangements - Calculs détaillés

Maîtriser les factorielles est essentiel ! Les premières valeurs à connaître : 0! = 1, 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120. Ces valeurs reviennent constamment dans les exercices.

Pour simplifier les fractions de factorielles, utilise la définition : 6!/3! = (3! × 4 × 5 × 6)/3! = 4 × 5 × 6 = 120. De même, 9!/11! = 9!/(9! × 10 × 11) = 1/110.

Les arrangements Aₙᵏ = n!/$n-k$! représentent le nombre de façons de choisir et ordonner k éléments parmi n. L'exercice 20 demande le nombre de façons de choisir 3 personnes parmi 7 pour un podium : A₇³ = 7 × 6 × 5 = 210.

L'exercice 21 combine arrangements et produit cartésien : 3 chiffres différents parmi 5, puis une lettre parmi 3, soit A₅³ × 3 = 60 × 3 = 180 codes.

💡 Astuce : Pour les arrangements, pense "combien de choix à chaque étape ?" puis multiplie !

Arrangements complexes et permutations

L'exercice sur les codes à 4 caractères illustre parfaitement les arrangements dans un ensemble mixte. Avec 8 éléments au total (5 chiffres + 3 lettres), le nombre de codes de 4 caractères différents est A₈⁴ = 8!/$8-4$! = 8!/4! = 1 680.

Pour une approche plus complexe, si tu veux exactement 3 chiffres différents ET 1 lettre, tu calcules séparément : A₅³ arrangements de chiffres × 3 choix de lettres = 60 × 3 = 180 possibilités.

L'exercice 24 demande le nombre de 6-arrangements dans un ensemble à 12 éléments : A₁₂⁶ = 12!/$12-6$! = 12!/6! = 665 280. C'est énorme, mais logique quand on réfléchit aux 12 × 11 × 10 × 9 × 8 × 7 choix successifs.

L'exercice 25 confirme qu'un ensemble à 4 éléments {a,b,c,d} a exactement 4! = 24 permutations, toutes listées dans le cours.

💡 Stratégie : Face à un problème complexe, décompose-le en étapes simples !

Applications avancées et synthèse

L'exercice 31 montre l'explosion des possibilités avec les permutations : 10 personnes peuvent s'organiser en 10! = 3 628 800 ordres différents ! Cette croissance factorielle explique pourquoi certains problèmes de combinatoire deviennent rapidement impossibles à résoudre par énumération.

Les exercices de cette page synthétisent toutes les notions : arrangements, permutations, et combinaisons. Tu dois maintenant savoir distinguer quand utiliser chaque formule selon que l'ordre compte ou non, et selon que les répétitions sont autorisées.

La méthode générale pour réussir : identifie d'abord le type de problème (arrangement, permutation, combinaison, ou k-uplet), puis applique la formule correspondante. N'hésite pas à décomposer les problèmes complexes en sous-problèmes plus simples.

💡 Conseil final : Entraîne-toi à reconnaître les mots-clés : "ordre important" = arrangements, "ordre sans importance" = combinaisons, "avec répétition" = k-uplets !