5
Algèbre et géométrie • Combinatoire et dénombrement
S’entraîner
matT_2400_00_01C
Combinatoire et dénombrement
Autour de la relation de Pascal
Intérêt du sujet • La relation de Pascal se généralise en ce que l’on appelle « relation itérée de Pascal ». On en démontre tout d’abord un cas particulier, puis on démontre le cas général par récurrence. Pour finir, on démontre par dénombrement une autre identité : l’identité de Vandermonde.
Partie A • Un cas particulier
▶ 1. Calculer et . Que remarque-t-on ?
▶ 2. On considère les combinaisons de 3 éléments de l’ensemble à 6 éléments E = {a, b, c, d, e, f}.
a) Combien de ces combinaisons contiennent a ?
b) Parmi celles qui restent, combien y en a-t-il qui contiennent b ?
Parmi celles qui restent, combien y en a-t-il qui contiennent c ?
Parmi celles qui restent, combien y en a-t-il qui contiennent d ?
c) Y en a-t-il d’autres ?
▶ 3. Utiliser la question 2 pour montrer, sans calculs, le résultat remarqué à la question 1.
▶ 4. Utiliser la relation de Pascal pour écrire sous forme d’une somme de combinaisons ; itérer ce procédé avec et et retrouver le résultat remarqué à la question 1.
Partie B • Relation itérée de Pascal
Il s’agit dans cette partie de démontrer que pour tous entiers naturels m et n tels que n ≥ m, on a .
▶ 1. Montrer que l’égalité (1) est vraie pour m = 2 et n = 5.
▶ 2. Montrer que l’égalité (1) est vraie pour n = m.
▶ 3. Démontrer l’égalité (1) par récurrence sur l’entier naturel n.
Partie C • Identité de Vandermonde
On va démontrer que pour tous entiers naturels n, p et q, tels que n ≤ p et n ≤ q, on a :
.
▶ 1. Vérifier l’égalité (2) pour n = 2, p = 3 et q = 4.
▶ 2. Soit n, p et q des entiers naturels tels que n ≤ p et n ≤ q. On considère deux ensembles disjoints A et B comprenant respectivement p et q éléments. On pose C = A ∪ B.
a) Combien d’éléments l’ensemble C contient-il ?
b) Combien y a-t-il de combinaisons d’éléments de C à n éléments ?
c) Soit k un entier naturel tel que k ≤ n. Combien y a-t-il de combinaisons de n éléments de C qui contiennent exactement k éléments de A ?
d) Conclure pour montrer l’identité de Vandermonde.
Les clés du sujet
Partie A
▶ 1. Utilisez la formule du cours permettant de calculer le nombre de combinaisons.
▶ 2. a) Les combinaisons qui contiennent a doivent contenir deux autres éléments.
b) Les combinaisons qui contiennent b mais pas a doivent contenir deux autres éléments ; celles qui contiennent c mais ni a, ni b doivent en contenir deux autres, de même pour celles qui contiennent d mais ni a, ni b, ni c.
Partie B
▶ 3. L’initialisation a été faite pour n = m. Il s’agit de réécrire l’hypothèse de récurrence, en remplaçant n par n + 1 car la récurrence se fait sur n.
Partie C
c) Considérez les combinaisons de k éléments de A et les combinaisons de n - k éléments de B, puis appliquez le principe multiplicatif.
d) Parmi les combinaisons de n éléments de C, il y a celles qui ont 0 élément de A, celles qui ont 1 élément de A, … jusqu’à celles qui ont n éléments de A. Par sommation, on obtient le nombre total de combinaisons.
Partie A • Un cas particulier
▶ 1. Dénombrer et comparer des combinaisons
On a , donc .
D’autre part : .
Donc : .
On remarque que .
▶ 2. a) Distinguer des combinaisons particulières
Les combinaisons de trois éléments de E, qui contiennent a sont formées par a et par deux des cinq éléments de E distincts de a : il y en a .
b) Procéder par étape pour déterminer des combinaisons
Les combinaisons de 3 éléments de E qui contiennent b mais pas a sont formées par b et par deux des quatre éléments de E distincts de a et de b : il y en a .
Les combinaisons de 3 éléments de E, qui contiennent c mais ni a ni b sont formées par c et par deux des trois éléments de E distincts de a, b et c : il y en a .
Les combinaisons de 3 éléments de E, qui contiennent d mais ni a ni b ni c sont formées par d et par les deux éléments de E distincts de a, b, c et d : il y en a .
c) Déterminer des combinaisons par élimination
Une combinaison de 3 éléments de E contient forcément au moins un des quatre éléments a, b, c ou d : on a donc envisagé toutes les possibilités dans les deux questions précédentes, et il n’y a plus d’autres combinaisons possibles.
▶ 3. Utiliser le principe additif
On en déduit que le nombre des combinaisons de trois éléments de E est égal à la somme des nombres de combinaisons trouvés aux questions 2. a) et 2. b) d’où :
.
▶ 4. Itérer une relation
On a, d’après la relation de Pascal, et . D’où .
On a de plus et donc .
Partie B • Relation itérée de Pascal
▶ 1. Calculer une somme
Pour m = 2 et n = 5, le membre de gauche de l’égalité (1) est :
et le membre de droite est
Or, comme on l’a vu dans la partie A :
L’égalité (1) est donc vraie pour et
▶ 2. Démontrer une égalité
Pour n = m, le membre de gauche de l’égalité (1) est :
et le membre de droite est
Or : donc l’égalité (1) est vraie pour .
▶ 3. Rédiger une démonstration par récurrence
Soit m un entier naturel. Démontrons par récurrence que pour tout entier naturel n tel que n ≥ m, on a :
.
Initialisation : D’après la question précédente, l’égalité (1) est vraie pour n = m.
Hérédité : Soit n un entier naturel tel que n ≥ m pour lequel l’égalité (1) est vraie.
On a .
Donc, d’après l’hypothèse de récurrence .
Et, d’après la relation de Pascal .
Le principe de récurrence permet de conclure que pour tout entier naturel n tel que n ≥ m, on a :
.
Partie C • Identité de Vandermonde
▶ 1. Calculer une somme
Pour n = 2, p = 3 et q = 4 le membre de gauche de l’égalité (2) est :
Et le membre de droite est : .
Or, .
On a donc bien .
▶ 2. a) Compter un nombre d’éléments
L’ensemble C a éléments puisque A et B sont disjoints.
b) Dénombrer des combinaisons
Le nombre de combinaisons à n éléments d’un ensemble à p + q éléments est .
c) Utiliser le produit de deux ensembles
Soit k un entier naturel tel que k ≤ n. Une combinaison de n éléments de C qui contient k éléments de A contient n - k éléments de B.
Il y a combinaisons de k éléments de A et combinaisons de n - k éléments de B, soit combinaisons de éléments de qui contiennent exactement éléments de .
d) Manipuler une somme d’éléments
Les combinaisons de n éléments de C contiennent :
soit 0 élément de A, il y en a ;
soit 1 élément de A, il y en a ;
etc. jusqu’à n éléments de A, il y en a .
En sommant toutes ces combinaisons, on obtient donc toutes les combinaisons possibles de n éléments de C.
Autrement dit, en utilisant 2. b) et 2. c), on obtient l’identité de Vandermonde (2) : .