Combinatoire et dénombrement

Accueil » Cours et exercices » Terminale générale » Combinatoire et dénombrement

Cardinal d’ensembles

Union d’ensembles

Un ensemble \(A\) est une collection d’objets distincts que l’on appelle ses éléments.

  • On dit qu’un objet \(x\) appartint à \(A\) si \(x\) est un élément de \(A\). On note \(x\in A\).
  • On dit qu’un ensemble \(B\) est inclus dans \(A\) si tout élément de \(B\) est aussi un élément de \(A\). On note \(B \subset A\).

Exemple : On considère l’ensemble \(A=\{1;2;7;9;44\}\). On a \(1 \in A\), \(3 \not\in A\). L’ensemble \(B=\{2;9\}\) est inclus dans \(A\) : on a \(B\subset A\). En revanche, l’ensemble \(C=\{1;2;4;7\}\) n’est pas inclus dans \(A\) puisque \(4\in C\) alors que \(4\not\in A\).

Par ailleurs, il ne faut pas confondre \(2\) et \(\{2\}\) : \(2\) désigné l’élément alors que \(\{2\}\) désigne l’ensemble qui contient un seul élément, 2. On a ainsi \(2 \in A\) et \(\{2\} \subset A\).

Soit \(A\) un ensemble ayant un nombre fini d’éléments. On appelle Cardinal de \(A\), noté \(\mathrm{Card}(A)\), \(\sharp A\) ou \(|A|\) le nombre d’éléments de \(A\).

Exemple : Le cardinal de l’ensemble \(A=\{1;3;\pi;5;\sqrt{2}\}\) est 5.

Soit \(A\) et \(B\) deux ensembles

  • L’union de \(A\) et \(B\) est l’ensemble noté \(A\cup B\) qui contient tous les éléments qui sont au moins dans l’ensemble \(A\) ou dans l’ensemble \(B\).
  • L’intersection de \(A\) et \(B\) est l’ensemble noté \(A\cap B\) qui contient les éléments qui sont à la fois dans \(A\) et dans \(B\).
  • Deux ensembles sont disjoints s’ils n’ont aucun élément en commun, autrement dit, \(A\cap B = \varnothing\).

Exemple : On considère les ensemble \(A=\{1;3;4;5;8\}\) et \(B=\{1;2;4;6;7\}\). Alors \(A\cup B = \{1;2;4;5;6;7;8\}\) et \(A\cap B = \{ 1;4\}\). En particulier, les ensembles \(A\) et \(B\) ne sont pas disjoints.

Soit \(n\) un entier naturel non nul et \(A_1\), \(A_2\), …, \(A_n\) des ensembles deux à deux disjoints.
\[ \mathrm{Card}(A_1 \cup A_2 \cup \ldots \cup A_n)= \mathrm{Card}(A_1) + \mathrm{Card}(A_2)+\ldots + \mathrm{Card}(A_n)= \sum_{i=1}^n \mathrm{Card}(A_1)\]

Produit cartésien

L’essentiel : Soit \(A\) et \(B\) deux ensembles.

  • On appelle produit cartésien de \(A\) et \(B\), noté \(A \times B\) (\(A\) « croix » \(B\)), l’ensemble composé des couples \((a;b)\) avec \(a \in A\) et \(b \in B\).
  • Le produit cartésien \(A\times A\) est également noté \(A^2\).

Exemple : On considère les ensembles \(A=\{2;5;9\};\) et \(B=\{3;5\}\).

  • Les éléments de \(A \times B\) sont \((2;3)\), \((2;5)\), \((5;3)\), \((5;5)\), \((9;3)\) et \((9;5)\).
  • Les éléments de \(B \times A\) sont \((3:2)\), \((3;5)\), \((3;9)\), \((5;2)\), \((5;5)\), \((5;9)\).
  • Les éléments de \(B^2\) sont \((3;3)\), \((3;5)\), \((5;3)\) et \((5;5)\).

La notion de produit cartésien s’étend naturellement à plus de deux ensembles.

  • Soit \(n\) un entier naturel supérieur ou égal à 2. le produit cartésien de \(n\) ensembles \(A_1\), \(A_2\), …, \(A_n\) est l’ensemble des \(n\)-uplets \((a_1;a_2;\ldots;a_n)\) avec \(a_1 \in A_1\), \(a_2 \in A_2\), … \( a_n \in A_n\).
  • Le produit cartésien \(A \times A \times … \times A\) où \(A\) apparaît \(n\) fois est noté \(A^n\). Ses éléments sont appelés les \(n\)-uplets de \(A\).

