Déjà plus de
1 million
d'inscrits !
Factorielle, k-uplet, permutation et combinaison
Déjà plus de
1 million
d'inscrits !
Avant de commencer, regarde la vidéo
Introduction :
La découverte des ensembles a débuté en seconde avec :
Nous allons dans ce cours aborder les propriétés des ensembles finis quelconques. Plus particulièrement, nous nous attarderons sur les concepts fondamentaux permettant de calculer le nombre d’éléments (ou le cardinal) de ces ensembles.
Principe additif et multiplicatif
Avant d’introduire ces deux principes, il faut savoir que « dénombrer », c’est compter le nombre d’éléments que contient un ensemble fini, c’est-à-dire en déterminer le cardinal.
Cardinal d’un ensemble fini :
Soit un ensemble fini.
On appelle cardinal de le nombre de ses éléments.
Soit l’ensemble .
Nous allons donc voir un certain nombre de formules permettant d’exprimer le cardinal d’un ensemble donné.
Principe additif
Commençons par regarder le cas de la réunion de deux ensembles finis.
Soit et deux ensembles finis.
Nous avons la formule suivante :
Prenons un exemple très simple : dans une classe de élèves, étudient l’anglais et l’espagnol, élèves étudient les deux langues.
Ainsi, élèves étudient soit l’anglais, soit l’espagnol, soit les deux.
On en déduit aussi que élèves n’étudient ni l’anglais ni l’espagnol.
Rappelons maintenant la définition d’un sous-ensemble.
Sous-ensemble :
si tout élément de est aussi un élément de .
En première, nous avons également abordé la notion de partition d’un ensemble fini, que nous redonnons ici.
Partition d’un ensemble fini :
Soit et des sous-ensembles non vides d’un ensemble fini .
Si
Soit
On constate que :
Nous remarquons aussi que
Soit
Reprenons l’exemple précédent.
Comme
Principe multiplicatif
Après avoir vu les propriétés du principe additif, découvrons le principe multiplicatif et définissons le produit cartésien de deux ensembles, avant de généraliser et de donner les propriétés principales qui en découlent.
Produit cartésien de deux ensembles :
Le produit cartésien de deux ensembles
Le produit cartésien n’est pas commutatif :
Prenons le produit cartésien suivant :
Nous pouvons voir aussi que, comme dit plus haut, le produit cartésien n’est pas commutatif :
Maintenant, généralisons au produit cartésien de plusieurs ensembles.
Soit
Le produit cartésien de
Donnons quelques propriétés du produit cartésien.
Alors,
On a :
Les éléments d’un produit cartésien de
Prenons un exemple simple, pour mieux comprendre.
Soit
Soit
Soit
Soit
Nous avons aussi :
Et illustrons la dernière propriété grâce aux nombres binaires.
Soit
Soit le produit cartésien
Nous avons aussi :
Ainsi, par exemple, avec
Parties, permutations et
Nombre des parties d’un ensemble et applications
Un autre calcul fondamental consiste à compter les parties d’un ensemble
On remarque pour cela que choisir une partie
Soit
Le nombre des parties de
L’ensemble vide (pour chaque élément de
Nous allons ici donner trois applications qui découlent de tout ce que nous venons de voir.
Le nombre de parties de
Prenons un mot de longueur
Prenons l’expérience d’une pièce de monnaie non truquée qu’on lance
En utilisant un arbre pour représenter cette succession d’épreuves de Bernoulli, nous aurons une racine et des nœuds à
En reprenons la même expérience du lancer de la pièce de monnaie, nous obtenons l’arbre suivant :
Remarque : Nous reviendrons longuement, dans la partie « Probabilités », sur les épreuves de Bernoulli.
Nombre de
Dans la première partie, nous avons défini les
Nous allons maintenant parler des
Ici, l’ordre est important :
Commençons par donner deux propriétés.
Soit
Nous allons maintenant donner deux exemples pour bien comprendre ces propriétés et notamment leur logique.
Soit une urne de
N’oubliez pas que le tirage de boules dans une urne (avec ou sans remise) permet de modéliser bon nombre de problèmes, cela vous sera souvent utile !
Donnons encore un exemple concret du nombre de
Combien peut-on écrire de nombres de
Nous sommes ici en présence du
Nous avons donc :
Nombre de permutations d’un ensemble fini et factorielle
Intéressons-nous maintenant à une nouvelle notation mathématique :
Commençons par définir cette nouvelle notion, que nous pouvons en fait comprendre intuitivement.
Permutation :
On appelle permutation d’un ensemble
Soit l’ensemble
Pour calculer le nombre de permutations d’un ensemble fini, nous utilisons la propriété suivante.
Le nombre de permutations d’un ensemble à
Chaque mot correspond tout simplement à une permutation de l’ensemble
Reprenons la formule que nous avons vue pour déterminer le nombre de
Combinaisons et triangle de Pascal
Tout d’abord, nous allons définir la combinaison de
Combinaison et dénombrement
Combinaison :
Soit
On appelle combinaison de
Une combinaison est un sous-ensemble.
Le nombre de combinaisons de
Dans un ensemble
Dans la pratique, le nombre
Prenons une urne contenant
Nous pouvons remarquer que
Nous considérons
Examinons maintenant les différents cas possibles.
L’exemple que nous venons de prendre nous montre que :
Et ceci est intuitivement compréhensible dans notre triple tirage :
Nous retrouvons ainsi les propriétés vues plus haut.
Et nous pressentons aussi la symétrie des coefficients binomiaux, que nous expliciterons dans la partie suivante.
Coefficient binomial et triangle de Pascal
Dans cette sous-partie, nous allons passer en revue des propriétés importantes permettant notamment de simplifier le calcul du coefficient binomial, puis nous établirons la « fameuse » formule de Pascal.
Démontrons cette dernière propriété.
Prenons le cas du Loto et plus précisément du tirage de
Nous pouvons aussi utiliser la seconde formule donnée :
Remarquons au passage que, si nous ne jouons qu’une seule grille, et donc une seule combinaison, nous avons
Il s’agit de tirages sans remise, simultanés, et l’ordre n’a pas d’importance.
Donnons maintenant deux nouvelles propriétés des coefficients binomiaux.
Soit
Si de plus
Nous allons démontrer la formule de Pascal.
Soit
Soit
Soit un élément
Soit
Soit
On les obtient en ajoutant l’élément
Nous pouvons maintenant passer à la construction du triangle de Pascal.
Si nous plaçons les coefficients binomiaux dans un tableau avec les
Nous plaçons dans un premier temps les coefficients suivants (selon les propriétés vues plus haut) :
Ensuite, selon la formule de Pascal, il suffit de faire la somme du coefficient juste au-dessus et de celui à gauche de ce dernier.
Nous pouvons également utiliser la propriété de symétrie.
Commençons à remplir, de manière détaillée, le triangle jusqu’à
$k=3$ | ||||
Maintenant que nous avons compris le principe, remplissons simplement le triangle de Pascal, jusqu’à
$2$ | $2$ | |||||||||
Conclusion :
Nous avons découvert la notion de combinatoire, une partie importante des mathématiques que l’on appelle « discrètes » (par opposition à « continues ») et qui s’intéressent notamment aux ensembles dénombrables.
Et cette branche a une part prépondérante aujourd’hui, car la recherche et le développement informatiques reposent en grande partie dessus.
En outre, nous nous sommes servis dans ce cours des épreuves de Bernoulli, que nous détaillerons dans la partie sur les probabilités. Ainsi la combinatoire y est-elle également importante.