Médaille
N°1 pour apprendre & réviser du collège au lycée.

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 :

  • N\mathbb N : l’ensemble des entiers naturels ;
  • Z\mathbb Z : l’ensemble des entiers relatifs ;
  • D\mathbb D : l’ensemble des décimaux ;
  • Q\mathbb Q : l’ensemble des rationnels ;
  • R\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.

bannière definition

Définition

Cardinal d’un ensemble fini :

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

  • On le note : Card(E)\text{Card}( E).
  • Et : Card(E)N\text{Card}( E)\in \mathbb N.
bannière exemple

Exemple

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

  • Card(E)=4\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.

bannière propriete

Propriété

Soit AA et BB deux ensembles finis.
Nous avons la formule suivante :

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

bannière exemple

Exemple

Prenons un exemple très simple : dans une classe de 3030 élèves, 2020 étudient l’anglais et 1515 l’espagnol, 88 élèves étudient les deux langues.

  • En notant AA l’ensemble des élèves étudiant l’anglais et EE celui des élèves étudiant l’espagnol, on a :

Card(AE)=Card(A)+Card(E)Card(AE)=20+158=27\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, 2727 élèves étudient soit l’anglais, soit l’espagnol, soit les deux.
On en déduit aussi que 3027=330-27=3 élèves n’étudient ni l’anglais ni l’espagnol.

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

bannière definition

Définition

Sous-ensemble :

FEF\subset E si tout élément de FF est aussi un élément de EE.

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

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

bannière definition

Définition

Partition d’un ensemble fini :

Soit pNp\in \mathbb N^* et A1,A2,,ApA1,\,A2,\,…,\,A_p des sous-ensembles non vides d’un ensemble fini EE.

  • On dit que P={A1,A2,,Ap}\mathcal P=\lbrace A1,\,A2,\,…,\,A_p\rbrace est une partition de EE si et seulement si :