Exemple : On considère les ensembles \(A=\{1;2;4\}\), \(B=\{3;7;14\}\) et \(C=\{1;3\}\).

  • \((1;7;3) \in A \times B \times C\) puisque \(1 \in A\), \(7 \in B\) et \(3 \in C\).
  • \((3;7;7;3;14) \in B^5\) puisque \(3\), \(7\) et 14 sont dans l’ensemble \(B\).

La notion de produit cartésien s’étend également à des ensembles infinis. Par exemple, \((1; \pi) \in \mathbb{N} \times \mathbb{R}\).

Le terme de produit cartésien doit son nom au mathématicien René Descartes. Celui-ci est en effet le premier à avoir décrit les points du plan à l’aide de leurs coordonnées dans un repère : un point est ainsi décrit par un couple de réels \((x;y)\) de \(\mathbb{R} \times \mathbb{R}\), ou tout simplement \(\mathbb{R}^2\). De la même manière, les points de l’espace sont décrits par un triplet \((x;y;z) \in \mathbb{R}^3\).

Soit \(A\) et \(B\) des ensembles finis.

  • \(\mathrm{Card} (A \times B)=\mathrm{Card}(A) \times \mathrm{Card} (B)\).
  • Plus généralement, soit \(n\) un entier naturel, \(A_1\), \(A_2\), …, \(A_n\) des ensembles finis. \[\mathrm{Card}(A_1 \times A_2 \times \ldots \times A_n)=\mathrm{Card}(a_1) \times \mathrm{Card}(A_2) \times \ldots \times \mathrm{Card}(A_n)\]
  • En particulier, \(\mathrm{Card}(A^n)=[\mathrm{Card}(A)]^n\).

On traduit ainsi le fait que si l’on souhaite construire un élément \((a_1;a_2;\ldots;a_n)\) de l’ensemble \(A_1 \times A_2 \times \ldots \times A_n\), on a \(\mathrm{Card}(A_1)\) choix pour \(a_1\), \(\mathrm{Card}(A_2)\) choix pour \(a_2\) etc.

Exemple : On reprend les ensembles \(A=\{1;2;4\}\), \(B=\{3;7;14\}\) et \(C=\{1;3\}\).

  • \(\mathrm{Card}(A \times B)= 3 \times 3 = 9\)
  • \(\mathrm{Card}(A \times B \times C) = 3 \times 3 \times 2 = 18\)
  • \(\mathrm{Card}(A^4)=3^4=81\)
  • \(\mathrm{Card}(C^{10})=2^{10}=1024\)

Le produit cartésien est utilisé pour dénombrer des situations où l’ordre des symboles (chiffres, lettres, signes…) est important et où ces symboles peuvent être utilisés plusieurs fois.

Exemple : A l’entrée d’un bâtiment est installé un digicode. Pour composer le code, on utilise 4 chiffres compris entre 1 et 6 suivis de deux lettres parmi les lettres A, B, C et D. Un chiffre ou une lettre peuvent être utilisés plusieurs fois. Combien de codes sont possibles ?

  • Pour les chiffres, on a 6 choix possibles pour le prmier, 6 pour le deuxième, 6 pour le troisième et 6 pour le quatrième, soit \(6\times 6 \times 6 \times 6 = 6^4 = 1296\) possibilités
  • Pour les lettres, il y a 4 choix pour la première et 4 pour la seconde soit \(4 \times 4 = 16\) possibilités.
  • En tout, il y a donc \(1296 \times 16 = 20736\) digicodes possibles

Formellement, si l’on note \(A_1=\{1;2;3;4;5;6\}\) et \(A_2=\{A;B;C;D\}\), un digicode est un élément de \(A_1^4 \times A_2 ^2\). Son cardinal est donc \(\mathrm{Card}(A_1)^4 \times \mathrm{Card}(A_2)^2 = 6^4 \times 4^2 = 20736\).

Arrangements et permutations

Soit \(n\) un entier naturel non nul. On note \(n!\) (factorielle de \(n\)) le produit de tous les entiers de 1 à \(n\) \[n!=n\times (n-1) \times \ldots \times 2 \times 1\]

Par ailleurs, on convient que \(0!=1\).

Exemple : \(5!=5\times 4 \times 3 \times 2 \times 1 = 120 \quad ;\quad \dfrac{8!}{6!}=\dfrac{8 \times 7 \times 6!}{6!}=8\times 7 = 56\)

