Dénombrement

Chapitre 17

Auteur·rice

Saîd MAHARI

Date de publication

22 août 2026

TSI 1re année — Chapitre 17. Cardinaux, parties, p-listes, arrangements, permutations, combinaisons, formules de Pascal et du binôme.

Ce chapitre a été réalisé conformément au programme marocain de mathématiques de la filière TSI1.

Dans ce chapitre, on note I_n = \llbracket 1, n \rrbracket (intervalle d’entiers compris entre 1 et n), où n \in \mathbb{N}^*, et I_0 = \varnothing.

1 Ensembles finis et applications entre ensembles finis

1.1 Notion de cardinal

Définition 1.1 — (Ensemble fini)

Un ensemble E est dit fini s’il existe n \in \mathbb{N} et une bijection de E sur I_n = \llbracket 1, n \rrbracket.

L’entier n est unique et est appelé cardinal de E. On le note \mathrm{Card}(E), |E| ou \#E.

Un ensemble qui n’est pas fini est dit infini.

Tout fondement théorique des notions d’entier naturel et de cardinal est hors programme.

Exemple 1.1

  • \mathrm{Card}(\varnothing) = 0
  • \mathrm{Card}(I_n) = n
  • \mathrm{Card}(\{a, b, c\}) = 3

1.2 Cardinal d’une partie d’un ensemble fini

Proposition 1.1

Soit E un ensemble fini et A une partie de E. Alors :

  1. A est fini et \mathrm{Card}(A) \leq \mathrm{Card}(E).
  2. \mathrm{Card}(A) = \mathrm{Card}(E) si et seulement si A = E.

Proposition 1.2 — (Cardinal du complémentaire)

Soit E un ensemble fini et A une partie de E. Alors : \mathrm{Card}(E \setminus A) = \mathrm{Card}(E) - \mathrm{Card}(A)

1.3 Cardinal d’un produit fini d’ensembles finis

Proposition 1.3

Soient E_1, E_2, \ldots, E_p des ensembles finis. Alors : \mathrm{Card}(E_1 \times E_2 \times \cdots \times E_p) = \mathrm{Card}(E_1) \times \mathrm{Card}(E_2) \times \cdots \times \mathrm{Card}(E_p)

Exemple 1.2

Le nombre de couples (x, y) \in I_3 \times I_4 est 3 \times 4 = 12.

1.4 Cardinal de l’ensemble des applications

Proposition 1.4

Soient E et F deux ensembles finis de cardinaux respectifs p et n. Alors le nombre d’applications de E dans F est : n^p

Preuve. Soit E = \{x_1, x_2, \ldots, x_p\}. Une application f : E \to F est entièrement déterminée par les valeurs (f(x_1), f(x_2), \ldots, f(x_p)) \in F^p. Or \mathrm{Card}(F^p) = n^p.

1.5 Cardinal de l’ensemble des parties

Proposition 1.5

Soit E un ensemble fini de cardinal n. Alors le nombre de parties de E est : 2^n

Preuve. À chaque partie A de E, on associe sa fonction indicatrice \mathbb{1}_A : E \to \{0, 1\} définie par \mathbb{1}_A(x) = 1 si x \in A et 0 sinon. Cette correspondance est bijective, donc le nombre de parties de E est égal au nombre d’applications de E dans \{0,1\}, qui est 2^n.

2 Dénombrement

2.1 Dénombrement des p-listes

Définition 2.1 — (\boldsymbol{p}-liste)

Soit E un ensemble fini de cardinal n \in \mathbb{N}^* et soit p \in \mathbb{N}^*. On appelle p-liste (ou liste de longueur p) un p-uplet (x_1, \ldots, x_p) d’éléments de E.

Une p-liste est donc un élément du produit cartésien E^p.

Proposition 2.1 — (Nombre des \boldsymbol{p}-listes)

Le nombre des p-listes d’un ensemble E de cardinal n est : n^p

Exemple 2.1

  • Le nombre de 3-listes de \{a, b, c\} est 3^3 = 27.
  • Le nombre de mots de 5 lettres formés avec les lettres de \{a, b\} est 2^5 = 32.

2.2 Dénombrement des p-arrangements

