Cardinal d'un ensemble

Le cardinal d'un ensemble $A$ est le nombre d'éléments contenus dans $A$. On le note : $Card(A)$.

Exemple : Si $A$ désigne l'ensemble des cartes qui constituent un jeu de 32 cartes alors $Card(A) = 32$.

On dit qu'un ensemble $A$ est fini si $Card(A)$ n'est pas infini

Principe additif

Soient $A$ et $B$ deux ensembles finis disjoints, c'est-à-dire n'ayant aucun élément commun, tels que $Card(A)=n$ et $Card(B)=m$. Alors, le nombre de façons de prendre un élément dans $A$ ou un élément dans $B$ est égal à $n+m$.

Exemple : Dans ma bibliothèque, il y a 20 romans et 10 bandes dessinées. Je peux donc y choisir un livre de $20 + 10 = 30$ façons différentes.

Principe multiplicatif

Soient $A$ et $B$ deux ensembles finis tels que $Card(A)=n$ et $Card(B) = m$. Le nombre de façons de prendre un élément dans $A$ et un élément dans $B$ est égal à $n \times m$.
Exemple : Dans ma bibliothèque, il y a 20 romans et 10 bandes dessinées. Je souhaite prendre un livre de chaque sorte. Il y a donc $20 \times 10= 200$ possibilités.
Les principe multiplicatif peut se représenter sous la forme d'un arbre des possibilités:
On peut aussi considérer un tableau à $n$ colonnes et $m$ lignes : il comporte $n \times m$ cellules.

Factorielle

La factorielle d'un nombre entier $n$ est le nombre : \[ n! = 1 \times 2\times 3\times 4\times \cdots \times (n-1) \times n. \]

Exemple : $5! = 1 \times 2\times 3\times 4\times 5 = 120$.

Permutation

Soit $E$ un ensemble à $n$ éléments, $n \in \mathbb{N}^*$. Une \textit{permutation} de $E$ est un ensemble composé des $n$ éléments de $E$.

Exemples :

Arrangement

Soit $n$ un entier naturel non nul, et soit $E$ un ensemble à $n$ éléments. Un arrangement de $p$ éléments de $E$ est une $p$-liste d'éléments distincts.

Exemple : Le podium d'une course à 20 participants est un arrangement constitué du premier arrivé, puis du deuxième et enfin du troisième.

Le nombre d'arrangements de $p$ éléments pris dans un ensemble à $n$ éléments est: \[ A_n^p = \dfrac{n!}{(n-p)!}=n(n-1)(n-2)\cdots(n-p+1). \]

Exemple : $A_{20}^3=20\times19\times18=6840$.
Il y a donc 6840 podiums possibles pour une course à 20 participants.

Combinaison

Soient $n$ et $p$ deux entiers naturels non nuls tels que $p \leqslant n$, et soit $E$ un ensemble à $n$ éléments. Une combinaison de $p$ éléments de $E$ est un ensemble non ordonné à $p$ éléments distincts pris parmi les $n$ éléments de $E$.

Exemple : Sur un jeu de 32 cartes, une main de 5 cartes est une combinaison.

Le nombre de combinaisons de $p$ éléments d'un ensemble $E$ à $n$ éléments est égal à : \[ \dbinom{n}{p}=\dfrac{A_n^p}{p!}=\dfrac{n!}{p!(n-p)!}=\dfrac{n(n-1)\cdots(n-p+1)}{p!}. \]

Exemple : \[\dbinom{32}{5}=\dfrac{32\times31\times\cdots\times(32-5+1)}{5!}=201376\] donc il y a 201376 mains de 5 cartes possibles sur un jeu de 32 cartes.

Triangle de Pascal

Pour tous entiers naturel $n$ et $p$ tels que $p\leqslant n$ et $n\neq0$, \[ \dbinom{n}{p}=\dbinom{n-1}{p-1}+\dbinom{n-1}{p}. \]

Binôme de Newton

Soient $a$ et $b$ deux réels. Pour tous entiers naturel $n$ et $p$ tels que $p\leqslant n$ et $n\neq0$,\[(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\]

Démonstration par récurrence du binôme de Newton

On veut montrer que pour tout entier \( n \geq 0 \) :

\[(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\]

Initialisation

Pour \( n = 0 \) :

\[(a + b)^0 = 1\]
\[\sum_{k=0}^{0} \binom{0}{k} a^{0-k} b^k = 1\]

La propriété est vraie au rang 0.

Hérédité

Supposons la propriété vraie pour un entier \( n \) :

\[(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\]

Montrons-la pour \( n+1 \) :

\[(a + b)^{n+1} = (a + b)(a + b)^n\]
\[= (a + b)\sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\]
\[= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k+ \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k+1}\]

On change d'indice dans la deuxième somme :

\[= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k+ \sum_{j=1}^{n+1} \binom{n}{j-1} a^{n+1-j} b^j\]

On regroupe :

\[(a + b)^{n+1} =\binom{n}{0} a^{n+1}+ \sum_{k=1}^{n} (\binom{n}{k} + \binom{n}{k-1}) a^{n+1-k} b^k+ \binom{n}{n} b^{n+1}\]
\[\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}\]
\[(a + b)^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k} b^k\]

Conclusion

La propriété est vraie pour tout entier \( n \geq 0 \).

Exemple : Lorsque $a=1$ et $b=1$. On obtient, pour tous entiers naturels $n$ et $p$ tels que $p\leqslant n$ et $n\neq0$, \[ \sum_{k=0}^n\dbinom{n}{k}=2^n. \]