Dans ce chapître, tous les ensembles sont des ensembles finis.

Rappel

Soit E un ensemble.

Si E a n éléments, on dit que E est un ensemble fini.

On dit que le cardinal de E est n et on le note : card(E) = n .

Si E et F sont deux ensembles finis, l'ensemble des couples (x,y) formés d'un élément de E et d'un élément de F est noté  EF .

EF est alors un ensemble fini et on a :

card(EF) = card(E) card(F)

D'autre part, on rappelle l'expression de la factorielle de n :

n! = n(n-1)(n-2)...321

Par convention, 0! = 1.

a. Ensembles, p-uplets (ou p-listes) et dénombrement

Définition

Soit p un entier naturel non nul et (Ei)1<i<p une famille d'ensembles.

L'ensemble E1E2 ... Ep est l'ensemble des listes constituées d'un élément x1 de E1, d'un élément x2 de E2, ... , d'un élément xp de Ep.

On note une telle liste (x1,x2,...,xp).

Définition

Soit p un entier naturel non nul et E un ensemble fini.

Un p-uplet, ou une p-liste, d'éléments de E est une liste ordonnée de p éléments de E, distincts ou confondus.

On note Ep l'ensemble de tous les p-uplets.

Remarque :

Un 2-uplet s'appelle un couple, un 3-uplet est un triplet.

Formule

Soit un ensemble E fini de cardinal n et p un entier naturel non nul. On a :

card(Ep) = (card E)p = np

b. Arrangements de p éléments pris parmi un ensemble de cardinal n

Définition

Soit un ensemble E fini de cardinal n et p un entier naturel non nul.

Un arrangement de p éléments (ou p-arrangements) de E est une p-liste d'éléments deux à deux distincts pris parmi les éléments de E.

Le nombre de p-arrangements de E est noté :

Remarque :

Le nombre d'arrangements se "traduit" par "combien y a-t-il de manière de tirer p éléments parmi n sans remise avec prise en compte de l'ordre".

Propriété

Si n et p sont deux entiers naturels avec 0 p n , alors :

Démonstration :

La formule ci-dessus se démontre facilement : raisonnons avec des boules dans un sac.

On doit tirer p boules parmi les n que comporte un sac.

Au premier tirage, nous avons n possibilités (car il y a n boules dans le sac).

Au deuxième tirage, nous avons n-1 possibilités (car il reste n-1 boules dans le sac, une boule ayant déjà été prélevée).

Au troisième tirage, nous avons n-2 possibilités (car il reste n-2 boules dans le sac, deux boules ayant déjà été prélevées).

...

Au p-ième tirage, nous avons n-p+1 possibilités (car il reste n-p+1 boules dans le sac, p-1 boules ayant déjà été prélevées).

Le nombre d'arrangements possibles est donc   n(n-1)(n-2)...(n-p+1)   et on écrit alors :

c. Permutations de n éléments

Définition

Soit n un entier non nul et E un ensemble de cardinal n.

Une permutation des éléments de E est un n-arrangement des n éléments de E.

Propriété

Le nombe de permutations d'un ensemble E de cardinal n est n! .

Remarque :

Le nombre de permutations se "traduit" par "combien y a-t-il de manière de ranger dans un ordre quelconque n éléments".

Démonstration :

On peut soit reconsidérer un sac de n boules et compter le nombre de manières de tirer la première boule (n manières), la deuxième (n-1) manières, ... puis la dernière (1 manière, c'est la dernière boule !) et en multipliant tout on obtient :

n(n-1)(n-2)...321 = n!

On peut aussi écrire que le nombre de permutations est le nombre d'arrangements dans le cas n = p et on obtient :

a. Combinaisons

Définition

Soit n et p deux entiers naturels avec p n et E un ensemble fini de cardinal n.

Un sous-ensemble de E et appelé combinaison de p éléments (ou p-combinaison) de E , ces éléments étant tous distincts.

Le nombre de p-combinaisons de E est noté :

Remarque :

Le nombre de combinaisons se "traduit" par "combien y a-t-il de manière de tirer p éléments parmi n sans remise et sans prendre en compte l'ordre des éléments tirés".

Propriété

Si n et p sont deux entiers naturels avec 0 p n , alors :

Démonstration :

Considérons une p-combinaison de E: à partir de ses éléments, on peut faire (d'après ce qui précède) p! permutations chacune représentant un p-arrangement de E. On peut donc écrire la relation suivante :

d'où :

b. Combinaisons et triangle de Pascal

Théorème

Soit n et p deux entiers naturels quelconques tels que 0 p n . On a :

Théorème   Formule du "triangle de Pascal"

Soit n et p deux entiers naturels quelconques tels que 1 p n . On a :

Remarque :

Ce tableau a été construit à l'aide de la formule précédente : elle permet de calculer très rapidement les coefficients du binôme de Newton (cf. § suivant), qui apparaissent sur chaque ligne.

Ces formules se démontrent très facilement en les traduisant sous forme fractionnaires.

c. Formule du binôme de Newton

Formule   Binôme de Newton

Pour tous x et y réels (ou complexes) et pour tout n entier naturel. On a :

Remarque :

On déduit de cette formule et du tableau précédent les développements suivants :

(x+y)0 = 1

(x+y)1 = x + y

(x+y)2 = x2 + 2xy + y2

(x+y)3 = x3 + 3x2y + 3xy2 + y3

(x+y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4

(x+y)5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5

(x+y)6 = x6 + 6x5y + 15x4y2 + 20x3y3 + 15x2y4 + 6xy5 + y6

(x+y)7 = x7 + 7x6y + 21x5y2 + 35x4y3 + 35x3y4 + 21x2y5 + 7xy6 + y7

Et ainsi de suite ...