Soit \(A\) un ensemble fini de cardinal \(n\) et \(k\) un entier inférieur ou égal à \(n\). Un \(k\)-arrangement de \(A\) est un \(k\)-uplet d’éléments distincts de \(A\).
Lorsque \(k=n\), on parle de permutation de \(A\).

Exemple : On considère l’ensemble \(A=\{1;3;4;5;7;10\}\).

  • \((7;10;3)\) est un 3-arrangement de \(A\).
  • \((10;5;4;1)\) est un 4-arrangement de \(A\).
  • En revanche, \((7;10;1;7)\) n’est pas un arrangement de \(A\) car l’élément \(7\) y apparaît deux fois.
  • \((3;7;4;5;1;10)\) est par ailleurs une permutation de \(A\) puisque tous les éléments de \(A\) y apparaissent.

Soit \(A\) un ensemble fini de cardinal \(n\) et \(k\) un entier inférieur ou égal à \(n\). Le nombre de \(k\)-arrangements de \(A\) vaut \(\dfrac{n!}{(n-k)!}\).
En particulier, le nombre de permutation de \(A\) vaut \(n!\).

Démonstration : Pour construire un \(k\)-uplet d’éléments distincts de \(A\), on a

  • \(n\) choix pour le premier élément
  • \(n-1\) choix pour le deuxième
  • \(n-(k+1)\) pour le \(k\)-ième

Le nombre de \(k\) arrangements de \(A\) vaut donc \(n \times (n-1) \times \ldots \times n-(k+1)\), ce que l’on peut réécrire en
\[ n \times (n-1) \times \ldots \times n-(k+1) \times \dfrac{(n-k) \times (n-k-1)\times \ldots \times 2 \times 1}{(n-k) \times (n-k-1)\times \ldots \times 2 \times 1}=n \times (n-1) \times \ldots \times n-(k+1) \times \dfrac{(n-k)!}{(n-k)!}\]
d’où
\[n \times (n-1) \times \ldots \times n-(k+1) \times \dfrac{(n-k) \times (n-k-1)\times \ldots \times 2 \times 1}{(n-k) \times (n-k-1)\times \ldots \times 2 \times 1}=\dfrac{n!}{(n-k)!}\]

Exemple : On considère l’ensemble \(A=\{1;3;4;5;7;9;11\}\), de cardinal 7. Le nombre de \(3\)-arrangements de \(A\) vaut \(9 \times 8 \times 7 = 504\).

Les arrangements sont utilisés pour dénombres des situations où l’ordre des objets (chiffres, nombres, lettres, signes,…) est important mais où chaque objet ne peut être utilisé qu’une seule fois.

Exemple : Une cours hippique réunit 8 jockeys et leurs chevaux. Le « quarté dans l’ordre » est un pari qui consiste à deviner les quatre premiers chevaux arrivés dans l’ordre. Combien de paris différents est-il possible de réaliser ?

  • On a 8 choix pour le premier cheval arrivé
  • Il reste 7 choix pour le deuxième, 6 pour le troisième et 5 pour le quatrième.
  • Le nombre total de paris est donc \(8 \times 7 \times 6 \times 5 = 1680\).

Formellement, si on nomme \(A\) l’ensemble des chevaux de la course, un quarté dans l’ordre est un 4-arrangement de \(A\).

Prenons au hasard et de manière uniforme 23 personnes nées en 2019. Pour simplifier, on suppose que leur date de naissance est également uniforme sur l’année. Quelle est la probabilité que deux personnes parmi ces 23 soient nées le même jour ?
Nous allons plutôt, pour répondre à cette question, nous intéresser à l’événement complémentaire : quelle est la probabilité que tout le monde soit né un jour différent ?
Puisque les personnes sont choisies au hasard et que la date de naissance est supposée uniforme, il suffit d’utiliser la formule \(\dfrac{\text{Nombre de cas favorables}}{\text{Nombre de cas total}}\).

  • Un cas est ici favorable lorsque les dates de naissances des 23 personnes sont différentes. Le nombre de cas favorables est donc le nombre de 23-arrangements de l’ensemble des jours (365 éléments). Il y en a \(\dfrac{365!}{(365-23)!}\) soit \(\dfrac{365!}{342!}\).
  • Le nombre de cas total est un 23-uplet de l’ensemble des jours : chaque personne a une date de naissance, sans restriction. Il y en a donc \(365^{23}\).

