Dénombrement

Un article de Wiki SILLAGES.

Ce résumé est basé sur le programme de mathématiques de première année des classes préparatoires aux grandes écoles économiques et commerciales, voie scientifique (ECS1). Un résumé complet du programme de mathématiques ECS1 est proposé sur la Plate-forme SILLAGES.

Sommaire

1 Cardinal d’un ensemble fini
2 Partition
3 Arbre de dénombrement
4 Notation factorielle
5 Nombre de p-listes avec répétition
6 Nombre de p-listes sans répétition (arrangements)
7 Nombre de permutations
8 Nombre de parties à p éléments (combinaisons)
9 Nombre de parties d’un ensemble à n éléments
10 Nombre de manières d’ordonner des objets
11 Nombre de tirages de p objets parmi n

Cardinal d’un ensemble fini

Si $E\neq\O$ , c’est l’unique entier $n\in\mathbb N^*$ tel que $E$ soit en bijection avec $[\![1,n]\!]$ .

$\mathrm{Card}E=n$ est le nombre d’éléments de $E$ et $\mathrm{Card}\O=0$ .

Propriétés :

$\mathrm{Card}\overline A=\mathrm{Card}E-\mathrm{Card}A$

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

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

Formule du crible :

$\mathrm{Card}\left(\bigcup_{k=1}^{n}A_k\right)=\sum_{k=1}^{n}(-1)^{k-1}\left(\sum_{1\leq i_1<...<i_k\leq n}\mathrm{Card}(A_{i_1}\cap ...\cap A_{i_k})\right)$

$\mathrm{Card}(A\times B)=(\mathrm{Card}A)\times\mathrm{Card}B$

Partition

Une famille $(A_1, ...,A_n )$ de parties de $E$ est une partition de $E$ si :

Leur réunion est égale à $E$ : $E=A_1\cup ...\cup A_n$
Elles sont deux à deux disjointes : $A_i\cap A_j=\O\quad\mathrm{pour} \quad\mathrm{tous}\quad i\neq j$

Alors $\mathrm{Card}E=\mathrm{Card}A_1+ ...+\mathrm{Card}A_n$ .

Arbre de dénombrement

Si une situation se décompose en $k$ étapes ayant respectivement $n_1, ..., n_k$ issues possibles, alors on peut schématiser cette situation par un arbre et le nombre total d’issues est : $n=n_1\times ...\times n_k$ .

Notation factorielle

Si $n\neq 0$ , $n!$ est le produit de tous les entiers compris entre 1 et $n$ .

Par définition : $0!= 1$

Propriété: $(n+1)!=(n+1)\times n!$

Nombre de p-listes avec répétition

Une $p$ -liste avec répétition de $E$ est un élément $(x_1, ...,x_p)$ de $E^p$ .

Si $\mathrm{Card}E=n$ , le nombre de $p$ -listes avec répétition de $E$ est : $n^p$ .

C’est aussi le nombre d’applications d’un ensemble à $p$ éléments dans un ensemble à $n$ éléments.

Nombre de p-listes sans répétition (arrangements)

Une $p$ -liste sans répétition de $E$ est un élément $(x_1, ...,x_p)$ où les $x_i$ sont des éléments distincts de $E$ .

Si $\mathrm{Card}E=n$ , le nombre de $p$ -listes sans répétition de $E$ est : $A_{n}^{p}=\dfrac{n!}{(n-p)!}\quad\mathrm{si}\quad 0\leq p\leq n\quad\mathrm{et}\quad A_{n}^{p}=0\quad\mathrm{sinon.}$

C’est aussi le nombre d’applications injectives d’un ensemble à $p$ éléments dans un ensemble à $n$ éléments.

Nombre de permutations

Une permutation de $E$ est une bijection de $E$ dans $E$ . Si $\mathrm{Card}E=n$ , une permutation de $E$ correspond à une $n$ -liste sans répétition de $E$ . Donc le nombre de permutations de $E$ est $n!$ .

C’est aussi le nombre de bijections d’un ensemble à $n$ éléments dans un autre ensemble à $n$ éléments.

Nombre de parties à p éléments (combinaisons)

Si $\mathrm{Card}E=n$ , le nombre de parties à $p$ -éléments est : $\begin{pmatrix} n \\ p \end{pmatrix}=\dfrac{n!}{p!(n-p)!}\quad\mathrm{si}\quad 0\leq p\leq n\quad\mathrm{et}\quad\begin{pmatrix} n \\ p \end{pmatrix}=0\quad\mathrm{sinon.}$

Propriétés :

$\begin{pmatrix} n \\ p \end{pmatrix}=\begin{pmatrix} n \\ {n-p} \end{pmatrix}$

$\begin{pmatrix} {n+1} \\ p \end{pmatrix}=\begin{pmatrix} n \\ p \end{pmatrix}+\begin{pmatrix} n \\ {p-1} \end{pmatrix}\quad\mathrm{si}\quad 1\leq p\leq n$