On souhaite dénombrer le nombre de parties à $p$ éléments dans un ensemble à $n$ éléments. Une telle partie est aussi désignée sous le nom de combinaison de $p$ éléments parmi $n$.
Le nombre de combinaison de $p$ éléments parmi $n$ est :\begin{align*}&\mbox{Si $0\lt p\lt n$,}\ \frac{\prod\limits_{i=n-p+1}^n{i}}{\prod\limits_{j=1}^{p}{j}}=\frac{n(n-1)(n-2)\dotsm(n-p+1)}{p!}=\frac{n!}{p!(n-p)!}=\binom{n}{p} \\&\mbox{Si $p\gt n$, ce nombre est nul}.\end{align*}
Soit $n$ un entier naturel non nul fixé et $p$ un entier compris entre $0$ et $n$.
Nous avons d’après ce qui précède :\begin{align*}&n(n-1)\dotsm(n-p+1)=\prod\limits_{k=n-p+1}^n{k} \\&=\dfrac{n!}{(n-p)!}\text{ listes de $p$ éléments de $E$ deux à deux distincts.}\end{align*}Or, chaque combinaison de $p$ éléments peut être définie à partir de $p!$ listes ordonnées différentes, obtenues en rangeant les $p$ éléments en question selon toutes les permutations possibles de ces $p$ éléments.
Par exemple, avec $E=\{a,b,c,d\}$, nous avons $4\times 3=\dfrac{4!}{(4-2)!}=12$ listes de $2$ éléments.
Ces listes sont :\[(a,b),\ (a,c),\ (a,d),\ (b,a),\ (b,c),\ (b,d),\ (c,a),\ (c,b),\ (c,d),\ (d,a),\ (d,b),\ (d,c).\]Si nous nous intéressons aux combinaisons de $2$ éléments, les listes $(a,b)$ et $(b,a)$ donne la même combinaison : $\{a,b\}$.
Pour une combinaison de $p$ éléments, nous avons $p!$ listes ordonnées.II y a donc $p!$ fois moins de combinaisons que de telles listes.
Ainsi, le nombre de combinaisons possibles de $p$ éléments parmi $n$ est :\[\frac{\text{Nombre de listes de $p$ éléments parmi $n$ $2$ à $2$ distincts}}{p!}=\frac{\dfrac{n!}{(n-p)!}}{p!}=\frac{n!}{p!(n-p)!}\]Cette méthode de raisonnement est connue sous le nom de principe des bergers.
En effet, pour compter ses moutons, le berger compte le nombre de pattes et divise le résultat par $4$.
Dans le cas présent, un mouton formant une combinaison possède $p!$ pattes constituées de chacune des listes donnant cette combinaison.Comme il y a au total $n(n-1)(n-2)\dotsm(n-p+l)$ listes et que chaque mouton possède $p!$ pattes, il y a bien \[\dfrac{n(n-1)(n-2)\dotsm(n-p+1)}{p!}\text{ moutons.}\]
Le nombre $\dbinom{n}{p}$ si $0\lt p\lt n$ est appelé coefficient binomial (nous allons voir qu’il intervient dans la formule du binôme de Newton).
On note aussi $C_n^p$ le coefficient binomial, notation de moins en moins utilisée.
On considère $5$ boules de couleurs différentes. On en prend $3$ dans un ordre arbitraire. Il y a $10$ choix possibles.
Les valeurs les plus courantes, à savoir sans hésitation, sont :\begin{align}\binom{n}{0}&=\binom{n}{n}=1 \label{eq:prop4-1} \\\binom{n}{1}&=\binom{n}{n-1}=n \label{eq:prop4-2}\end{align}
Les démonstrations peuvent se faire avec la formule : $\dbinom{n}{p}=\dfrac{n!}{p!(n-p)!}$ ou plus simplement en suivant le raisonnement suivant :
- Pour $\eqref{eq:prop4-1}$ :
$\dbinom{n}{0}$ est le nombre de partie à $0$ élément parmi un ensemble de $n$ éléments. Ce nombre est $1$ (il y a une seule partie à $0$ élément : la partie vide).
$\dbinom{n}{n}$ est le nombre de partie à $n$ éléments parmi un ensemble de $n$ éléments. Ce nombre est $1$ (il y a une seule partie à $n$ élément : la partie pleine de tous les éléments).
Donc, nous obtenons :\[\binom{n}{0}=\dbinom{n}{n}=1.\]- Pour $\eqref{eq:prop4-2}$ :
$\dbinom{n}{1}$ est le nombre de partie à $1$ élément parmi un ensemble de $n$ élément : ce nombre est $n$.
$\dbinom{n}{n-1}$ est le nombre de partie à $(n-1)$ éléments parmi un ensemble de $n$ élément. Prendre une partie à $(n-1)$ élément ou laisser $1$ élément est la même procédure. Donc, $\dbinom{n}{1}$=$\dbinom{n}{n-1}$et ainsi ce nombre est $n$.
Donc, nous obtenons :\[\binom{n}{1}=\dbinom{n}{n-1}=n.\]