Définition 2.2 — (Arrangements et permutations)

Soit E un ensemble fini de cardinal n \in \mathbb{N}^* et soit p tel que 1 \leq p \leq n.

  1. On appelle p-arrangement (ou arrangement de p éléments) une p-liste d’éléments distincts de E.
  2. On appelle permutation tout n-arrangement des éléments de E.

Proposition 2.2 — (Nombre des \boldsymbol{p}-arrangements et des permutations)

Soit E un ensemble fini de cardinal n \in \mathbb{N}^* et soit p tel que 1 \leq p \leq n. Alors :

  1. Le nombre des p-arrangements des éléments de E est : A_n^p = n(n-1)\cdots(n-p+1) = \frac{n!}{(n-p)!}

  2. Le nombre des permutations des éléments de E est : A_n^n = n!

Preuve. Pour former un p-arrangement, on choisit successivement p éléments distincts : - n choix pour le premier élément - n-1 choix pour le deuxième élément - \vdots - n-p+1 choix pour le p-ème élément

Par le principe multiplicatif, le nombre total est n(n-1)\cdots(n-p+1).

Exemple 2.2

  • Le nombre de 3-arrangements de \{a, b, c, d, e\} est A_5^3 = 5 \times 4 \times 3 = 60.
  • Le nombre de permutations de \{a, b, c\} est 3! = 6.

Proposition 2.3 — (Nombre d’applications injectives)

Soient E et F deux ensembles finis de cardinaux respectifs p \in \mathbb{N}^* et n \in \mathbb{N}^*. Alors le nombre des applications injectives de E dans F est : \begin{cases} A_n^p = \frac{n!}{(n-p)!} & \text{si } p \leq n \\ 0 & \text{si } p > n \end{cases}

2.3 Dénombrement des p-combinaisons

Définition 2.3 — (\boldsymbol{p}-combinaison)

Soit E un ensemble fini de cardinal n \in \mathbb{N}^* et soit p tel que 0 \leq p \leq n. On appelle p-combinaison (ou combinaison à p éléments) toute partie de E à p éléments.

Proposition 2.4 — (Nombre des \boldsymbol{p}-combinaisons)

Soit E un ensemble fini de cardinal n \in \mathbb{N}^* et soit p tel que 0 \leq p \leq n. Alors le nombre des p-combinaisons des éléments de E est : C_n^p = \binom{n}{p} = \frac{A_n^p}{p!} = \frac{n!}{p!(n-p)!}

Preuve. Chaque p-combinaison A de E donne lieu à p! p-arrangements distincts (les permutations des éléments de A). Donc : A_n^p = C_n^p \times p! d’où C_n^p = \frac{A_n^p}{p!} = \frac{n!}{p!(n-p)!}.

Exemple 2.3

  • Le nombre de parties à 2 éléments de \{a, b, c, d\} est C_4^2 = \frac{4!}{2!2!} = 6.
  • Le nombre de façons de choisir 3 élèves parmi 10 est C_{10}^3 = \frac{10!}{3!7!} = 120.

Exemple 2.4 — (Exemple de dénombrement)

Dans une classe de 32 élèves (19 garçons et 13 filles), on veut choisir 2 délégués.

  1. Quel est le nombre de choix ? Cela revient à choisir 2 éléments parmi 32 : C_{32}^2 = 496.

  2. Quel est le nombre de choix si l’on impose un garçon et une fille ? Cela revient à choisir 1 parmi 19 et 1 parmi 13 : C_{19}^1 \times C_{13}^1 = 19 \times 13 = 247.

  3. Quel est le nombre de choix si l’on impose 2 garçons ? Cela revient à choisir 2 éléments parmi 19 : C_{19}^2 = 171.

3 Formules de Pascal et du binôme

3.1 Triangle de Pascal

Proposition 3.1 — (Relation de Pascal)

Soit n \in \mathbb{N}^* et soit p tel que 0 \leq p \leq n. On a la relation : C_{n+1}^{p+1} = C_n^{p+1} + C_n^p

