Le denombrement

« Chapitre 3 – Combinatoire et dénombrement 1.

Cardinal d’ensembles a- Ensemble fini et cardinal Définition Soit 𝑛 un entier naturel. Lorsqu’un ensemble E possède 𝑛 éléments, on dit que E est un ensemble fini. Le nombre 𝑛 d’éléments de E est appelé cardinal de E, noté Card(E). Exemple : E = {𝑎 ; 𝑒 ; 𝑖 ; 𝑜 ; 𝑢 ; 𝑦} est un ensemble à six éléments. Card(E) = 6. b- Principe additif Définition Deux ensemble A et B sont disjoints lorsque leur intersection est vide : 𝐴 ∩ 𝐵 = ∅ Propriété Si E et F sont deux ensembles finis disjoints, on a : Card(E ∪ F) = Card(𝐸) + Card(𝐹) Exemple E = {𝑏 ; 𝑟} et F = {1 ; 2 ; 3} Remarque Si E et F ne sont pas disjoints on a la relation Card(E ∪ F) = Card(𝐸) + Card(𝐹) − card(𝐸 ∩ 𝐹) c- Principe multiplicatif Définition et propriété E et F sont deux ensembles non vides. Le produit cartésien de E par F, noté E × F, est l’ensemble des couples (𝑥 ; 𝑦) avec 𝑥 ∈ E et 𝑦 ∈ F. Lorsque les ensembles E et F sont finis, Card(E × F) = Card(E) × Card(F). Exemple 1: E = {𝑏 ; 𝑟} et F = {1 ; 2 ; 3} Ecrire l’ensembles des éléments du produit cartésien 𝐸 × 𝐹 Exemple 2 : Le digicode d’un hôtel est composé de trois entier pris dans 𝐴 = {1; 2; 3; 4} suivis d’une lettre prise dans 𝐵 = {𝑉; 𝑊; 𝑋; 𝑌; 𝑍} puis d’un symbole issu de 𝐶 = {#; $;∗} Donner deux codes possibles. Combien de codes peut-on former suivant ce procédé ? Exemple 3 : Un coffre-fort est protégé par un code constitué de quatre ou cinq chiffres allant de 0 à 9 puis d’une lettre parmi A, B et C.

Combien de codes peut-on former avec ce système ? 2.

𝒌-uplets d’un ensemble fini Nombre de 𝑘-uplets d’un ensemble à 𝑛 éléments Définition Soit 𝑘 un entier naturel non nul et E un ensemble non vide. Un 𝒌-uplet de E est un élément du produit cartésien E 𝑘 = ⏟ 𝐸 × 𝐸 × 𝐸 × … × 𝐸). 𝑘 𝑓𝑜𝑖𝑠 Un 𝒌-uplet de E est donc une liste ordonnée de 𝑘 éléments de E On peut interpréter un k-uplet de E comme un tirage successif avec remise de k éléments de E. L’ordre est à prendre en compte. Exemple : Ecrire la liste des triplets (3-uplets) de l’ensemble E = {𝑎 ; 𝑏}. Théorème Soient 𝑛 et 𝑘 deux entiers naturels non nuls et E un ensemble fini de cardinal n. Le nombre de 𝑘-uplets de E est 𝑛𝑘 , soit Card(E𝑘 ) = 𝑛𝑘 . Exemple 1 : Le code d’une carte bancaire est un 4-uplet de l’ensemble E = {0; 1; 2; 3; 4; 5; 6; 7; 8; 9} Combien de codes différents existe-t-il ? Exemple 2 : On dispose de trois boîtes numérotées A, B et C, et de cinq jetons numérotés de 1 à 5 que l’on doit ranger dans les boîtes.

On note T = {A ; B ; C} l’ensemble des boîtes. Les différents rangements possibles sont des 5-uplets de T. Par exemple, (A ; A ; C ; B ; B) signifie que l’on a rangé le premier jeton dans la boîte A, le deuxième dans la boîte A, le troisième dans la boîte C, le quatrième dans la boîte B et le 5ème dans la boite B..... »