Pré Requis :

• Cardinal d'un ensemble fini
• Deux ensembles ont même cardinal s'ils sont en bijection.
• Dénombrement d'unions disjointes.

I) Représentation graphique :

1. Diagrammes :

• En bleu : A  B
• En gris : AB

Card(A  B) = Card A +Card B - Card(A  B)
 
 

Card () = Card E - Card A
 
 

Exple de dénombrement :

Elèves pratiquant plusieurs langues. (classique)
 
 

2) Arbres :

Un arbre représente un ensemble fini d'événements; on le note A.

On le munit d'une relation d'ordre partiel notée"---" vérifiant :

• A admet un plus petit élément : 0
• aA \ { 0 } , l'ensemble des minorants stricts de a admet un plus grand élément.

Définitions :

• a est un successeur de b
• b est le prédécesseur de a
• [ab] est une branche de A
• { successeurs de b } = ramification de A
• Un élément qui n'a pas de successeur est un élément terminal de A
• { minorants de a } est la branche allant de 0 à a

Dans une urne, on dispose de boules blanches et de boules noires.

On effectue des tirages successifs dans cette urne :

• Si la boule tirée est blanche, on la remet dans l'urne
• Si elle est noire, on l'enlève

Dénombrer les cas possibles. (faire un arbre)
 
 

Principe multiplicatif :

Définition :

A est dit régulier de rang m ( supérieur ou égal à 1 ), si k [| 0,m-1 |] au rang k,chaque ramification a un même nombre de branches.
 
 

Théorème :

Soit A régulier de rang m ( supérieur ou égal à 1 );

Soit (n_k)_{0km - 1}

n_k le nombre de branches de la k^ième ramification, alors A a  éléments terminaux.

Preuve : par récurrence sur le rang de A
 
 

II) Arrangements ,permutations :

1. Dénombrement. Arrangement :

 

 
 
 

Soit n > 0 , np >0 :

E= { x₁,x₂,…,x_n } ,ensemble à n éléments distincts.

Déf:

Un p-arrangement de E est un p-uplet d'éléments distincts de E.

Théorème :

Le nombre de p-arrangement de E est n(n-1)…(n-p+1).

On le note 
 
 

2. Dénombrements des permutations :

Une permutation de E est un n-arrangement de E.
 
 

Théorème :

Il y a n(n-1)…2*1 permutations. On note ce nombre : n !

Rque :

Pour op < n ,=

Pour p=n on pose 0! =1 , Aⁿ_n = = n!
 
 

III) Exples d'utilisation :

• Tirage sans remise
• Lien entre arrangements et injections et entre permutations et bijections
• Dénombrement des combinaisons.