Combinatoire
 |
♦ Le cours à compléter : |  |
♦ Le cours complété : | bientôt |
I. Ensemble fini et cardinal.
II. Principe additif.
III. Principe multiplicatif.
IV. Arrangements.
V. Permutations.
VI.Combinaisons.
VII.Coefficients binomiaux.
VIII. Parties d’un ensemble.
echiquier Lucas
Ensembles finis
Définition :
On dit qu’un ensemble E est fini lorsqu’il admet un nombre fini d’éléments.
Le nombre d’éléments de E est appelé le cardinal de l’ensemble et il est noté : card(E) ou |E|.
Par convention, l’ensemble vide ∅ est un ensemble fini de cardinal 0.
Point Méthode : Déterminer le cardinal d'un ensemble
Remarque :
♦ Dénombrer, c’est compter le nombre d’éléments que contient un ensemble fini, c’est à dire en déterminer le cardinal.
♦ Certains ensembles ne sont pas finis : L'ensemble ? des entiers naturels, l'ensemble des nombres réels de l'intervalle [ 0 ; 1 ].......
principe additif
Définition :
On dit que deux ensembles sont disjoints s’ils ont aucun élément en commun.
Propriété :
Si E et F sont deux ensembles finis, alors Card(E∪F)=Card(E)+Card(F)−Card(E∩F)
Si Eet F sont deux ensembles finis et disjoints, alors Card(E∪F)=Card(E)+Card(F)
Point Méthode : Déterminer le cardinal d'une réunion d' ensembles.
Propriété : Soit E1, E2, … , En, n ensembles finis deux à deux disjoints.
Alors card(E1∪ E2 ∪ … ∪ En) = card(E1) + card(E2) + ? + card(En)
Point Méthode : Déterminer en utilisant le principe additif.
Propriété : Soit A une partie d'un ensemble fini E et B le complémentaire de A dans E
Alors card(E) = card(E∩A) + card(E∩B)
Principe multiplicatif
Définition : Soit E1, E2, Ep , p ensembles finis.
Le produit cartésien E1×E2×.....×Ep, est l'ensemble des p_uplets (e1;e2;...;ep) où ei ∈ Ei , pour 1 ≤i≤p
Propriété : Soit E1, E2, Ep , p ensembles finis.
Alors Card( E1×E2×.....×Ep)= Card( E1) ×Card( E2)×.....×Card( Ep)
Point Méthode : Dénombrer en utilisant le principe multiplicatif.
Remarque :
Attention ne pas confondre le symbole × dans ( E× F ) qui désigne le un produit cartésien des ensemble E et F avec le symbole × dans dans Card(E)× dansCard(F) qui symbolise la multiplication de deux entiers.
kuplets
Propriété : Soit E un ensemble fini à n éléments et k est un nombre entier naturel non nul.
Un k-uplet d'éléments de E est une liste ordonnée de k éléments de E, distincts ou confondus.
L'ensemble de tous les k-uplets de E est l'ensemble E×E×…×E (k fois) ; On le note Ek
Propriété : Soit E un ensemble fini à n éléments.
Card (Ek ) = card(E) k=nk
Point Méthode : Déterminer le nombre de k-uplets d’un ensemble à n éléments
Arrangements
Définition : Soit E un ensemble à n éléments. Soit k un entier tel que 1 ≤ k ≤ n.
Un arrangement de k éléments de E est un k-uplet d’éléments deux à deux distincts de E.
Propriété : Soit E un ensemble à n éléments. Soit k un entier tel que 1 ≤ k ≤ n.
Le nombre d'arrangements de k éléments de E est : n × (n−1) ×…× (n−k+1)
Point Méthode : Dénombrer en utilisant les arrangements
Permutations
Définition : Soit E un ensemble à n éléments.
Une permutation des éléments de E est un n-uplets d'éléments distincts de E.
Une permutation est un arrangement de n éléments de E.
Propriété :
Le nombre de permutations d'un ensemble fini à n éléments est : n×(n−1)×…×2×1.
Point Méthode : Dénombrer en utilisant les permutations
Point Méthode : Dénombrer en utilisant les permutations niveau 2.
factorielle
Définition : Soit n un entier naturel.
On appelle factorielle n le produit de tous les nombres entiers de 1 à n.
On note : n! = 1 × 2 × 3 × … × n
Outil : Calculateur de factorielle
♦ Simplification d'écrire avec la factorielle.
Définition : Soit E un ensemble à n éléments. Soit k un entier tel que 1 ≤ k ≤ n.
♦ Le nombre de permutations de E est : n!
♦ Le nombre d'arrangements de k éléments de E est : n! / ( n-p ) !
Combinaison
Définition : Soit E un ensemble à n éléments avec n∈N et k un entier naturel tel que 0?k?n.
Une combinaison de k éléments de l'ensemble E est un sous-ensemble de k éléments de E.
Remarque : Attention ! Ne pas confondre :
♦ Un k-uplet d'élément de E qui est un élément de l'ensemble Ek.
♦ Une combinaison de k élément de E qui est un sous ensemble de l'ensemble E.
Propriété : Soit E un ensemble à n éléments avec n∈N et k un entier naturel tel que 0?k?n.
Le nombre de combinaisons de k éléments parmi les n éléments de E, noté (nk) est :
(nk) =[ n×(n−1)×…×(n−k+1) ] / k! = n ! / k ! (n−k) !
Point Méthode : Dénombrer en utilisant les combinaisons.
Remarque : Pour tout entier naturel n
♦ (n0) = 1 ♦ (nn) = 1 ♦ (n1) = 2
Coefficients binomiaux
Définition : Soit n et k deux entiers naturels tel que 0?k?n.
Le nombre(n k ) de combinaisons de k parmi p porte également le nom de coefficient binomial.
Propriété de symétrie :
Pour tout entier k tel que 0?k?n. (n k ) = ( n n-k )
Propriété du triangle de Pascal ( démonstration exigible ) :
Pour tout entier k tel que 0?k?n (n k ) + ( n k+1 ) = ( n+1 k+1 )
♦ Le triangle de Pascal
Parties d'un ensemble
Définition : Soit E un ensemble à n éléments.
Le nombre de sous-ensembles ( parties ) de E est égal à :
Σ ( np ) = ( n0) + (n1)+ +(nn) = 2n
Savoir-faire
 |
Les savoir-faire du Chapitre : Combinatoire et dénombrement. |
♦ Savoir déterminer le cardinal d'un ensemble fini.
♦ Savoir déterminer le cardinal d'une union d'ensembles finis.
♦ Savoir dénombrer en utilisant le principe additif.
♦ Savoir dénombrer en utilisant un diagramme.
♦ Savoir déterminer le cardinal du produit cartésien d'ensembles finis.
♦ Savoir dénombrer en utilisant le principe multiplicatif.
♦ Savoir déterminer le nombre de n-uplets d'un ensemble fini.
♦ Savoir utiliser le nombre de n-uplets d'un ensemble fini.
♦ Savoir dénombrer en utilisant les arrangements.
♦ Savoir dénombrer en utilisant les permutations.
♦ Savoir dénombrer en utilisant les combinaisons.
♦ Savoir calculer des coefficients binomiaux.
♦ Savoir calculer un coefficient binomial avec le triangle de Pascal.
Démonstrations exigibles
♦ Propriété du triangle de Pascal.
♦ Nombre de parties d’un ensemble.