Ainsi, la probabilité que tout le monde soit né un jour différent vaut \(\dfrac{365!}{342! \times 365^{23}}\simeq 0.4927\). En passant au complémentaire, il y a donc \(50,73\%\) de chances que, dans un groupe de 23 personnes prises au hasard, au moins deux personnes soient nées le même jour !

Combinaisons d’un ensemble fini

Une partie ou combinaison d’un ensemble fini \(A\) est un ensemble inclus dans \(A\). L’ensemble des parties de \(A\) est noté \(\mathcal{P}(A)\).

Si \(A\) est de cardinal \(n\), le nombre de parties de \(A\) est \(2^n\).

Démonstration : Nous allons montrer qu’il y a autant de parties de \(A\) que de \(n\)-uplets de l’ensemble \(\{0;1\}^n\). Puisque \(\{0;1\}\) possède 2 éléments, le cardinal de \(\{0;1\}^n\) vaut donc \(2^n\).

Pour cela, à chaque partie de \(A\), on fait correspondre un élément de \(\{0;1\}^n\) de telle sorte que deux parties différentes de \(A\) sont associés à deux \(n\)-uplets différents de \(\{0;1\}\). On dit qu’on réalise une bijection entre \(\mathcal{P}(A)\) et \(\{0;1\}^n\).

L’idée : Pour chaque élément de \(A\), on a deux choix pour construire une partie de \(A\) : soit cet élément appartient à la partie que l’on construit, soit il ne lui appartient pas. On a donc

  • 2 choix pour le premier élément de \(A\)
  • 2 choix pour le deuxième élément…
  • 2 choix pour le \(n\)-ième élément de \(A\).

Ainsi, le cardinal de \(\mathcal{P}(A)\) vaut \(2\times 2 \times \ldots \times 2 = 2^n\).

De manière formelle : Notons \(a_1\), \(a_2\) , …, \(a_n\) les éléments de \(A\).
Soit \(B\) une partie de \(A\). On construit un \(n\)-uplet \((b_0;b_1;…;b_n)\) de \(\{0;1\}\) comme suit : pour tout entier naturel \(i\) entre 1 et \(n\).

  • \(b_i=1\) si \(a_i \in B\),
  • \(b_1=0\) sinon.

Chaque partie de \(A\) est ainsi associé de manière unique à un \(n\)-uplet de \(\{0;1\}\) et réciproquement. Les cardinaux de \(\mathcal{P}(A)\) et \(\{0;1\}^n\) sont donc égaux.

Exemple : Soit \(A=\{1;2;3\}\). Les parties de \(A\) sont \(\varnothing\), \(\{1\}\), \(\{2\}\), \(\{3\}\), \(\{1;2\}\), \(\{1;3\}\), \(\{2;3\}\) et \(\{1;2;3\}\). Elles sont au nombre de \(2^3=8\).

Soit \(A\) un ensemble fini à \(n\) éléments et \(k\) un entier naturel \(n\). Le nombre de combinaisons à \(k\) éléments de \(A\) est noté \(\dbinom{n}{k}\) et se lit « \(k\) parmi \(n\) ». Les nombres \(\dbinom{n}{k}\) sont appelés coefficients binomiaux

Soit \(n\) et \(k\) deux entiers naturels.

  • Si \(k > n\), \(\dbinom{n}{k}=0\)
  • Sinon, \(\dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}\)

On sait qu’il y a \(\dfrac{n!}{(n-k)!}\) \(k\)-arrangements de \(A\). Cependant, plusieurs \(k\)-arrangements utilisent les mêmes éléments de \(A\) (par exemple, les couples (1;2) et (2;1) utilisent les nombres 1 et 2). Etant donné une partie de \(A\) à \(k\) éléments, on peut construire \(k!\) arrangements différents : on a \(k\) choix pour le premier élément, \(k-1\) pour le deuxième, etc.

Ainsi, le nombre de \(k\)-arrangements est \(k!\) fois plus grand que la nombre de combinaisons à \(k\) éléments. Ainsi, le nombre de combinaisons à \(k\) élements est égale au nombre de \(k\)-arrangements divisé par \(k!\), soit \(\dfrac{n!}{k!(n-k)!}\).

