Combinaisons

E est un ensemble fini de cardinal n : Card(E) = n.
Pour p entier appartenant à {0 ; 1 ; 2 ; ... ;n}, on note E_p l'ensemble des parties de E ayant exactement p éléments.

Définition:
On appelle Combinaison de p éléments pris parmi les n éléments de E tout choix de p éléments de E, sans ordre et sans remise. Cela correspond donc au choix d'une partie de E ayant p éléments, ou d'un sous-ensemble de E à p éléments.
C'est donc un élément de E_p.

Par exemple, si E = {1 ; 2 ; 3 ; 4}, choisir une Combinaison de 2 éléments parmi les 4 éléments de E, c'est choisir un de des ensembles suivants:
{1;2} ou {1;3} ou {1;4} ou {2;3} ou {2;4} ou {3;4}
Il faut attention à ne pas confondre {1;2} qui est la partie de E contenant les éléments 1 et 2, avec le couple (1;2) qui est un élément du produit cartésien ExE.
La partie {1;2} et la partie {2;1} sont identiques, alors que les couples (1;2) et (2;1) sont distincts.

Nombre de Combinaisons à p éléments dans un ensemble à n éléments:
Pour p quelconque compris entre 0 et n, on note C^p_n le nombre de Comninaisons de p éléments parmi les n éléments de E. Ce nombre correspond au cardinal de E_p.
On sait par ailleurs, que le nombre de p-listes dans E est A^p_n.
Appelons A(n,p) l'ensemble des p-listes de E.
A toute p-listes de E, correspond une et une seule partie à p éléments de E.
C'est la partie de E dont les éléments sont ceux apparaissant dans cette p-listes.

Par exemple, prenons E = {1;2;3;4} et p = 3.
                    Si on a la 3-liste suivante (2 ; 1 ; 4) alors on a la partie de E suivante {2 ; 1 ; 4}.
                    Si on a la 3-liste suivante (3 ; 2 ; 4) alors on a la partie de E suivante {3 ; 2 ; 4}.
                    Si on a la 3-liste suivante (2 ; 4 ; 3) alors on a la partie de E suivante {2 ; 4 ; 3}
                    mais les parties {3 ; 2 ; 4} et {2 ; 4 ; 3} sont identiques.
                    On voit alors que, d'une façon plus générale, deux p-listes formées des mêmes
                    éléments donneront la même partie de E à p éléments.
                    On peut alors former une partition sur l'ensemble A(n,p) des p-listes de E.
                    Pour toute partie F de E à p éléments, on note A(F) l'ensemble des p-listes donnant
                    cette partie F.
                    La suite des A(F) où F parcourt l'ensemble des parties de E à p éléments est une
                    partition de A(n,p).
                    On remarque qu'il autant de A(F) qu'il y a de parties à p éléments dans E, et pour cause!
                    De plus, pour une partie à p éléments F de E, on peut former exactement p! p-listes
                    possibles. C'est simplement toutes les possibilités d'écrire une p-liste en utlisant
                    les p éléments de F.
                    Il y a donc p! fois plus de p-listes dans E que de parties à p éléments dans E.
                   Ou encore,
                    il y a p! fois plus de p-listes dans E que de Combinaisons à p éléments dans E.

Donc, On a la relation : p!xC^p_n = A^p_n.
Ceci permet alors de dire:

Le nombre de Combinaisons de p éléments pris parmi n éléments est:

(Formule 1)

On peut remarquer que la seule partie de l'ensemble vide est l'ensemble vide lui-même.
Donc, C⁰₀ = 1. C'est des raisons qui font que la convention veut que 0! = 1.
On peut aussi remarquer que l'ensemble vide ne possède aucune partie à 1 élément, (par défintion).
On a donc C¹₀ = 0.
De plus, pour tout ensemble E, la seule partie de E ayant 0 élément est l'ensemble vide.
Donc pour tout n entier , on a : C⁰_n = 1
Ce n'est pas une simple plaisanterie. C'est cette petite remarque qui va permettre de construire par la suite le TRIANGLE DE PASCAL avec un minimum de renseignements.
Propriétés de Calcul:
Les principales propriétés des à savoir sont:

Cette relation est évidente pour deux raisons:
1: Il suffit d'utiliser la relation précédente pour le voir.
2: Choisir une partie à p éléments dans E, c'est choisir son complémentaire qui, lui, a (n-p) éléments. Il y a donc autant de parties à p éléments dans E que de parties à (n-p) éléments dans E.

Cette formule permet alors le
calcul des coefficients
par récurrence.

On a vu que

et pour tout entier n

On obtient le Triangle De Pascal.

On peut biensur, montrer cette formule par un calcul en utilisant la Formule 1. C'est particulièrement maladroit et en plus cela ne montre en rien en quoi cette formule peut se généraliser.
Considérons un ensemble E à n éléments et fixons un élément e dans E.
Une partie F de E ayant p éléments peut être de deux types.
1: Elle contient l'élément e.
2: Elle ne contient pas l'élément e.
Dans le premier cas, F contient e et il lui manque exactement (p-1) à choisir parmi les (n-1) éléments de E qui ne sont pas e.
Il y a alors façons de construire F.
Dans le second cas, F ne contient pas e, il lui manque donc p éléments à choisir parmi les (n-1) éléments de E qui ne sont pas e
Il y a alors façons de construire F.
Comme au total il y a façons de choisir F, on a bien la relation

Triangle de Pascal:
L'idée du triangle de Pascal est de présenter les sous forme de tableau à double-entrées.
En colonne, les valeurs de p et en ligne les valeurs de n.
Les colonnes et les lignes sont numérotées à partir de 0, et la case correspond à la p-ème colonne et n-ème ligne est le coefficient .
Or les formules précédentes montrent deux choses.
1: Il y a une symétrie dans ce tableau car
2: Si on connait les éléments de la ligne (n-1), on connait automatiquement ceux de la ligne n par la formule
D'où le Triangle de Pascal:

	0	1	2	3	4	p-1	p
0	1	0
1	1	1	0
2	1	2	1	0
3	1	3	3	1	0
4	1	4	6	4	1

n-1
n