Combinatoire et dénombrement terminal

« Combinatoire et dénombrement I – Principes additif et multiplicatif – Dénombrement des k-uplets : 1.

Principe additif : a.

Définition : Un ensemble fini est un ensemble qui possède un nombre fini d’éléments. b.

Principe additif : Si A et B sont deux parties disjointes ( A∩ B=∅ ¿ d’un ensemble fini E, constituées respectivement de m et n éléments alors le nombre d’éléments de la réunion A∪ B est la somme m+ n. Notation et cas général : Card ¿ ) (lire « cardinal de A ») désigne le nombre d’éléments d’une partie A d’un ensemble fini E. Pour toutes parties A et B de E : Card ¿ )¿………. Ainsi,Card ¿ )¿ … ….

. Exemple :  Card ¿ )¿……. A={ 1 ;2 } B={ 3 ; 4 } A∪ B= {… … … .

}  Card ¿ )¿ … …… C= {1 ; 2 } D={ 1 ; 4 } C ∪ D={ … …..

} 2.

Principe multiplicatif: a.

Définition : Le produit cartésien de deux ensembles finis E et F, noté E× F (se lit « E croix F »), est l’ensemble des couples ( x ; y ) où x est un élément de E et y un élément de F. Exemple : E= { a ; b } et F = {1 ; 2 ;3 } E× F¿ { … …… … … … …… … … …… … … …… … … } De même, F× E¿ { … …… … … … …… … … …… … … …… … … ..

} b.

Principe multiplicatif : Si E et F sont deux ensembles finis constitués respectivement de m et n éléments, alors E×F est un ensemble fini dont le nombre d’éléments est le produit mn. Démonstration : un tableau à n lignes et m colonnes a n × m cases. Exemple : Un restaurant propose quatre entrées, deux plats et trois desserts. Trois menus sont proposés: entrée-plat-dessert ou entrée-plat ou plat-dessert. Combien de menus différents peut-on composer ? 3.

Ensemble E k et k -uplets de E (ou k -listes) : a.

Définition : Soit E un ensemble fini tel que Card ¿ )¿ n . Pour tout nombre entier naturel non nul k : ( k fois) E k = E × E ×… … × E k Un élément de E est appelé un k -uplet d’éléments de E (ou une k-liste) Lycée Notre Dame de Mongré 1 C’est une énumération ordonnée de k éléments de E, distincts ou confondus. b.

Exemple : E= { a ; b ;c }.

Cet arbre permet de lister les triplets de E 3.  (a ; b ; a ¿ ∈ E 3.  (a ; b ; c ¿ et (c ; a ; b ¿ sont des triplets différents de E 3. c.

Propriété : k est un nombre entier naturel, k ≥ 1 et E est un ensemble fini à n éléments (n ∈ N ). Le nombre de k -uplets de E est n k , c’est-à-dire Card ¿ )¿ n k . Démonstration : On démontre par récurrence que pour tout entier naturel k non nul, la propriété P( k ) : « Card ¿ )¿ n k » est vraie. Initialisation : pour k =1, E 1=E .

Son nombre d’éléments est n , c’est-à-dire n 1.

La propriété P(1) est donc vraie. Hérédité : On suppose que pour un entier naturel i ≥ 1 , la propriété P(i ) est vraie, c’est-à-dire que Card ¿ )¿ n i. Or, E i +1 est le produit cartésien E i × E , donc Card ¿ )¿ n i × n=ni +1. Donc P(i+1) est vraie. Conclusion : la propriété est vraie pour k =1 et est héréditaire.

Donc, d’après le principe de récurrence, P( k ) est vraie pour tout entier naturel k non nul, c’est à dire Card ¿ )¿ n k pour tout entier naturel k non nul. d.

Applications: E={π ; 3 ; 5} .

Lister les éléments de E 2 . I. E={0 ; 1 }.

Ecrire quatre 3-uplets de E.

Combien en existe-t-il ? II. III.

Code de carte bleue : 4 uplets de E= {0 ;1 ; 2 … .9 } Combien de code s existe nt ? II – Dénombrement des k -uplets d’éléments distincts .

Permutations: n désigne un nombre entier naturel avec n ≥ 1. 1.

Nombre de k -uplets d’éléments distincts d’un ensemble E : a.

Propriété : k désigne un nombre entier naturel tel que 1 ≤ k ≤ n. Le nombre de k -uplets d’éléments distincts d’un ensemble E à n éléments est : n × ( n−1 ) × … .× ( n−k +1 ) . Lycée Notre Dame de Mongré 2 b.

Vocabulaire : Un k -uplet d’éléments distincts d’un ensemble E est aussi appelé k -arrangement de E. c.

Démonstration : Choisir un k -uplet revient à remplir k cases avec des éléments distincts de E. Case 1 Case 2 Case k n choix n−1 choix n−k.... »