Preuve. Soit E un ensemble de n+1 éléments et a \in E. On compte les parties à p+1 éléments de E de deux manières :

  • Directement : C_{n+1}^{p+1}.
  • En séparant les parties qui contiennent a et celles qui ne le contiennent pas :
    • Parties à p+1 éléments contenant a : on choisit les p autres éléments parmi les n restants, soit C_n^p.
    • Parties à p+1 éléments ne contenant pas a : on choisit les p+1 éléments parmi les n restants, soit C_n^{p+1}.

Donc C_{n+1}^{p+1} = C_n^p + C_n^{p+1}.

Proposition 3.2 — (Triangle de Pascal)

À partir de la relation de Pascal, on peut tracer la table dite Triangle de Pascal qui donne les valeurs des coefficients binomiaux :

n \backslash p 0 1 2 3 4 5
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

3.2 Formule du binôme de Newton

Théorème 3.1 — (Formule du binôme de Newton)

Le triangle de Pascal permet notamment de développer le polynôme (a+b)^n. Par récurrence, on montre :

Pour tout n \in \mathbb{N}^* et tous a, b \in \mathbb{C} : (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}

Exemple 3.1

(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 (a+b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4

Proposition 3.3 — (Interprétation combinatoire)

On a les propriétés suivantes :

  1. \binom{n}{p} = \binom{n}{n-p} (symétrie)
  2. \sum_{k=0}^n \binom{n}{k} = 2^n (somme des coefficients binomiaux)

Preuve. \sum_{k=0}^n \binom{n}{k} compte le nombre total de parties d’un ensemble de n éléments, en regroupant les parties par cardinal. Or ce nombre est 2^n.

4 Ensembles dénombrables

Définition 4.1

Un ensemble est dénombrable s’il est en bijection avec \mathbb{N}. Un ensemble est au plus dénombrable s’il est en bijection avec une partie de \mathbb{N}.

Un ensemble est au plus dénombrable si et seulement s’il est fini ou dénombrable.

Exemple 4.1

  • L’ensemble \mathbb{Z} est dénombrable.
  • Les parties infinies de \mathbb{N} sont dénombrables.
  • L’ensemble des entiers naturels pairs 2\mathbb{N} et l’ensemble des entiers naturels impairs 2\mathbb{N}+1 sont dénombrables.
  • Plus généralement, toute partie de \mathbb{N} infinie est dénombrable.
  • L’ensemble des zéros d’un polynôme non nul est au plus dénombrable.
  • L’ensemble des termes d’une suite est dénombrable.
  • Le produit cartésien \mathbb{N} \times \mathbb{N} est dénombrable.
  • L’ensemble des points de discontinuité d’une fonction monotone est au plus dénombrable.

5 Exercices

Exercice 5.1

  1. Déterminer le nombre de mots de 4 lettres formés avec les lettres de \{a, b, c\}.
  2. Déterminer le nombre de mots de 4 lettres formés avec les lettres de \{a, b, c\} sans répétition.

Exercice 5.2

  1. Déterminer le nombre de façons de ranger 5 livres sur une étagère.
  2. Déterminer le nombre de façons de choisir 3 livres parmi 5.

Exercice 5.3

Dans un jeu de 32 cartes, on tire 5 cartes.

  1. Quel est le nombre de tirages possibles ?
  2. Quel est le nombre de tirages contenant exactement 2 as ?
  3. Quel est le nombre de tirages contenant au moins 1 as ?

Exercice 5.4

Montrer par un argument combinatoire que : \sum_{k=0}^n \binom{n}{k} = 2^n

Exercice 5.5

Montrer par un argument combinatoire que : \binom{n}{p} = \binom{n}{n-p}

Exercice 5.6

Calculer C_{10}^3, C_{10}^7 et vérifier que C_{10}^3 = C_{10}^7.

Exercice 5.7

Montrer que : \binom{n+1}{p+1} = \binom{n}{p+1} + \binom{n}{p} en utilisant la formule avec les factorielles.

Exercice 5.8

Soit E un ensemble de n éléments.

  1. Déterminer le nombre de parties de E.
  2. Déterminer le nombre de parties de E à 1 élément.
  3. Déterminer le nombre de parties de E à 2 éléments.
  4. En déduire la valeur de \sum_{k=0}^n \binom{n}{k}.

Document en PDF

Chapitre 17 : Dénombrement