I. k-uplets d’éléments distincts d’un ensemble à éléments connu également sous le nom de k-arrangements
Définition
Soit un ensemble ayant éléments distincts.Un k-uplet (ou k-arrangement avec ) est une suite ordonnée de éléments distincts choisis dans .
Nombre de k-uplets et arrangements
Définition de la factorielle
Définition : Soit un entier naturel non nul. On appelle factorielle de le nombre :
Par convention, .
Définition d'un arrangement : Soit A un ensemble fini non vide à éléments et un entier naturel inférieur ou égal à . Un arrangement de éléments de (ou k -arrangement) est un k -uplet
d’éléments distincts de .
Comme l’ordre compte, pour construire un k-uplet de , on choisit :
Le premier élément parmi les disponibles, le deuxième élément parmi les restants, etc., jusqu’au -ième élément.
Le nombre total de k-uplets distincts est donc : .
On le note parfois ou . En notation factorielle, cela s’écrit : .
Exemples :
Si , alors et sont deux arrangements de trois éléments de . Ce sont deux 3-arrangements de .
Remarque : Un arrangement de peut être interprété comme un tirage avec ordre et sans remise des éléments de .
Propriété : Soient un ensemble fini non vide à éléments, et un entier naturel tel que .
Le nombre de -arrangements de est égal à :
Exemple : On dispose de trois jetons et de cinq boîtes notées , , , et . On doit ranger les jetons dans les boîtes, une boîte ne pouvant pas contenir deux jetons.
On dispose de cinq possibilités pour le premier jeton, de quatre possibilités pour le deuxième jeton, et de trois possibilités pour le troisième jeton.
Les rangements possibles sont les 3-uplets d’éléments deux à deux distincts de l’ensemble . Leur nombre est : .
II. Permutations d’un ensemble à éléments
Définition : Soit un ensemble fini non vide à éléments. Une permutation de est un -uplet d’éléments distincts de .
Remarque : Une permutation est un -arrangement.
Exemple : Si , les permutations de sont :
.
Propriété : Le nombre de permutations d’un ensemble fini non vide à éléments est : .
Exemple : Si , on a bien permutations possibles.
2.2. Nombre de permutations
Une permutation d’un ensemble de éléments est un réarrangement complet de ces éléments.
Le nombre de permutations de éléments (c’est-à-dire, le nombre de façons de les ordonner) est : .
Remarque :
Les permutations correspondent au cas particulier des k-uplets où .
Dans ce cas, la formule devient .
III. Parties et combinaisons d'un ensemble fini
1. Parties
Soit un ensemble fini dont la cardinalité est , c’est-à-dire .
On appelle partie (ou sous-ensemble) de tout ensemble tel que .On cherche à déterminer le nombre total de parties de . On note généralement l’ensemble de toutes les parties de par .
La question est donc : Combien y a-t-il d’éléments dans ?
Un exemple : Prenons un petit ensemble :
Si (ensemble vide, ), la seule partie de est elle-même. Donc .
Si (un seul élément, ), les parties de sont et .
Il y en a 2 au total, donc .
Si (deux éléments, ), les parties de sont :
Il y en a 4, donc .
Conjecture : lorsque a éléments, le nombre de ses parties serait . Voyons pourquoi.
Justification par le principe multiplicatif
a) Décomposition de la formation d’une partie
Pour construire une partie (sous-ensemble) de :
Chaque élément de peut soit être inclus dans la partie,
soit être exclu de la partie.Il y a donc 2 choix (inclure ou non) pour chaque élément.
b) Application du principe multiplicatif
Puisque le choix concernant chaque élément est indépendant du choix fait pour les autres éléments, on applique le principe multiplicatif :Nombre total de façons de choisir = produit du nombre de choix pour chaque élément.
Pour chaque élément de , on a 2 possibilités.
Il y a éléments dans . Donc,
Conclusion :
2. Combinaisons
Définition : Soient et deux entiers naturels tels que , et un ensemble fini de cardinal . On appelle combinaison de éléments de toute partie de ayant éléments.
Le nombre de combinaisons de éléments de est noté .
Remarque : Les nombres sont également appelés coefficients binomiaux et se lisent « parmi ».
Exemple :
Soit .
i) Les parties de sont : , , , , , , , .
ii) Il y a 3 parties à 1 élément.
iii) .
Propriété :
Soient et deux entiers naturels tels que , alors :
.
i) Symétrie : .
ii) Exemples particuliers :
si , : Il n’y a qu’une seule façon de ne rien choisir : le sous-ensemble vide .
si , : Choisir un élément parmi donne sous-ensembles à 1 élément.
si , : Pour choisir 2 éléments sans ordre parmi , on a possibilités.
est une relation intéressante (simplification de fractions etc.) dont on peut donner un exemple
iii) Relation de Pascal :
Pour tous entiers naturels et tels que , on a :
.
5. Symétrie et triangle de Pascal
5.1. Symétrie
On a la propriété de symétrie :
Autrement dit, choisir éléments ou ne pas choisir éléments (ce qui revient à choisir éléments) donne le même nombre de sous-ensembles.
5.2. Relation de Pascal
Les coefficients de combinaisons vérifient la relation de Pascal :
.
Cette relation donne naissance au triangle de Pascal. On peut l’interpréter de manière combinatoire : pour choisir éléments parmi , on distingue les sous-ensembles contenant un élément spécifique (disons le premier) et ceux ne le contenant pas.
Triangle de Pascal : (issu de Wikipedia)
Présenté également souvent ainsi :
À l'intersection de la ligne et de la colonne , on lit l'entier .
On commence par écrire les « 1 » dans la 1ère colonne et sur la diagonale, puis on utilise la relation de Pascal, selon le schéma :
Propriété : Soit un entier naturel. Alors :
Démonstration :
Par dénombrement, on compte le nombre de parties d’un ensemble à éléments.
Il y a parties à 0 élément, parties à 1 élément, ...
En tout, il y a parties d’un ensemble à éléments (chaque élément peut être présent ou absent).
Ainsi, en sommant les pour allant de à , on obtient la relation : .
IV. Lien entre les sous-ensembles et d’autres objets combinatoires
Lorsque nous comptons les parties (sous-ensembles) d’un ensemble à éléments, nous obtenons un total de . Ce résultat se retrouve de manière équivalente dans plusieurs situations :
nombre de parties de à éléments et n-uplets de
Pour construire un sous-ensemble de , on considère étapes où pour chaque élément de , on décide de le choisir ou de ne pas le choisir pour l’inclure dans le sous-ensemble. Il y a donc deux possibilités par étape et il y a étapes. On retrouve bien qu'il y a sous-ensembles possibles.
Ainsi, il existe une correspondance bijective entre les sous-ensembles de et les -uplets de .
Mots de longueur sur un alphabet à deux éléments
Un mot binaire de lettres (0 ou 1) correspond aussi à un sous-ensemble (présence/absence).
Chemins dans un arbre
Dans un arbre binaire complet de hauteur , chaque étage représente un choix « à gauche » ou « à droite » (analogue à 0 ou 1).
Un chemin complet du sommet à une feuille peut donc être vu comme une suite de choix, exactement comme les -uplets de .
Le nombre total de chemins (et donc de feuilles) est .
Issues dans une succession de épeuves de Bernoulli
Une épreuve de Bernoulli est un « tirage » à deux résultats possibles (réussite/échec, pile/face, etc.).
Sur épreuves, la collection de résultats forme une suite binaire de longueur .
Le nombre total de suites (donc d’issues possibles) est également .
Conclusion
Toutes ces situations (sous-ensembles d’un ensemble à éléments, -uplets de , mots binaires de longueur , chemins dans un arbre binaire, issues de épreuves de Bernoulli) sont reliées par une bijection commune et se comptent toutes par la même formule :
En résumé :
Factorielle : sert à compter les arrangements complets (permutations) de objets :
k-uplets (arrangements partiels) : on prend objets dans un ordre précis :
Combinaisons : on prend objets sans ordre : , avec diverses interprétations (mots binaires, chemins, etc.).
Le triangle de Pascal : donne à la fois une interprétation combinatoire et une construction pratique des nombres .
IV. Exercices d'application directe
Exercice 1 :
Soient et .
Déterminez l'ensemble des -uplets formés avec les éléments de .
Déterminez l'ensemble des -uplets formés avec les éléments de et , où les deux premiers éléments proviennent de et le troisième de .
Combien y a-t-il de -uplets au total dans le cas de la question précédente ?
Solution exercice 1 :
Les -uplets de sont : , , , .
Les -uplets formés sont :
, ,
, ,
, ,
, , .
Il y a -uplets.
Exercice 2 :
Une urne contient boules, numérotées de à .
Combien de façons existe-t-il de choisir boules parmi les sans tenir compte de l'ordre ?
Combien de façons existe-t-il de choisir boules parmi les ?
Combien de façons existe-t-il de ne pas choisir une seule boule, c'est-à-dire d'en choisir ?
Solution exercice 2 :
Le nombre de façons de choisir boules parmi est :
.
Le nombre de façons de choisir boules parmi est :
.
(Remarque : .)
Le nombre de façons de choisir boules parmi est :
.
Exercice 3 :
Combien de mots de lettres distinctes peut-on former en utilisant les lettres , , , et ?
Combien de mots différents de lettres peut-on former en utilisant les lettres , , , et sans répétition, et en considérant l'ordre des lettres ?
En utilisant toutes les lettres du mot "PARIS", combien de mots différents peut-on former, en considérant que chaque mot est une permutation des lettres ?
Solution exercice 3 :
En utilisant toutes les lettres , , , , et , on forme mots différents :
.
Pour former des mots de lettres sans répétition, le nombre de possibilités est donné par nombre de -uplets formés avec ces lettres :
.
En utilisant toutes les lettres de "PARIS", le nombre de mots différents formés est :
.