Problème — Identités binomiales combinatoires et algébriques

Exercice de TD · niveau 3 (difficile) · mathématiques (terminale), chapitre 7 — Combinatoire et Dénombrement

Énoncé

Problème — Identités binomiales combinatoires et algébriques.

Soit $n$ un entier naturel non nul. Le but de ce problème est d'étudier la somme :

$S_{n} = k = 1 \sum n k (k n)$

Calculer $S_{1}$ , $S_{2}$ et $S_{3}$ . Conjecturer une formule simplifiée pour $S_{n}$ .
Méthode algébrique : En utilisant la relation d'égalité de l'exercice « Calculs de coefficients binomiaux et propriétés » ( $k (k n) = n (k - 1 n - 1)$ ), démontrer la conjecture.
Méthode combinatoire : On considère un groupe de $n$ personnes. On souhaite former un comité de taille quelconque (contenant au moins une personne) et choisir un président au sein de ce comité.

En dénombrant selon la taille $k$ du comité choisi, montrer que le nombre total de choix possibles est égal à $S_{n}$ .
En choisissant d'abord le président, puis le reste du comité parmi les personnes restantes, déterminer à nouveau le nombre total de choix possibles.
Conclure.

Corrigé

Calculons les premières valeurs :

pour $n = 1$ : $S_{1} = 1 (1 1) = 1 \times 1 = 1 = 1 \times 2^{0}$ ;
pour $n = 2$ : $S_{2} = 1 (1 2) + 2 (2 2) = 1 \times 2 + 2 \times 1 = 4 = 2 \times 2^{1}$ ;
pour $n = 3$ : $S_{3} = 1 (1 3) + 2 (2 3) + 3 (3 3) = 1 \times 3 + 2 \times 3 + 3 \times 1 = 12 = 3 \times 2^{2}$ .

On conjecture ainsi la formule générale :

$S_{n} = n 2^{n - 1}$

D'après la relation $k (k n) = n (k - 1 n - 1)$ , on a :

$S_{n} = k = 1 \sum n k (k n) = k = 1 \sum n n (k - 1 n - 1) = n k = 1 \sum n (k - 1 n - 1)$

Effectuons le changement d'indice $j = k - 1$ . Quand $k$ varie de $1$ à $n$ , l'indice $j$ varie de $0$ à $n - 1$ :

$S_{n} = n j = 0 \sum n - 1 (j n - 1)$

Or, d'après l'exercice « Nombre de sous-ensembles », la somme des coefficients binomiaux d'ordre $n - 1$ vaut $\sum_{j = 0}^{n - 1} (j n - 1) = 2^{n - 1}$ . On en déduit immédiatement :

$S_{n} = n 2^{n - 1}$

Utilisons le raisonnement par double dénombrement :

Pour former un comité avec un président, on peut d'abord choisir un comité de $k$ personnes parmi les $n$ ( $(k n)$ choix), puis désigner un président parmi les $k$ membres élus ( $k$ choix). Le nombre de choix pour un comité de taille $k$ est $k (k n)$ . Comme la taille $k$ du comité peut être n'importe quelle valeur de $1$ à $n$ , le nombre total de choix possibles est :

$k = 1 \sum n k (k n) = S_{n}$

On peut procéder autrement :

on choisit d'abord le président du comité parmi les $n$ personnes du groupe ( $n$ choix) ;
ensuite, pour chacune des $n - 1$ personnes restantes, on décide si elle fait partie ou non du reste du comité : cela correspond à former un sous-ensemble quelconque des $n - 1$ personnes restantes, soit $2^{n - 1}$ choix.

Par le principe multiplicatif, le nombre total de choix possibles est :

$n \times 2^{n - 1}$

Les deux méthodes dénombrant le même ensemble de configurations, on en déduit l'égalité :

$S_{n} = n 2^{n - 1}$

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.