Exemple : Soit \(A=\{1;2;3;4\}\). Le nombre de combinaisons de \(A\) à deux élémens vaut \(\dbinom{4}{2}=\dfrac{4!}{2!(4-2)!}=\dfrac{4!}{2!2!}=\dfrac{24}{2 \times 2}=6\). Ces combinaisons sont \(\{1;2\}\), \(\{1;3\}\), \(\{1;4\}\), \(\{2;3\}\), \(\{2;4\}\) et \(\{3;4\}\).

Les combinaisons sont utilisées pour dénombrer les situations où l’ordre des objets n’est pas important – lorsque l’on tire simultanément plusieurs personnes par hasard – et qu’un objet ne peut être utilisé qu’une seule fois.

Exemple : A la belote, on utilise un jeu de 32 cartes. Chaque carte est déterminé par sa couleur (Pique, Trèfle, Carreau, Coeur) et sa valeur (As, Roi, Dame, Valet, 10, 9, 8, 7). Pour le premier tour de distribution, chaque joueur reçoit 5 cartes, que l’on appelle une main. Combien existe-t-il de mains comportant exactement 2 as ?

L’ordre de distribution des cartes n’a pas d’importance ici : recevoir un as en première carte ou en deuxième carte n’a pas d’influence, on utilise donc les combinaisons.

  • La main est composée de 2 as, choisis parmi 4, ce qui donne \(\dbinom{4}{2}=\dfrac{4!}{2!(4-2)!}=\dfrac{4!}{2!2!}=\dfrac{24}{4}=6\) possibilités
  • Il reste 3 cartes à déterminer, choisis parmi les 28 cartes qui ne sont pas des as. Cela donne \(\dbinom{28}{3}=\dfrac{28!}{3!(28-3)!}=\dfrac{28!}{3!25!}=\dfrac{28\times 27 \times 26}{3 \times 2 \times 1}=3276\)
  • Au total, cela fait \(6\times 3276 =19656\) mains de 5 cartes contenant exactement 2 as.

Soit \(n\) un entier naturel non nul.

  • Pour tout entier naturel \(k \leqslant n\), \(\dbinom{n}{k}=\dbinom{n}{n-k}\)
  • \(\dbinom{n}{0}=\dbinom{n}{n}=1\)
  • Si \(n\geqslant 1\), \(\dbinom{n}{1}=\dbinom{n}{n-1}=n\)
  • Si \(n\geqslant 2\), \(\dbinom{n}{2}=\dbinom{n}{n-2}=\dfrac{n(n-1)}{2}\)

Démonstration (Avec la formule) :

  • Pour tout entier naturel \(k\leqslant n\), \(\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}=\dfrac{n!}{(n-k)!(n-(n-k))!}=\dbinom{n}{n-k}\).
  • D’après le premier point, on a bien \(\dbinom{n}{0}=\dbinom{n}{n-0}=\dbinom{n}{n}\). Or, \(\dbinom{n}{0}=\dfrac{n!}{0!n!}=\dfrac{n!}{n!}=1\)
  • D’après le premier point, on a bien \(\dbinom{n}{1}=\dbinom{n}{n-1}\).Or, \(\dbinom{n}{1}=\dfrac{n!}{1!(n-1)!}=\dfrac{n!}{(n-1)!}=\dfrac{n \times (n-1)!}{(n-1)!}=n\)
  • D’après le premier point, on a bien \(\dbinom{n}{2}=\dbinom{n}{n-2}\).Or, \(\dbinom{n}{2}=\dfrac{n!}{2!(n-2)!}=\dfrac{n!}{2(n-2)!}=\dfrac{n(n-1) \times (n-2)!}{2(n-1)!}=\dfrac{n(n-1)}{2}\)

Démonstration (Combinatoire)

  • Choisir \(k\) objets parmi \(n\) revient à exclure \(n-k\) objets parmi ces \(n\) objets.Ainsi, \(\dbinom{n}{k}=\dbinom{n}{n-k}\)
  • Il n’existe qu’un seul ensemble à 0 élément, il s’agit de l’ensemble vide \(\varnothing\). De la même manière, si \(A\) est un ensemble à \(n\) éléments, la seule partie de \(A\) ayant \(n\) éléments est l’ensemble \(A\) lui-même. Ainsi, \(\dbinom{n}{0}=\dbinom{n}{n}=1\)
  • Si \(A\) est un ensemble fini \(\{a_1;a_2;\ldots ;a_n\}\) de cardinal supérieur ou égal à 1, les parties à 1 élément de \(A\) sont simplement les singletons \(\{ a_1\}\), \(\{a_2\}\), … , \(\{a_n\}\).Ainsi, \(\dbinom{n}{1}=\dbinom{n}{n-1}=n\).
  • Soit \(A\) un ensemble de cardinal \(n\geqslant 2\). Pour construire une partie à 2 éléments de \(A\), on choisit un premier élément (\(n\) choix possible) puis un second (\(n-1\) choix). En faisant ainsi, on peut construire \(n(n-1)\) couples d’éléments de \(A\). Or, l’ordre n’ayant pas d’importance, il est possible d’inverser l’ordre dans lequel on choisit les éléments de \(A\). Le nombre de combinaisons de \(A\) à 2 éléments vaut donc \(\dfrac{n(n-1)}{2}\)

