Factorielle, k-uplet, permutation et combinaison : Fiche de cours - Mathématiques

Introduction :

La découverte des ensembles a débuté en seconde avec :

$\mathbb N$ : l’ensemble des entiers naturels ;
$\mathbb Z$ : l’ensemble des entiers relatifs ;
$\mathbb D$ : l’ensemble des décimaux ;
$\mathbb Q$ : l’ensemble des rationnels ;
$\mathbb R$ : l’ensemble des nombres réels.

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.

Définition

Cardinal d’un ensemble fini :

Soit $E$ un ensemble fini.
On appelle cardinal de $E$ le nombre de ses éléments.

On le note : $\text{Card}( E)$ .
Et : $\text{Card}( E)\in \mathbb N$ .

Exemple

Soit l’ensemble $E=\lbrace 0,\,2,\,6,\,7\rbrace$ .

$\text{Card}( E)=4$ .

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.

Propriété

Soit $A$ et $B$ deux ensembles finis.
Nous avons la formule suivante :

$\text{Card}(A\cup B)= \text{Card}(A) + \text{Card}(B)-\text{Card}(A\cap B)$

Exemple

Prenons un exemple très simple : dans une classe de $30$ élèves, $20$ étudient l’anglais et $15$ l’espagnol, $8$ élèves étudient les deux langues.

En notant $A$ l’ensemble des élèves étudiant l’anglais et $E$ celui des élèves étudiant l’espagnol, on a :

$\begin{aligned} \text{Card}(A\cup E)&=\text{Card}(A)+\text{Card}(E)-\text{Card}(A\cap E) \ &=20+15-8 \ &=27 \end{aligned}$

Ainsi, $27$ élèves étudient soit l’anglais, soit l’espagnol, soit les deux.
On en déduit aussi que $30-27=3$ élèves n’étudient ni l’anglais ni l’espagnol.

Rappelons maintenant la définition d’un sous-ensemble.

Définition

Sous-ensemble :

$F\subset E$ si tout élément de $F$ est aussi un élément de $E$ .

On dit alors que F est un sous-ensemble, ou une partie, de $E$ .

En première, nous avons également abordé la notion de partition d’un ensemble fini, que nous redonnons ici.

Définition

Partition d’un ensemble fini :

Soit $p\in \mathbb N^*$ et $A$ des sous-ensembles non vides d’un ensemble fini $E$ .

On dit que $\mathcal P=\lbrace A$ est une partition de $E$ si et seulement si :

$\begin{cases} A$

Si $A$ est une partie de $E$ , non vide et non égale à $E$ , $A$ et $\bar A$ forment une partition.

Exemple

Soit $E=\lbrace 1,\,2,\,3,\,…,\,9,\,10\rbrace$ l’ensemble des nombres entiers non nuls jusqu’à $10$ , $A$ et $B$ deux parties de $E$ , où $A$ contient les nombres pairs et $B$ les nombres impairs.
On constate que :

$A$ et $B$ ne sont pas vides,
$A\cup B=E$ ,
$A\cap B=\varnothing$ (c’est-à-dire que $A$ et $B$ sont disjoints).
On conclut que $A$ et $B$ forment bien une partition de $E$ .

Nous remarquons aussi que $B = \bar A$ , $A$ et $\bar A$ forment bien une partition de $E$ .

Propriété

Soit $\mathcal P=\lbrace A$ une partition d’un ensemble fini $E$ . Alors on a :

