COMBINATOIRE ET DENOMBREMENT

Ch2 : COMBINATOIRE ET DENOMBREMENT

Définition : E est un ensemble fini.

Le cardinal de E, noté Card(E) ou E , est le nombre d’éléments de l’ensemble E.

Définition : Deux ensembles A et B sont disjoints lorsqu’ils n’ont pas d’éléments en commun. Leur

intersection est vide : A B   .

Propriété : Principe additif

Si A et B sont deux ensembles disjoints, alors Card A B Card(A) + Card(B)    .

Remarques : Cette propriété se généralise à la réunion de n ensembles finis deux à deux disjoints :

Card(𝐸ଵ ∪ 𝐸ଶ ∪ … ∪ 𝐸௡

) = Card(𝐸ଵ) + Card(𝐸ଶ) + ⋯ + Card(𝐸௡

)

Plus généralement, pour tous A et B, on a Card A B Card(A) + Card(B) Card A B        .

Définition : Le produit cartésien de deux ensembles non vides A et B, noté A B est l’ensemble des

couples (a ; b) où a est un élément de A et b un élément de B.

Remarques : A B se lit « A croix B ».

A B= a ; b , a A, b B       peut se représenter dans un tableau à double entrée.

Si A ou B est vide, alors A B .

Propriété : Principe multiplicatif

Si A et B sont deux ensembles finis, alors Card A B Card(A) Card(B)      .

Remarque : Cette propriété se généralise à n ensembles finis :

Card(𝐸ଵ × 𝐸ଶ × … × 𝐸௡

) = Card(𝐸ଵ) × Card(𝐸ଶ) × … × Card(𝐸௡

)

Le produit cartésien de A par lui-même est noté 2 A . Un élément de 2 A est un couple (…, …).

Le produit cartésien de A par lui-même p fois où p > 1 est noté A

p

.

Définition : p-uplet ou p-liste où p > 1

Un p-uplet de A est un élément de A

p

.

C’est une liste ordonnée a a a 1 2 , ,..., p  de p éléments de A, distincts ou non.

Remarque : Un 2-uplet est un couple ; un 3-uplet est un triplet.

L’ordre intervient et on considère qu’il y a remise.

Propriété : Nombre de p-uplets

Si Card (A) = n, alors le nombre de p-uplets de A est p n .

Définition : factorielle

Si n est un entier naturel non nul, factorielle de n, noté n!, est le produit de tous les entiers de 1 à n.

n n n n ! 1 2 3 ... ( 1) ... 2 1           .

Remarque : n! se lit « factorielle n »

0! 1  , par convention. n n n ! ( 1)!    ( 1)! ( 1) ! n n n    

Définition : permutation

Une permutation d’un ensemble E à n éléments est un n-uplet d’éléments distincts de E.

Propriété : Nombre de permutations

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

Propriété : Nombre de p-uplets d’éléments distincts ou p-arrangements

Si Card (E) = n et si 0  p n , alors le nombre de p-uplets d’éléments distincts de E est

!

( 1) ... ( 1)

( )!

p

n

n

n n n p A

n p

      



.

Remarque : Un arrangement de p éléments de E est considéré comme un tirage avec ordre et sans remise.

Sur la calculatrice, écrire n A p

Définition : combinaison

Si Card (E) = n et si 0  p n , une combinaison de p éléments de E est une partie (ou un sous-ensemble)

de E comportant p éléments.

Remarque : Dans une combinaison, notée entre {accolades}, l’ordre n’intervient pas et on considère qu’il

n’y a pas remise.

Propriété : Nombre de combinaisons

Si Card (A) = n et si 0  p n , alors le nombre de combinaisons de p éléments parmi n est

n

p

   

 

   

( 1) ... ( 1) ( 1) ... ( 1) !

( 1) ... 2 1 ! ( )! !

n n n p n n n p n n

p p p n p p p

                 

 

        

Remarque : Le nombre

n

p

   

 

   

qui se lit « p parmi n » est encore appelé coefficient

...