L’analyse combinatoire consiste à compter les éléments de certains ensembles finis.
Dans les chapitres précédents nous avons établi plusieurs résultats importants concernant le dénombrement :
Soit E un ensemble de cardinal p et F un ensemble de cardinal q:
De manière générale, soient n ensembles (Ei)i=1… n tels que chaque Ei a un nombre pi d’éléments alors le produit cartésien E1× … × En a pour cardinal ∏i=1n pi.
On peut généraliser ce résultat de la manière suivante. Si on doit faire n choix consécutifs et qu’à l’étape i, le nombre de choix différents possibles est pi alors le nombre de choix total est ∏i=1n pi. Ce résultat se montre par récurrence sur n.
Le nombre d’arrangements Ank compte le nombre de manière de choisir en les classant k éléments dans un ensemble E à n éléments.
Le tiercé consite à choisir dans le bon ordre 3 chevaux gagnants parmi les n chevaux en course. Il y a n(n−1)(n−2) combinaisons possibles, soit pour une course de 20 chevaux 6840 combinaisons.
Le nombre d’arrangements de k éléments d’un ensemble E peut se formaliser comme le nombre d’applications injectives de [1,k] dans E.
Pour construire une injection de [1,k] dans E, il suffit de choisir f(1) puis f(2) en satisfaisant f(2)≠f(1) puis f(3) différent des précédents et finalement f(k).
Si k=0 alors l’ensemble [1,k] est vide et il y a une seule application injective.
Si 0<k≤ n alors à l’étape i, il y a n−i+1 choix possibles et donc le nombre d’arrangements est
si k≤ n alors Ank= |
| (n−i+1)=n(n−1)… (n−k+1) |
Dans le cas où n<k alors il n’y a pas d’application injective de [1,k] dans E (lemme des tiroirs) et donc le nombre d’arrangements est nul.
si n < k alors Ank=0= |
| (n−i+1)=n(n−1)… (n−k+1) |
Une permutation est une application bijective d’un ensemble fini dans
lui-même.
Le nombre de permutations sur un ensemble E à n
éléments est égal au nombre d’arrangements de [1,n] dans
E. En effet si on se donne une manière d’énumérer les éléments de E :e1,…,en. Il suffit de se donner pour chaque i la valeur f(i) de l’application pour ei et toute application injective d’un ensemble fini dans un ensemble de même cardinal est bijective.
Le nombre de permutations est donc ∏i=1n (n−i+1)=n(n−1)…
1. Ce nombre est connu sous le nom de factorielle de n et est
noté n!.
La définition récursive de cette fonction est donnée par les équations :
0!=1 (n+1)!=(n+1)n! |
On remarque que si k≤ n alors le nombre d’arrangements peut s’exprimer en utilisant la fonction factorielle.
Ank= |
|
Dans un arrangement, les éléments choisis sont ordonnés. On cherche parfois à dénombrer des parties dans lesquelles l’ordre n’a pas d’importance. Par exemple si on joue au loto plutôt qu’au tiercé, le but est d’avoir k numéros corrects parmi 49 possibilités, mais l’ordre du tirage n’intervient pas comme critère de gain.
Le nombre de combinaisons de k éléments dans un ensemble à n éléments est noté Cnk.
On peut relier le nombre de combinaisons et le nombre d’arrangements. Si on veut arranger k éléments parmi n on peut d’abord identifier un sous ensemble de k éléments parmi n (on a Cnk possibilités) puis les ordonner (k! différentes possibilités). On obtient au final :
Ank = Cnk k! |
On a en particulier Cn0=1, Cnn=1 , Cnk=0 si n<k.
Dans le cas où k≤ n on obtient la formule:
Cnk= |
|
Lorsque l’on doit calculer à la main les combinaisons, la formule suivante est utile et valable si 0<k : Cnk=n(n−1)…(n−k+1)/k(k−1)… 1. Dans cette formule, on a le même nombre de produits en numérateur et en dénominateur.
On retiendra en particulier les cas suivants : Cn1=n Cn2=n(n−1)/2
Si k≤ n alors choisir k éléments parmi n est équivalent à choisir n−k éléments parmi n (ceux qui restent). On en déduit la formule :
Cnk=Cnn−k |
On peut également trouver une formule de récurrence pour les combinaisons. Supposons que l’on veuille choisir k éléments dans un ensemble à n+1 éléments et essayons de nous ramener au choix dans un ensemble à n éléments. Dans l’ensemble E qui à n+1 éléments on particularise un élément e. Soit une partie à k éléments dans E avec 1≤ k. Soit elle contient e soit elle ne contient pas e. On compte d’abord le nombre de parties à k éléments qui contiennent e, il y en a exactement autant que le nombre de parties à k−1 éléments dans E∖{e} soit Cnk−1. On compte ensuite le nombre de parties à k éléments qui ne contiennent pas e, il y en a exactement autant que le nombre de parties à k éléments dans E∖{e} soit Cnk. On obtient la formule de récurrence suivante:
Cn+1k=Cnk+Cnk−1 |
A partir de cette formule on peut construire le Triangle de Pascal qui nous donne les valeurs des nombres de combinaisons juste en faisant des additions. On choisit de mettre l’indice k en colonnes et n en lignes. On peut remplir la première colonne et la diagonale en utilisant Cn0=Cnn=1, pour les autres données, on utilise la formule du binôme en aditionnant la valeur de la case du dessus et de celle dans le coin en haut à gauche.
|
Les combinaisons apparaissent naturellement dans la formule du binôme :
(x+y)n=Σk=0n Cnk xk yn−k |
La preuve se fait par récurrence sur n.
|
Preuve: On a (x+y+z)n = Σk=0n Σl=0n−k Cnk Cn−kl xkylzn−k−l
On remarque que Cnk Cn−kl=n!/k!l!(n−k−l)!.
On généralise en :
(x1+⋯ +xk)n = Σ{0≤ n1,…,nk|n1+⋯+nk =n} |
| x1n1… xknk |
.
□
On a donc en tout Cnp Sm,p solutions.
nm=Σp=1n Cnp Sm,p |
|
□