Exemple : \(\dbinom{100}{98}=\dbinom{100}{2}=\dfrac{100 \times 99}{2}= 4950\)

Soit \(n\) un entier naturel supérieur ou égal à 2 et \(k\) un entier tel que \(1\leqslant k\leqslant n-1\). On a alors
\[ \dbinom{n-1}{k-1}+\dbinom{n-1}{k} = \dbinom{n}{k}\]
Cette relation s’appelle la relation de Pascal.

Démonstration (Avec la formule) :
\[ \dbinom{n-1}{k-1}+\dbinom{n-1}{k}=\dfrac{(n-1)!}{(k-1)!(n-1-(k-1))!}+\dfrac{(n-1)!}{k!(n-1-k)!}\]

On multiplie le premier quotient par \(\dfrac{k}{k}\) et le second par \(\dfrac{n-k}{n-k}\), ce qui donne
\[\dbinom{n-1}{k-1}+\dbinom{n-1}{k}=\dfrac{k \times (n-1)!}{k\times (k-1)! \times (n-1)!}+\dfrac{(n-k) \times (n-1)!}{k! \times (n-k-1)! \times (n-k)}\]
Or, \(k\times (k-1)!=k!\), \((n-k-1) \times (n-k)=(n-k)!\). Ainsi,

\[\dbinom{n-1}{k-1}+\dbinom{n-1}{k} = \dfrac{k \times (n-1)!}{k!(n-k)!}+\dfrac{(n-k) \times (n-1)!}{k!(n-k)!}=\dfrac{n \times (n-1)!}{k! (n-k)!}=\dfrac{n!}{k!(n-k)!}=\dbinom{n}{k}\]

Démonstration (Combinatoire) : Soit \(A\) un ensemble fini à \(n\) éléments et \(a\in A\). Soit \(k\) un entier naturel compris entre 1 et \(n-1\). L’ensemble des combinaisons à \(k\) éléments, noté \(\mathcal{P}_k(A)\), est, par définition, de cardinal \(\dbinom{n}{k}\). Il peut se décomposer en deux ensembles disjoints :

  • \(P_1\), L’ensemble des combinaisons à \(k\) éléments de \(A\) qui contiennent l’élément \(a\). Il reste donc à choisir \(k-1\) éléments parmi les \(n-1\) restants. Le cardinal de cet ensemble est donc \(\dbinom{n-1}{k-1}\)
  • \(P_2\), L’ensemble des combinaisons à \(k\) éléments de \(A\) qui ne contiennent pas l’élément \(a\). Il faut donc choisir \(k\) éléments parmi les \(n-1\) autres éléments. Le cardinal de cet ensemble est donc \(\dbinom{n-1}{k}\)

On a alors \(\mathcal{P}_k(A)=P_1 \cup P_2\) ce qui implique que \(\dbinom{n}{k} = \mathrm{Card}(\mathcal{P}_k(A))=\mathrm{Card}(P_1 \cup P_2)\). Or, les ensembles \(P_1\) et \(P_2\) sont disjoints. Ainsi, \(\mathrm{Card}(P_1 \cup P_2)= \mathrm{Card}(P_1)+\mathrm{Card}(P_2)\). Autrement dit, on a \(\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}\).

La relation de Pascal permet de construire récursivement les coefficients binomiaux. Ces coefficients peuvent être arrangés en triangle et forment ce que l’on appelle le triangle de Pascal

Dans ce triangle, on démarre avec un 1 en haut à gauche. Pour compléter chaque cellule, on ajoute alors le nombre au-dessus avec le nombre en haut à gauche. Les cases vides se voient assigner la valeur 0. On peut alors lire les coefficients binomiaux \(\dbinom{n}{k}\) dans ce triangle.