{A1A2Ap=EA1,A2,,Ap sont disjoints 2 aˋ 2\begin{cases} A1\cup A2 \cup…∪Ap=E \ A1,\,A2,\,…,\,Ap \text{ sont disjoints 22 à 22} \end{cases}

Si AA est une partie de EE, non vide et non égale à EE, AA et Aˉ\bar A forment une partition.

bannière exemple

Exemple

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

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

Nous remarquons aussi que B=AˉB = \bar A, AA et Aˉ\bar A forment bien une partition de EE.

bannière propriete

Propriété

Soit P={A1,A2,,Ap}\mathcal P=\lbrace A1,\,A2,\,…,\,A_p \rbrace une partition d’un ensemble fini EE. Alors on a :

Card(E)=Card(A1)+Card(A2)++Card(Ap)\text{Card}(E)=\text{Card}(A1)+\text{Card}(A2 )+…+\text{Card}(A_p)

  • Cette propriété est appelée principe additif ou aussi « lemme des bergers ».
bannière exemple

Exemple

Reprenons l’exemple précédent.
Comme AA et BB forment bien une partition de EE, nous avons :

Card(E)=Card(A)+Card(B)=5+5=10\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.

bannière definition

Définition

Produit cartésien de deux ensembles :

Le produit cartésien de deux ensembles EE et FF est noté E×FE\times F et est défini par :

E×F={(x,y) avec xE et yF}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 EE et le second un élément de FF.
bannière attention

Attention

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

bannière exemple

Exemple

Prenons le produit cartésien suivant : {0,1}×{1,2,3}\lbrace0,\,1\rbrace\times \lbrace 1,\,2,\,3\rbrace.

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

{0,1}×{1,2,3}={(0,1),(0,2),(0,3),(1,1),(1,2),(1,3)}\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 :

{1,2,3}×{0,1}={(1,0),(1,1),(2,0),(2,1),(3,0),(3,1)}\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.

bannière à retenir

À retenir

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

E1×E2××En={(x1,x2,,xn) avec, pour tout i{1,2,,n} : xiEi}\begin{aligned} E1\times E2\times … \times En=&\big\lbrace(x1,\,x2,\,…,\,xn) \ &\text{ avec, pour tout $i\in\lbrace1,\,2,\,…,\,n\rbrace$ : $x_i\in E_i$}\big\rbrace \end{aligned}

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

bannière propriete

Propriété

  • Soit deux ensembles finis EE et FF.

Alors, E×FE\times F est fini et :

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

  • Soit nNn\in \mathbb N^* et E1,,EnE1,\,…,\,En des ensembles finis.

On a : E1××EnE1\times … \times En est fini et :

Card(E1××En)=Card(E1)××Card(En)\text{Card}(E1\times … \times En)=\text{Card}(E1 )\times … \times \text{Card}(En)

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

Card(En)=(Card(E))n [ouˋ E est un ensemble fini]\text{Card}(E^n )=\big(\text{Card}(E)\big)^n \footnotesize{\textcolor{#A9A9A9}{\text{ [où EE est un ensemble fini]}}}

bannière à retenir

À retenir

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

Prenons un exemple simple, pour mieux comprendre.

bannière exemple

Exemple

Soit E={0,1}E=\lbrace0,\,1\rbrace.
Soit F={1,2,3}F=\lbrace 1,\,2,\,3\rbrace.
Soit G={2,3,4,5}G=\lbrace 2,\,3,\,4,\,5\rbrace.
Soit PP le produit cartésien : P=E×F×GP=E\times F\times G.

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

Nous avons aussi :

Card(P)=Card(E×F×G)=Card(E)×Card(F)×Card(G)=2×3×4=24\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}

  • PP a donc 2424 éléments.

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

bannière exemple

Exemple

Soit B={0,1}B=\lbrace0,\,1\rbrace.
Soit le produit cartésien PP tel que :

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

PP est l’ensemble des listes de la forme (x1,x2,,xn)(x1,\,x2,\,…,\,xn) où les nn éléments x1,x2,,xnx1,\,x2,\,…,\,xn appartiennent à {0,1}\lbrace0,\,1\rbrace, c’est-à-dire qu’ils sont égaux à 00 ou 11.

  • Nous définissons ainsi les nombres binaires de nn chiffres.

Nous avons aussi :

Card(P)=Card(Bn)=(Card(B))n=2n\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 bitsn\ \text{bits}, on peut représenter 2n2^n nombres binaires.

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

Parties, permutations et k-upletsk\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 EE à nn éléments.
On remarque pour cela que choisir une partie AA de EE revient à choisir pour chaque élément de EE entre les possibilités : il appartient à AA, ou non.

  • Nous avons la propriété suivante.
bannière propriete

Propriété

Soit EE un ensemble à nn éléments.
Le nombre des parties de EE est égal à 2n2^n.

bannière attention

Attention

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

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

  • Soit l’ensemble E={0,1}E=\lbrace 0,\,1\rbrace.

Le nombre de parties de EE est alors égal à 22=42^2=4.

  • En effet, les parties de EE sont : ,{0},{1},{0,1}\varnothing,\,\lbrace 0 \rbrace,\, \lbrace 1 \rbrace,\, \lbrace 0,\,1 \rbrace.
  • Pour un mot de longueur nn sur un alphabet à 22 éléments, nous avons 2n2^n possibilités.

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

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

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

  • Le nombre d’issues au total est alors égal 24=162^4=16.

En utilisant un arbre pour représenter cette succession d’épreuves de Bernoulli, nous aurons une racine et des nœuds à 22 branches, et le nombre total de chemins possibles sera égal à 2n2^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 24=162^4=16 chemins, et donc issues, possibles.

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

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

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

bannière attention

Attention

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

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

bannière propriete

Propriété

Soit nn et kk deux entiers naturels non nuls.

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

n×(n1)××(nk+1)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.

bannière exemple

Exemple

Soit une urne de 1010 boules numérotées de 00 à 99.

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

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

bannière astuce

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

bannière exemple

Exemple

Combien peut-on écrire de nombres de 33 chiffres 22 à 22 distincts avec les chiffres 11, 22 , 33, 44, 55 et 66 ?
Nous sommes ici en présence du 3-uplet3 \text{-uplet} d’éléments distincts (a,b,c)(a,\,b,\,c) pour former le nombre abcabc.

Nous avons donc :

  • pour aa, 66 possibilités (tous les chiffres),
  • pour bb, 55 possibilités (tous les chiffres, sauf celui utilisé à l’étape précédente, car nous souhaitons des nombres composés de chiffres distincts 22 à 22),
  • pour cc, 44 possibilités.
  • Nous pouvons donc écrire 6×5×4=1206\times 5\times 4=120 nombres de 33 chiffres 22 à 22 distincts avec les chiffres 11, 22 , 33, 44, 55 et 66.

Nombre de permutations d’un ensemble fini et factorielle

Intéressons-nous maintenant à une nouvelle notation mathématique : n!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.

bannière definition

Définition

Permutation :

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

bannière exemple

Exemple

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

  • Alors les 66 permutations de EE sont les suivantes : (1,2,3)(1,\,2,\,3), (1,3,2)(1,\,3,\,2), (2,1,3)(2,\,1,\,3), (2,3,1)(2,\,3,\,1), (3,1,2)(3,\,1,\,2) et (3,2,1)(3,\,2,\,1).

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

bannière propriete

Propriété

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

n!=n×(n1)××2×1n!=n\times(n-1)\times…\times2\times1

  • On convient que : 0!=10!=1.
  • Et l’on a : (n+1)!=(n+1)×n!(n+1)!=(n+1)\times n!
bannière exemple

Exemple

  • Calculons la factorielle de 44 et celle de 55.

4!=4×3×2×1=245!=5×4!=5×24=120\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 55 lettres peut-on composer avec les lettres A\text{A}, B\text{B}, C\text{C}, D\text{D}, E\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 {A,B,C,D,E}\lbrace \text{A},\,\text{B},\,\text{C},\,\text{D},\,\text{E}\rbrace, dont le cardinal est égal à 55.

  • Il y a donc 5!=1205!=120 mots possibles.

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

  • Et voyons comment la notion de factorielle nous permet de simplifier le calcul (notamment avec une calculatrice) :
bannière à retenir

À retenir

N=n×(n1)××(nk+1)=n×(n1)××(nk+1)×(nk)!(nk)![la factorielle d’un entier naturel n’est jamais nulle]=n×(n1)××(nk+1)×(nk)×(nk1)××2×1(nk)!=n!(nk)!\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 kk éléments d’un ensemble à nn éléments. Puis nous introduirons le coefficient binomial, avant de découvrir le triangle de Pascal.

Combinaison et dénombrement

bannière definition

Définition

Combinaison :

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

bannière attention

Attention

Une combinaison est un sous-ensemble.

  • L’ordre n’est pas important : {0,1}={1,0}\lbrace 0,\,1\rbrace = \lbrace 1,\,0\rbrace.
bannière à retenir

À retenir

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

  • Il est appelé coefficient binomial.

Dans un ensemble EE à nn éléments, il y a :

  • nn parties à 11 élément,
  • (n1)=n\binom n 1 = n ;
  • 11 seule à nn éléments (EE),
  • (nn)=1\binom n n=1 ;
  • 11 seule à 00 élément (\varnothing),
  • (n0)=1\binom n 0 = 1.

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

bannière exemple

Exemple

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

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

Nous pouvons remarquer que p(R)=47p(R)=\frac 47 et p(Rˉ)=37p(\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 33 tirages et nous regardons uniquement le nombre de boules rouges obtenues après les 33 tirages. Nous le notons kk.

  • Et nous cherchons le nombre de chemins de l’arbre où on a kk 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=0k=0.
  • Cela revient à chercher les chemins qui mènent à 0\red 0 boule rouge obtenue après les 3\green3 tirages. Il n’y en a que 1\blue 1 :

(30)=1\binom {\green 3} {\red 0}=\blue 1

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

(31)=3\binom 3 1=3

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

(32)=3\binom 3 2=3

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

(33)=1\binom 3 3=1

bannière astuce

Astuce

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

(30)=(33)=1(31)=(32)=3\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 33 sont noires) comme il y a une seule possibilité que les 33 boules soient rouges ;
  • il y a 33 possibilités que 11 boule, et 11 seule, soit rouge, celle-ci pouvant être tirée au premier, ou au deuxième, ou au troisième tirage ;
  • tirer 11 boule rouge revient à tirer 31=23-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.

bannière propriete

Propriété

  • Soit nn et kk deux entiers tels que 0kn0\leq k\leq n :

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

  • Soit nNn\in \mathbb N :

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

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

bannière demonstration

Démonstration

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

Nparties=2nN_\text{parties}=2^n

  • Or, pour tout entier kk, il y a (nk)\binom nk parties de EE à kk éléments, ce qui nous donne le nombre total des parties de EE :

Nparties=k=0n(nk)N\text{parties}=\displaystyle\sum{k=0}^n \binom nk

  • Nous obtenons ainsi :

Nparties=k=0n(nk)=2nN\text{parties}=\boxed{\displaystyle\sum{k=0}^n \binom nk=2^n}

bannière exemple

Exemple

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

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

(496)=49×48×47×46×45×446×5×4×3×2×1=13983816\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 :

(496)=49!6!×43!=13983816\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 11 chance sur 1398381613\,983\,816 de gagner !

bannière attention

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.

bannière propriete

Propriété

Soit nn un entier naturel non nul et kk un entier naturel.

  • Symétrie :

(nk)=(nnk) [ouˋ 0kn]\binom nk = \binom n{n-k}\footnotesize{\textcolor{#A9A9A9}{\text{ [où $0\leq k\leq n$]}}}

  • Formule de Pascal :

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

(nk)=(n1k)+(n1k1) [ouˋ 1kn1]\binom nk = \binom {n-1}k+\binom{n-1}{k-1}\footnotesize{\textcolor{#A9A9A9}{\text{ [où 1kn11\leq k\leq n-1]}}}

Nous allons démontrer la formule de Pascal.

  • Pour cela, nous allons utiliser une méthode combinatoire.
bannière demonstration

Démonstration

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

  • Intéressons-nous à FF, l’ensemble de toutes les combinaisons à kk éléments de EE.
  • Le cardinal de FF est égal au nombre de combinaisons possibles de kk éléments parmi les nn éléments de EE :

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

  • Parmi les combinaisons, nous trouvons celles qui contiennent aa et celles qui ne contiennent pas aa.

Soit GG l’ensemble des combinaisons à kk éléments ne contenant pas aa (GG n’est pas vide car, dans EE, il y a au moins un autre élément que aa).

  • Le cardinal de GG est égal au nombre de combinaisons possibles de kk éléments parmi les n1n-1 éléments de EE distincts de aa :

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

Soit HH l’ensemble des combinaisons à kk éléments contenant aa.
On les obtient en ajoutant l’élément aa aux parties à k1k-1 éléments parmi les n1n-1 éléments de EE distincts de aa.

  • Le cardinal de HH est égal au nombre de combinaisons possibles de k1k-1 éléments parmi les n1n-1 éléments de $E$ distincts de aa :

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

  • Nous voyons que GG et HH ne sont pas vides, que GH=FG\cup H=F et que GH=G\cap H=\varnothing.

GG et HH forment une partition de FF.

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

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

  • Nous en déduisons finalement :

(nk)=(n1k)+(n1k1)\binom nk = \binom {n-1}k +\binom {n-1}{k-1}

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

bannière à retenir

À retenir

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

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

Astuce

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

  • (n0)=1\binom n0=1 ;
  • (nn)=1\binom nn=1 ;
  • (n1)=n\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=3n=3.

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

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

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

nk^{k\,\rightarrow}_{n\,\downarrow} 00 11 22 33 44 55 66 77 88 99
00 11
11 11 11
$2$ 11 $2$ 11
33 11 33 33 11
44 11 44 66 44 11
55 11 55 1010 1010 55 11
66 11 66 1515 2020 1515 66 11
77 11 77 2121 3535 3535 2121 77 11
88 11 88 2828 5656 7070 5656 2828 88 11
99 11 99 3636 8484 126126 126126 8484 3636 99 11

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.