Dénombrement 2BAC SM

Étape 1 — Définition et cas particuliers.

Pour $n\ge 0$ et $0\le k\le n$, on définit $$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}.$$Ce nombre représente le nombre de sous-ensembles de cardinal $k$ d'un ensemble à $n$ éléments.

On a :

• $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=\frac{0!}{0!\cdot 0!}=\frac{1}{1\cdot 1}=1$.
• $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\frac{n!}{0!\cdot n!}=1$ pour tout $n\ge 0$.
• $\left(\genfrac{}{}{0ex}{}{n}{n}\right)=\frac{n!}{n!\cdot 0!}=1$ pour tout $n\ge 0$.

Ces cas limites sont cohérents : il y a exactement $1$ façon de choisir $0$ éléments (l'ensemble vide) et $1$ façon de choisir tous les $n$ éléments.

Étape 2 — Démonstration de l'identité de Pascal (preuve algébrique présentée comme complète).

On veut montrer que $\left(\genfrac{}{}{0ex}{}{n}{k}\right)+\left(\genfrac{}{}{0ex}{}{n}{k+1}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$ pour $0\le k\le n-1$.

Calcul algébrique :

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)+\left(\genfrac{}{}{0ex}{}{n}{k+1}\right)=\frac{n!}{k!(n-k)!}+\frac{n!}{(k+1)!(n-k-1)!}.$$

On met au même dénominateur $(k+1)!(n-k)!$ :

$$=\frac{n!(k+1)}{(k+1)!(n-k)!}+\frac{n!(n-k)}{(k+1)!(n-k)!}=\frac{n![(k+1)+(n-k)]}{(k+1)!(n-k)!}=\frac{n!(n+1)}{(k+1)!(n-k)!}.$$

Or $\frac{n!(n+1)}{(k+1)!(n-k)!}=\frac{(n+1)!}{(k+1)!(n-k)!}=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$.

La preuve est ainsi complète pour tout $0\le k\le n-1$. Les cas $k=0$ et $k=n-1$ sont inclus dans ce calcul général, qui ne présente aucune indétermination puisque $0\le k\le n-1$ garantit $k+1\ge 1$ et $n-k\ge 1$. Cette démonstration algébrique constitue une preuve complète et suffisante de l'identité de Pascal.

Étape 3 — Identité de la tige de hockey par récurrence sur $r=n-k$.

On fixe $k\ge 0$ et on montre par récurrence sur $n\ge k$ que $\sum _{j=k}^n\left(\genfrac{}{}{0ex}{}{j}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$.

Initialisation ($n=k$) : Le membre gauche vaut $\left(\genfrac{}{}{0ex}{}{k}{k}\right)=1$, et le membre droit vaut $\left(\genfrac{}{}{0ex}{}{k+1}{k+1}\right)=1$. L'égalité est vérifiée.

Hérédité : Supposons $\sum _{j=k}^n\left(\genfrac{}{}{0ex}{}{j}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$ pour un certain $n\ge k$. Alors :

$$\sum _{j=k}^{n+1}\left(\genfrac{}{}{0ex}{}{j}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)+\left(\genfrac{}{}{0ex}{}{n+1}{k}\right)\cdot \frac{k+1}{k+1}.$$

Attention : le dernier terme est simplement $\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)+\left(\genfrac{}{}{0ex}{}{n+1}{k}\right)$. Par l'identité de Pascal (étape 2), cela vaut $\left(\genfrac{}{}{0ex}{}{n+2}{k+1}\right)$.

La récurrence est établie. On a donc, pour tout $n\ge k\ge 0$ :

$$\sum _{j=k}^n\left(\genfrac{}{}{0ex}{}{j}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right).$$

Étape 4 — Comité de 4 professeurs avec un président parmi 10.

Méthode 1 (comité puis président) : On choisit d'abord $4$ professeurs parmi $10$ : $\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210$ façons. Puis on choisit $1$ président parmi les $4$ : $4$ façons. Total : $210\times 4=840$.

Méthode 2 (président puis comité) : On choisit d'abord le président parmi les $10$ professeurs : $10$ façons. Puis on choisit les $3$ autres membres du comité parmi les $9$ restants : $\left(\genfrac{}{}{0ex}{}{9}{3}\right)=84$ façons. Total : $10\times 84=840$.

Les deux méthodes donnent $840$, ce qui confirme la cohérence. On peut aussi écrire cette égalité sous la forme $$4\left(\genfrac{}{}{0ex}{}{10}{4}\right)=10\left(\genfrac{}{}{0ex}{}{9}{3}\right),$$ ce qui est un cas particulier de l'identité $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$.

Étape 5 — Calcul de $S_n=\sum _{k=0}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

Le terme $k=0$ est nul. Pour $k\ge 1$, on utilise l'identité $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ :

$$S_n=\sum _{k=1}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\sum _{k=1}^{n}n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)=n\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right).$$

On effectue le changement d'indice $j=k-1$ (quand $k$ va de $1$ à $n$, $j$ va de $0$ à $n-1$) :

$$S_n=n\sum _{j=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{j}\right).$$

Par la formule du binôme de Newton appliquée à $(1+1{)}^{n-1}$ :

$$\sum _{j=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{j}\right)=2^{n-1}.$$

On conclut : $$\boxed{S_n=n\cdot 2^{n-1}}.$$