$\text{Card}(E)=\text{Card}(A$

Cette propriété est appelée principe additif ou aussi « lemme des bergers ».

Exemple

Reprenons l’exemple précédent.
Comme $A$ et $B$ forment bien une partition de $E$ , nous avons :

$\begin{aligned} \text{Card}(E)&=\text{Card}(A)+\text{Card}(B) \ &=5+5 \ &=10 \end{aligned}$

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.

Définition

Produit cartésien de deux ensembles :

Le produit cartésien de deux ensembles $E$ et $F$ est noté $E\times F$ et est défini par :

$E\times F=\lbrace(x,\,y) \text{ avec $x\in E$ et $y \in F$}\rbrace$

Il s’agit de l’ensemble des couples dont le premier élément est un élément de $E$ et le second un élément de $F$ .

Attention

Le produit cartésien n’est pas commutatif : $E\times F\neq F\times E$ .

Exemple

Prenons le produit cartésien suivant : $\lbrace0,\,1\rbrace\times \lbrace 1,\,2,\,3\rbrace$ .

C’est l’ensemble des couples $(x,\,y)$ où $x\in\lbrace 0,\,1\rbrace$ et $y\in \lbrace 1,\,2,\,3\rbrace$ . D’où :

$\lbrace 0,\,1\rbrace \times \lbrace 1,\,2,\,3\rbrace=\lbrace (0,\,1),\,(0,\,2),\,(0,\,3),\,(1,\,1),\,(1,\,2),\,(1,\,3)\rbrace$

Nous pouvons voir aussi que, comme dit plus haut, le produit cartésien n’est pas commutatif :

$\lbrace 1,\,2,\,3\rbrace\times\lbrace 0,\,1\rbrace =\lbrace (1,\,0),\,(1,\,1),\,(2,\,0),\,(2,\,1),\,(3,\,0),\,(3,\,1)\rbrace$

Maintenant, généralisons au produit cartésien de plusieurs ensembles.

À retenir

Soit $n\in \mathbb N^*$ .
Le produit cartésien de $n$ ensembles est :

$\begin{aligned} E$

Donnons quelques propriétés du produit cartésien.

Propriété

Soit deux ensembles finis $E$ et $F$ .

Alors, $E\times F$ est fini et :

$\text{Card}(E\times F)=\text{Card}(E)\times \text{Card}(F)$

Soit $n\in \mathbb N^*$ et $E$ des ensembles finis.

On a : $E$ est fini et :

$\text{Card}(E$

Une conséquence immédiate de cette propriété est la suivante :

$\text{Card}(E^n )=\big(\text{Card}(E)\big)^n \footnotesize{\textcolor{#A9A9A9}{\text{ [où$

À retenir

Les éléments d’un produit cartésien de $k$ ensembles sont appelés des $k\text{-listes}$ ou des $k\text{-uplets}$ .

Prenons un exemple simple, pour mieux comprendre.

Exemple

Soit $E=\lbrace0,\,1\rbrace$ .
Soit $F=\lbrace 1,\,2,\,3\rbrace$ .
Soit $G=\lbrace 2,\,3,\,4,\,5\rbrace$ .
Soit $P$ le produit cartésien : $P=E\times F\times G$ .

$(0,\,1,\,2)$ , $(0,\,2,\,3)$ , $(1,\,2,\,2)$ , $(1,\,3,\,5)$ sont des éléments de $P$ , et ce sont des $3\text{-uplets}$ , aussi appelés triplets.

Nous avons aussi :

$\begin{aligned} \text{Card}(P) &= \text{Card}(E\times F\times G) \ &= \text{Card}(E) \times \text{Card}(F) \times \text{Card}(G) \ &= 2\times 3 \times 4 \ &=24 \end{aligned}$

$P$ a donc $24$ éléments.

Et illustrons la dernière propriété grâce aux nombres binaires.

Exemple

Soit $B=\lbrace0,\,1\rbrace$ .
Soit le produit cartésien $P$ tel que :

$\begin{aligned} P&=\underbrace{B\times B\times…\times B}_{n \text{ fois}} \ &=B^n \end{aligned}$

$P$ est l’ensemble des listes de la forme $(x$ où les $n$ éléments $x$ 1,\,x2,\,…,\,xn $x_{1}, x_{2}, \dots, x_{n}$ appartiennent à $\lbrace0,\,1\rbrace$ , c’est-à-dire qu’ils sont égaux à $0$ ou $1$ .

Nous définissons ainsi les nombres binaires de $n$ chiffres.

Nous avons aussi :

$\begin{aligned} \text{Card} (P) &= \text{Card}(B^n) \ &=\big(\text{Card}(B)\big)^n \ &=2^n \end{aligned}$

Nous retrouvons ainsi la formule que vous connaissez sans doute : avec $n\ \text{bits}$ , on peut représenter $2^n$ nombres binaires.

Ainsi, par exemple, avec $1\ \text{mot}=2\ \text{octets}=16\ \text{bits}$ , on peut représenter $2^{16}=65\,536$ valeurs.

Parties, permutations et $k\text{-uplets}$ d’un ensemble fini

Nombre des parties d’un ensemble et applications

Un autre calcul fondamental consiste à compter les parties d’un ensemble $E$ à $n$ éléments.
On remarque pour cela que choisir une partie $A$ de $E$ revient à choisir pour chaque élément de $E$ entre les possibilités : il appartient à $A$ , ou non.

Nous avons la propriété suivante.

Propriété

Soit $E$ un ensemble à $n$ éléments.
Le nombre des parties de $E$ est égal à $2^n$ .

Attention

L’ensemble vide (pour chaque élément de $E$ , on choisit qu’il n’appartient pas à $A$ ) et $E$ lui-même (pour chaque élément de $E$ , on choisit qu’il appartient à $A$ ) sont donc bien des parties de $E$ .

Nous allons ici donner trois applications qui découlent de tout ce que nous venons de voir.

Soit l’ensemble $E=\lbrace 0,\,1\rbrace$ .

Le nombre de parties de $E$ est alors égal à $2^2=4$ .

En effet, les parties de $E$ sont : $\varnothing,\,\lbrace 0 \rbrace,\, \lbrace 1 \rbrace,\, \lbrace 0,\,1 \rbrace$ .
Pour un mot de longueur $n$ sur un alphabet à $2$ éléments, nous avons $2^n$ possibilités.

Prenons un mot de longueur $8$ et uniquement les lettres $\text{A}$ et $\text{B}$ comme choix pour constituer ce mot.

Nous avons alors $2^8=256$ mots possibles.
Dans le cas d’une succession de $n$ épreuves de Bernoulli (épreuve à $2$ issues), nous avons au total $2^n$ issues possibles.

Prenons l’expérience d’une pièce de monnaie non truquée qu’on lance $4$ fois.

Le nombre d’issues au total est alors égal $2^4=16$ .

En utilisant un arbre pour représenter cette succession d’épreuves de Bernoulli, nous aurons une racine et des nœuds à $2$ branches, et le nombre total de chemins possibles sera égal à $2^n$ .

En reprenons la même expérience du lancer de la pièce de monnaie, nous obtenons l’arbre suivant :

Alt mathématiques terminale spécialité factorielle k-uplet permutation combinaison

Nous avons donc $2^4=16$ chemins, et donc issues, possibles.

Remarque : Nous reviendrons longuement, dans la partie « Probabilités », sur les épreuves de Bernoulli.

Nombre de $k \text{-uplets}$ d’éléments d’un ensemble fini

Dans la première partie, nous avons défini les $k \text{-uplets}$ comme éléments d’un produit cartésien de $k$ ensembles.
Nous allons maintenant parler des $k \text{-uplets}$ d’un ensemble fini de $n$ éléments : c’est une liste de $k$ éléments choisis parmi les $n$ éléments de $E$ .

Attention

Ici, l’ordre est important : $k$ éléments choisis rangés dans $2$ ordres différents sont $2$ $k \text{-uplets}$ différents.

Commençons par donner deux propriétés.

Propriété

Soit $n$ et $k$ deux entiers naturels non nuls.

Le nombre de $k \text{-uplets}$ d’un ensemble à $n$ éléments est : $n^k$ .
Le nombre de $k \text{-uplets}$ d’éléments distincts d’un ensemble à $n$ éléments, avec $1\leq k\leq n$ , est :

$n\times (n-1)\times … \times (n-k+1)$

Nous allons maintenant donner deux exemples pour bien comprendre ces propriétés et notamment leur logique.

Exemple

Soit une urne de $10$ boules numérotées de $0$ à $9$ .

Procédons dans un premier temps à un tirage, avec remise, de $3$ boules dont on note le numéro. Cela veut dire que nous pouvons tirer $2$ ou $3$ fois le même numéro.
Cela correspond donc à un $3 \text{-uplet}$ d’un ensemble à $10$ éléments, leur nombre est donc de $10^3=1\,000$ .
Procédons ensuite à un tirage cette fois sans remise de $3$ boules. Ainsi, nous ne pourrons tirer plusieurs fois la même boule.
Cela correspond donc à un $3 \text{-uplet}$ d’éléments distincts d’un ensemble à $10$ éléments, leur nombre est donc de :

$\begin{aligned} \overbrace{10}^n\times \overbrace{9}^{n-1}\times \overbrace{8}^{n-k+1} &=720\ &\footnotesize{\textcolor{#A9A9A9}{\text{ [avec $n=10$,$

Astuce

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 $k \text{-uplets}$ distincts d’un ensemble.

Exemple

Combien peut-on écrire de nombres de $3$ chiffres $2$ à $2$ distincts avec les chiffres $1$ , $2$ , $3$ , $4$ , $5$ et $6$ ?
Nous sommes ici en présence du $3 \text{-uplet}$ d’éléments distincts $(a,\,b,\,c)$ pour former le nombre $abc$ .

Nous avons donc :

pour $a$ , $6$ possibilités (tous les chiffres),
pour $b$ , $5$ possibilités (tous les chiffres, sauf celui utilisé à l’étape précédente, car nous souhaitons des nombres composés de chiffres distincts $2$ à $2$ ),
pour $c$ , $4$ possibilités.
Nous pouvons donc écrire $6\times 5\times 4=120$ nombres de $3$ chiffres $2$ à $2$ distincts avec les chiffres $1$ , $2$ , $3$ , $4$ , $5$ et $6$ .

Nombre de permutations d’un ensemble fini et factorielle

Intéressons-nous maintenant à une nouvelle notation mathématique : $n!$ , afin de calculer le nombre de permutations d’un ensemble fini.

Commençons par définir cette nouvelle notion, que nous pouvons en fait comprendre intuitivement.

Définition

Permutation :

On appelle permutation d’un ensemble $E$ de $n$ éléments tout $n \text{-uplet}$ d’éléments distincts.

Exemple

Soit l’ensemble $E=\lbrace 1,\,2,\,3\rbrace$ .

Alors les $6$ permutations de $E$ sont les suivantes : $(1,\,2,\,3)$ , $(1,\,3,\,2)$ , $(2,\,1,\,3)$ , $(2,\,3,\,1)$ , $(3,\,1,\,2)$ et $(3,\,2,\,1)$ .

Pour calculer le nombre de permutations d’un ensemble fini, nous utilisons la propriété suivante.

Propriété

Le nombre de permutations d’un ensemble à $n$ éléments ( $n\geq 1$ ) est le nombre noté $n!$ (qui se lit : « factorielle de n », ou plus simplement : « factorielle n »), défini de la façon suivante :

$n!=n\times(n-1)\times…\times2\times1$

On convient que : $0!=1$ .
Et l’on a : $(n+1)!=(n+1)\times n!$

Exemple

Calculons la factorielle de $4$ et celle de $5$ .

$\begin{aligned} 4!&=4\times 3\times 2\times 1 \ &= 24 \ \ 5!&=5\times 4! \ &=5\times 24 \ &=120 \end{aligned}$

Combien de mots différents de $5$ lettres peut-on composer avec les lettres $\text{A}$ , $\text{B}$ , $\text{C}$ , $\text{D}$ , $\text{E}$ , sachant qu’une lettre ne peut être utilisée qu’une seule fois ?

Chaque mot correspond tout simplement à une permutation de l’ensemble $\lbrace \text{A},\,\text{B},\,\text{C},\,\text{D},\,\text{E}\rbrace$ , dont le cardinal est égal à $5$ .

Il y a donc $5!=120$ mots possibles.

Reprenons la formule que nous avons vue pour déterminer le nombre de $k \text{-uplets}$ d’éléments distincts d’un ensemble à $n$ éléments, que nous notons ici $N$ (avec $1\leq k\leq n$ ).

Et voyons comment la notion de factorielle nous permet de simplifier le calcul (notamment avec une calculatrice) :

À retenir

$\begin{aligned} N&=n\times(n-1)\times…\times(n-k+1) \ &=\dfrac {n\times(n-1)\times…\times(n-k+1) \times (n-k)!}{(n-k)!} \ &\footnotesize{\textcolor{#A9A9A9}{\text{[la factorielle d’un entier naturel n’est jamais nulle]}}} \ &= \dfrac {n\times(n-1)\times…\times(n-k+1) \times (n-k)\times (n-k-1)\times … \times 2\times 1}{(n-k)!} \ &= \boxed{\dfrac{n!}{(n-k)!}} \end{aligned}$

Combinaisons et triangle de Pascal

Tout d’abord, nous allons définir la combinaison de $k$ éléments d’un ensemble à $n$ éléments. Puis nous introduirons le coefficient binomial, avant de découvrir le triangle de Pascal.

Combinaison et dénombrement

Définition

Combinaison :

Soit $E$ un ensemble fini de $n$ éléments et $k$ un entier tel que $0\leq k\leq n$ .
On appelle combinaison de $k$ éléments de $E$ toute partie de $E$ ayant $k$ éléments.

Attention

Une combinaison est un sous-ensemble.

L’ordre n’est pas important : $\lbrace 0,\,1\rbrace = \lbrace 1,\,0\rbrace$ .

À retenir

Le nombre de combinaisons de $k$ éléments d’un ensemble à $n$ éléments est noté $\binom n k$ (qui se lit « k parmi n »).

Il est appelé coefficient binomial.

Dans un ensemble $E$ à $n$ éléments, il y a :

$n$ parties à $1$ élément,
$\binom n 1 = n$ ;
$1$ seule à $n$ éléments ( $E$ ),
$\binom n n=1$ ;
$1$ seule à $0$ élément ( $\varnothing$ ),
$\binom n 0 = 1$ .

Dans la pratique, le nombre $\binom n k$ permet entre autres de compter le nombre de chemins dans un arbre.

Exemple

Prenons une urne contenant $3$ boules noires et $4$ boules rouges, indiscernables au toucher. L’expérience consiste à prélever dans l’urne $3$ boules successivement et avec remise.

On peut donc modéliser cette expérience à l’aide d’un arbre, en notant $R$ l’événement : « La boule prélevée est rouge ».

Nous pouvons remarquer que $p(R)=\frac 47$ et $p(\bar R)=\frac 37$ , mais nous allons nous intéresser au nombre de chemins de l’arbre, indépendant donc de la valeur de ces probabilités.

Nous considérons $3$ tirages et nous regardons uniquement le nombre de boules rouges obtenues après les $3$ tirages. Nous le notons $k$ .

Et nous cherchons le nombre de chemins de l’arbre où on a $k$ boule(s) rouge(s), peu importe l’ordre.

Alt mathématiques terminale spécialité factorielle k-uplet permutation combinaison

Examinons maintenant les différents cas possibles.

$k=0$ .
Cela revient à chercher les chemins qui mènent à $\red 0$ boule rouge obtenue après les $\green3$ tirages. Il n’y en a que $\blue 1$ :

$\binom {\green 3} {\red 0}=\blue 1$

$k=1$ .
Cela revient à chercher les chemins qui mènent à $1$ boule rouge obtenue après les $3$ tirages. Il y en a $3$ :

$\binom 3 1=3$

$k=2$ .
Cela revient à chercher les chemins qui mènent à $2$ boules rouges obtenues après les $3$ tirages. Il y en a $3$ :

$\binom 3 2=3$

$k=3$ .
Cela revient à chercher les chemins qui mènent à $3$ boules rouges obtenues après les $3$ tirages. Il n’y en a que $1$ :

$\binom 3 3=1$

Astuce

L’exemple que nous venons de prendre nous montre que :

$\begin{aligned} \binom 3 0 &= \binom 3 3 = 1 \ \binom 3 1 &= \binom 3 2 = 3 \end{aligned}$

Et ceci est intuitivement compréhensible dans notre triple tirage :

il y a une seule possibilité qu’aucune boule ne soit rouge (i.e. les $3$ sont noires) comme il y a une seule possibilité que les $3$ boules soient rouges ;
il y a $3$ possibilités que $1$ boule, et $1$ seule, soit rouge, celle-ci pouvant être tirée au premier, ou au deuxième, ou au troisième tirage ;
tirer $1$ boule rouge revient à tirer $3-1=2$ boules noires.

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.

Propriété

Soit $n$ et $k$ deux entiers tels que $0\leq k\leq n$ :

$\begin{aligned} \binom nk &= \dfrac{n\times(n-1)\times…\times(n-k+1)}{k!} \ &=\dfrac{n!}{k!(n-k)!} \end{aligned}$

Soit $n\in \mathbb N$ :

$\displaystyle\sum_{k=0}^n \binom nk= 2^n$

Démontrons cette dernière propriété.

Démonstration

D’après ce que nous avons vu dans la deuxième partie, si l’on prend un ensemble $E$ à $n$ éléments, alors nous avons le nombre des parties $N_\text{parties}$ de $E$ :

$N_\text{parties}=2^n$

Or, pour tout entier $k$ , il y a $\binom nk$ parties de $E$ à $k$ éléments, ce qui nous donne le nombre total des parties de $E$ :

$N$

Nous obtenons ainsi :

$N$

Exemple

Prenons le cas du Loto et plus précisément du tirage de $6$ numéros parmi $49$ . C’est en fait une combinaison de $6$ éléments parmi $49$ .

Le nombre de tirages possibles, c’est-à-dire le coefficient binomial, est donc :

$\begin{aligned} \binom {49}6 &= \dfrac {49\times48\times47\times46\times45\times44}{6\times5\times4\times3\times2\times1} \ &=13\,983\,816 \end{aligned}$

Nous pouvons aussi utiliser la seconde formule donnée :

$\begin{aligned} \binom {49}6 &=\dfrac {49!}{6!\times43!} \ &=13\,983\,816 \end{aligned}$

Remarquons au passage que, si nous ne jouons qu’une seule grille, et donc une seule combinaison, nous avons $1$ chance sur $13\,983\,816$ de gagner !

Attention

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.

Propriété

Soit $n$ un entier naturel non nul et $k$ un entier naturel.

Symétrie :

$\binom nk = \binom n{n-k}\footnotesize{\textcolor{#A9A9A9}{\text{ [où $0\leq k\leq n$]}}}$

Formule de Pascal :

Si de plus $n\geq 2$ et $1\leq k\leq n-1$ , nous avons alors :

$\binom nk = \binom {n-1}k+\binom{n-1}{k-1}\footnotesize{\textcolor{#A9A9A9}{\text{ [où$

Nous allons démontrer la formule de Pascal.

Pour cela, nous allons utiliser une méthode combinatoire.

Démonstration

Soit $E$ un ensemble à $n$ éléments ( $n\geq 2$ ).
Soit $k$ un entier tel que $1\leq k\leq n-1$.
Soit un élément $a\in E$ .

Intéressons-nous à $F$ , l’ensemble de toutes les combinaisons à $k$ éléments de $E$ .
Le cardinal de $F$ est égal au nombre de combinaisons possibles de $k$ éléments parmi les $n$ éléments de $E$ :

$\text{Card}(F)=\binom nk$

Parmi les combinaisons, nous trouvons celles qui contiennent $a$ et celles qui ne contiennent pas $a$ .

Soit $G$ l’ensemble des combinaisons à $k$ éléments ne contenant pas $a$ ( $G$ n’est pas vide car, dans $E$ , il y a au moins un autre élément que $a$ ).

Le cardinal de $G$ est égal au nombre de combinaisons possibles de $k$ éléments parmi les $n-1$ éléments de $E$ distincts de $a$ :

$\text{Card}(G)=\binom {n-1}k$

Soit $H$ l’ensemble des combinaisons à $k$ éléments contenant $a$ .
On les obtient en ajoutant l’élément $a$ aux parties à $k-1$ éléments parmi les $n-1$ éléments de $E$ distincts de $a$ .

Le cardinal de $H$ est égal au nombre de combinaisons possibles de $k-1$ éléments parmi les $n-1$ éléments de $E$ distincts de $a$ :

$\text{Card}(H)=\binom {n-1}{k-1}$

Nous voyons que $G$ et $H$ ne sont pas vides, que $G\cup H=F$ et que $G\cap H=\varnothing$ .

$G$ et $H$ forment une partition de $F$ .

Ainsi, d’après la formule vue dans la première partie :

$\text{Card}(F)= \text{Card}(G) + \text{Card}(H)$

Nous en déduisons finalement :

$\binom nk = \binom {n-1}k +\binom {n-1}{k-1}$

Nous pouvons maintenant passer à la construction du triangle de Pascal.

À retenir

Si nous plaçons les coefficients binomiaux dans un tableau avec les $n$ en ligne et les $k$ en colonne, nous obtenons un triangle et la formule de Pascal permet de calculer les coefficients de la ligne $n+1$ connaissant ceux de la ligne $n$ .

On a donc une formule de récurrence pour calculer les coefficients binomiaux et on peut tous les calculer de proche en proche.

Astuce

Nous plaçons dans un premier temps les coefficients suivants (selon les propriétés vues plus haut) :

$\binom n0=1$ ;
$\binom nn=1$ ;
$\binom n1=n$ .

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’à $n=3$ .

	$k=0$	$k=1$	$k=2$	$k=3$
$n=0$	$\footnotesize \displaystyle\binom 00=1$
$n=1$	$\footnotesize \blue{\displaystyle\binom 10}=1$	$\footnotesize \green{\displaystyle\binom 11}=n=1$
$n=2$	$\footnotesize \displaystyle\purple{\binom 20}=1$	$\begin{aligned} \footnotesize {\red{\binom 21}}&\footnotesize{=\green{\binom11} + \blue{\binom 10}} \ &\footnotesize{=n= 2} \end{aligned}$	$\footnotesize \displaystyle\pink{\binom 22}=1$
$n=3$	$\footnotesize \displaystyle\binom 30=1$	$\begin{aligned} \footnotesize {\binom 31}&\footnotesize{=\red{\binom21} + \purple{\binom 20}} \ &\footnotesize{=n= 3} \end{aligned}$	$\begin{aligned} \footnotesize {\binom 32}&\footnotesize{=\pink{\binom22} + \red{\binom 21}} \ &\footnotesize{=\binom 31=3} \end{aligned}$	$\footnotesize \displaystyle\binom 33=1$

Maintenant que nous avons compris le principe, remplissons simplement le triangle de Pascal, jusqu’à $n=9$ .

N’hésitez pas à ajouter vous-mêmes quelques lignes, pour vous familiariser avec le calcul des coefficients binomiaux.

$^{k\,\rightarrow}_{n\,\downarrow}$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
$0$	$1$
$1$	$1$	$1$
$2$	$1$	$2$	$1$
$3$	$1$	$3$	$3$	$1$
$4$	$1$	$4$	$6$	$4$	$1$
$5$	$1$	$5$	$10$	$10$	$5$	$1$
$6$	$1$	$6$	$15$	$20$	$15$	$6$	$1$
$7$	$1$	$7$	$21$	$35$	$35$	$21$	$7$	$1$
$8$	$1$	$8$	$28$	$56$	$70$	$56$	$28$	$8$	$1$
$9$	$1$	$9$	$36$	$84$	$126$	$126$	$84$	$36$	$9$	$1$

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.

Cours : Factorielle, arrangement, permutation et combinaison

Principe additif et multiplicatif

Principe additif

Principe multiplicatif

Parties, permutations et k-upletsk\text{-uplets}k-uplets d’un ensemble fini

Nombre des parties d’un ensemble et applications

Nombre de k-upletsk \text{-uplets}k-uplets d’éléments d’un ensemble fini

Nombre de permutations d’un ensemble fini et factorielle

Combinaisons et triangle de Pascal

Combinaison et dénombrement

Coefficient binomial et triangle de Pascal

Parties, permutations et $k\text{-uplets}$ d’un ensemble fini

Nombre de $k \text{-uplets}$ d’éléments d’un ensemble fini