Ch. 21 Dénombrement — récurrence et binôme de Newton — Terminale C Maths

1. Récurrence forte

Principe

Supposer P(k) vraie pour tout k<n, en déduire P(n).

Utile pour suites d'ordre ≥2 et décomposition en facteurs premiers.

2. Arrangements et combinaisons

ObjetFormule Aₙᵖn!/(n−p)! Cₙᵖn!/(p!(n−p)!) Perm. répétitionn!/(n₁!...nₖ!)

3. Binôme de Newton

Identités clés

(a+b)ⁿ=ΣCₙᵏaⁿ⁻ᵏbᵏ. ΣCₙᵏ=2ⁿ. ΣkCₙᵏ=n·2ⁿ⁻¹.

Vandermonde : Σ_{k=0}^r C_m^k·C_n^{r−k}=C_{m+n}^r.

Σ(Cₙᵏ)²=C_{2n}^n.

À retenir

Récurrence forte : hypothèse sur tout k<n
Newton : (a+b)ⁿ=ΣCₙᵏaⁿ⁻ᵏbᵏ
Σ(Cₙᵏ)²=C_{2n}^n (Vandermonde)

Récurrence forte

● Moyen

Montrer que tout entier n≥2 est produit de facteurs premiers.

Correction

Init n=2 premier ✓. Hérédité: si n non premier, n=ab avec 2≤a,b<n. Par hyp. forte a et b sont produits de premiers → n aussi.

Permutations avec répétitions

● Moyen

Anagrammes de COCOA (C×2,O×2,A×1) et de MISSISSIPPI.

Correction

COCOA: 5!/(2!2!1!)=30. MISSISSIPPI: 11!/(1!4!4!2!)=34650.

Binôme de Newton

● Moyen

(1) Terme en x³ dans (2x−1)⁵. (2) Terme en x² dans (1+3x)⁸. (3) ΣC₁₀ᵏ.

Correction

(1) C₅³·8·1=80x³. (2) C₈²·9x²=252x². (3) 2¹⁰=1024.

Vandermonde

● Moyen

Vérifier Vandermonde pour m=n=2, r=2. Puis prouver Σ(Cₙᵏ)²=C_{2n}^n.

Correction

C₂⁰C₂²+C₂¹C₂¹+C₂²C₂⁰=1+4+1=6=C₄² ✓. Vandermonde avec m=n, r=n et symétrie Cₙᵏ=Cₙⁿ⁻ᵏ.

Dénombrement — comités

● Difficile

5H, 6F. (1) Comité de 4. (2) Au moins 2F. (3) Président F.

Correction

(1) C₁₁⁴=330. (2) 330−C₅⁴−C₆¹C₅³=265. (3) 6×C₁₀³=720.

★

Problème de synthèse

● Niveau Bac

On étudie les coefficients binomiaux et leurs propriétés.

Prouver Pascal par les factorielles.
Σ(Cₙᵏ)²=C_{2n}^n par Vandermonde.
Application numérique n=4.
k·Cₙᵏ=n·Cₙ₋₁ᵏ⁻¹ : preuve et application pour ΣkCₙᵏ.
DL de (1+x)^(1/2) à l'ordre 2.
Triangle de Pascal mod 2 : triangle de Sierpiński.

Correction

Cₙ₋₁ᵏ⁻¹+Cₙ₋₁ᵏ = n!/[k!(n−k)!]=Cₙᵏ ✓.
Vandermonde avec m=n, r=n: Σ Cₙᵏ·Cₙⁿ⁻ᵏ=C_{2n}^n. Or Cₙⁿ⁻ᵏ=Cₙᵏ → Σ(Cₙᵏ)²=C_{2n}^n.
n=4: 1+16+36+16+1=70=C₈⁴ ✓.
k·Cₙᵏ=n·Cₙ₋₁ᵏ⁻¹. ΣkCₙᵏ=nΣCₙ₋₁ᵏ⁻¹=n·2ⁿ⁻¹.
(1+x)^(1/2)≈1+x/2−x²/8+o(x²).
Cₙᵏ mod 2 forme le triangle de Sierpiński (auto-similaire).

QCM

10 questions

0Score

0/10Repondues

Q1/10

Récurrence forte : on suppose P(k) pour

Q2/10

Perm. avec répétitions : n!/(n₁!...nₖ!) =

Q3/10

ΣCₙᵏ=

Q4/10

ΣkCₙᵏ=

Q5/10

Σ(Cₙᵏ)²=

Q6/10

Pascal: Cₙᵏ+Cₙᵏ⁺¹=

Q7/10

k·Cₙᵏ=

Q8/10

Vandermonde : Σ C_m^k·C_n^{r−k}=

Q9/10

Anagrammes de AABB=

Q10/10

Terme constant de (2x−1)⁴=

Équations avec combinaisons

● Moyen

Résoudre dans ℕ les équations suivantes.

Cₙ² = 190
2Cₙ² + 6Cₙ³ = 9n
Cₙ¹ + Cₙ² + Cₙ³ = 7n/2
C₂ₙ¹ + C₂ₙ² + C₂ₙ³ = 387n
C_{n+10}^{n+4} = C_{n+10}^{2n−10}

Correction

a) Cₙ²=n(n−1)/2=190 ⟹ n(n−1)=380 ⟹ n²−n−380=0, Δ=1521=39² ⟹ n=(1+39)/2=20.
b) 2Cₙ²+6Cₙ³=n(n−1)+n(n−1)(n−2)=n(n−1)²=9n. Comme n≠0 : (n−1)²=9 ⟹ n=4 (n=−2 rejeté).
c) En réduisant au même dénominateur : Cₙ¹+Cₙ²+Cₙ³=(n³+5n)/6. L'équation devient n³+5n=21n ⟹ n²=16 ⟹ n=4.
d) Avec m=2n, Cₘ¹+Cₘ²+Cₘ³=(m³+5m)/6 (formule du c). On obtient (8n³+10n)/6=387n ⟹ 4n³+5n=1161n ⟹ n²=289 ⟹ n=17.
e) Par symétrie Cₖᵖ=Cₖᵏ⁻ᵖ avec k=n+10 : soit n+4=2n−10 (⟹ n=14), soit (n+4)+(2n−10)=n+10 (⟹ n=8). Les deux valeurs vérifient 2n−10≥0 : n=8 ou n=14.

Puissances et racine carrée — binôme de Newton

● Facile

Écrire sous la forme a+b√3, où a et b sont des entiers, les nombres suivants.

(3−√3)⁴
(1+2√3)⁵
(2√3−5)³

Correction

En développant avec la formule du binôme (n=4), les termes d'exposant pair en √3 sont rationnels, ceux d'exposant impair donnent le coefficient de √3 : (3−√3)⁴ = 252 − 144√3.
De même, en développant Σ C₅ᵏ(2√3)ᵏ : (1+2√3)⁵ = 841 + 538√3.
Avec a=2√3, b=5 et (a−b)³=a³−3a²b+3ab²−b³ : 24√3−180+150√3−125, soit (2√3−5)³ = −305 + 174√3.

Puissances de nombres complexes — binôme de Newton

● Moyen

Développer et simplifier les expressions suivantes.

(1−i)⁴
(1+2i)⁵
(1+2j)⁶, où j=e^(i2π/3)

Correction

(1−i)²=1−2i+i²=−2i, donc (1−i)⁴=(−2i)²=4i²=−4.
En développant Σ C₅ᵏ(2i)ᵏ : partie réelle 1−40+80=41, partie imaginaire 10−80+32=−38, soit (1+2i)⁵ = 41−38i.
j vérifie j³=1 et 1+j+j²=0. En développant Σ C₆ᵏ2ᵏjᵏ et en regroupant selon jᵏ mod 3, on obtient 225+252j+252j²=225+252(j+j²)=225−252=−27 (vérification directe : 1+2j=i√3, donc (1+2j)⁶=(i√3)⁶=i⁶·27=−27).

Circuit touristique — arrangements

● Facile

Une compagnie aérienne organise un circuit ABIDJAN – ABIDJAN, via les villes de COTONOU, DAKAR, LIBREVILLE, NIAMEY et YAOUNDÉ.

Combien y a-t-il d'itinéraires possibles ?
Combien de ces itinéraires ont pour troisième étape la ville de NIAMEY ?
Pour combien de ces itinéraires l'étape de DAKAR précède-t-elle celle de YAOUNDÉ ?

Correction

Un itinéraire correspond à un ordre des 5 villes intermédiaires : 5! = 120 itinéraires.
NIAMEY fixée en 3ᵉ position, les 4 autres villes se permutent librement : 4! = 24 itinéraires.
Par symétrie, DAKAR précède YAOUNDÉ dans exactement la moitié des permutations : 120/2 = 60 itinéraires.

Coloriage d'un drapeau — principe multiplicatif

● Facile

On dispose de 4 couleurs pour colorier les 5 bandes verticales d'un drapeau. Combien de drapeaux différents peut-on obtenir si deux bandes voisines ne peuvent avoir la même couleur ?

Correction

1ʳᵉ bande : 4 choix. Chaque bande suivante doit différer de sa voisine précédente : 3 choix à chaque fois (bandes 2 à 5). Nombre total : 4×3×3×3×3 = 4×3⁴ = 324 drapeaux.

Identité télescopique de factorielles

● Moyen

Soit n un entier naturel non nul. Démontrer que :

1/(n−1)! − 1/n! + 1/(n+1)! = n²/(n+1)!

Correction

En réduisant au même dénominateur (n+1)! = (n+1)·n·(n−1)! : 1/(n−1)! = n(n+1)/(n+1)! et 1/n! = (n+1)/(n+1)!.

Le numérateur devient n(n+1) − (n+1) + 1 = (n+1)(n−1) + 1 = n²−1+1 = n². D'où l'égalité annoncée. ✓

Récurrence : somme Σp·p!

● Moyen

Démontrer, par récurrence sur n, que :

∀n∈ℕ*, Σ (p=1 à n) p·p! = (n+1)! − 1

Correction

Initialisation (n=1) : 1·1!=1 et (1+1)!−1=2−1=1. ✓
Hérédité : on suppose Σ(p=1 à n) p·p! = (n+1)!−1. Alors Σ(p=1 à n+1) p·p! = (n+1)!−1+(n+1)(n+1)! = (n+1)!(1+n+1)−1 = (n+1)!(n+2)−1 = (n+2)!−1, ce qui est la propriété au rang n+1.
Conclusion : la propriété est vraie pour tout n∈ℕ*.

Identité p·Cₙᵖ = n·Cₙ₋₁ᵖ⁻¹

● Difficile

Démontrer que pour tous entiers naturels n et p tels que 1≤p≤n, on a : p·Cₙᵖ = n·Cₙ₋₁ᵖ⁻¹. En déduire que pour tout entier naturel n non nul : Σ(p=1 à n) p·Cₙᵖ = n·2ⁿ⁻¹.

Correction

p·Cₙᵖ = p·n!/(p!(n−p)!) = n!/((p−1)!(n−p)!) = n·(n−1)!/((p−1)!(n−p)!) = n·Cₙ₋₁ᵖ⁻¹.
Donc Σ(p=1 à n) p·Cₙᵖ = n·Σ(p=1 à n) Cₙ₋₁ᵖ⁻¹ = n·Σ(k=0 à n−1) Cₙ₋₁ᵏ (k=p−1) = n·2ⁿ⁻¹.

Développement de (1+x)ⁿ et sommes remarquables

● Difficile

Développer (1+x)ⁿ (n∈ℕ*).
En déduire la valeur des sommes suivantes.
1. Cₙ⁰+Cₙ¹+...+Cₙⁿ
2. Cₙ⁰−Cₙ¹+...+(−1)ⁿCₙⁿ
3. Cₙ⁰+2Cₙ¹+...+2ⁿCₙⁿ
On suppose n=2k. Calculer C₂ₖ⁰+C₂ₖ²+...+C₂ₖ²ᵏ.
On suppose n=2k+1. Calculer C₂ₖ₊₁⁰+C₂ₖ₊₁²+...+C₂ₖ₊₁²ᵏ.

Correction

(1+x)ⁿ = Σ(p=0 à n) Cₙᵖxᵖ.
1. x=1 : (1+1)ⁿ=2ⁿ = ΣCₙᵖ.
2. x=−1 : (1−1)ⁿ=0 = Σ(−1)ᵖCₙᵖ.
3. x=2 : (1+2)ⁿ=3ⁿ = Σ2ᵖCₙᵖ.
D'après 2)a) et 2)b), la somme des termes de rang pair et celle des termes de rang impair vérifient : somme_paire+somme_impaire=2ⁿ et somme_paire−somme_impaire=0 (pour n≥1), donc somme_paire=somme_impaire=2ⁿ⁻¹. Pour n=2k (k≥1) : C₂ₖ⁰+C₂ₖ²+...+C₂ₖ²ᵏ = 2²ᵏ⁻¹.
Pour n=2k+1 (impair), la même relation donne somme_paire=2ⁿ⁻¹=2²ᵏ, donc C₂ₖ₊₁⁰+C₂ₖ₊₁²+...+C₂ₖ₊₁²ᵏ = 2²ᵏ.

Double dénombrement : Σ(Cₙᵖ)² = C_{2n}^n

● Difficile

Une urne contient n boules rouges et n boules blanches. En calculant de deux manières le nombre de tirages de n boules que l'on peut effectuer dans cette urne, démontrer que : Σ(p=0 à n) (Cₙᵖ)² = C_{2n}^n.

Correction

1ʳᵉ méthode : le nombre de façons de choisir n boules parmi les 2n boules de l'urne est directement C_{2n}^n.
2ᵉ méthode : on classe les tirages selon leur nombre p de boules rouges (0≤p≤n). Il faut choisir p boules rouges parmi n (Cₙᵖ façons) et n−p boules blanches parmi n (Cₙⁿ⁻ᵖ=Cₙᵖ façons), soit (Cₙᵖ)² tirages pour chaque valeur de p. En sommant sur les cas disjoints p=0,...,n, on obtient Σ(p=0 à n)(Cₙᵖ)² tirages au total.
Les deux méthodes comptent le même ensemble de tirages, d'où Σ(p=0 à n)(Cₙᵖ)² = C_{2n}^n.

Identité de Vandermonde généralisée

● Difficile

Pour tout entier naturel n, on pose Rₙ(x)=(x+1)ⁿ.

Soient n, p, q trois entiers naturels tels que n≤p+q. À l'aide de la formule du binôme, déterminer le coefficient de xⁿ dans le développement de chacun des membres de l'égalité R_{p+q}=Rₚ·R_q.
En déduire que pour tout triplet (n;p;q) d'entiers naturels tel que n≤p+q, on a : C_{p+q}^n = Σ(k=0 à n) C_p^k·C_q^{n−k}.

Correction

D'une part, R_{p+q}(x)=(x+1)^(p+q)=Σ(m=0 à p+q) C_{p+q}^m xᵐ : le coefficient de xⁿ est C_{p+q}^n. D'autre part, Rₚ(x)·R_q(x)=(Σᵢ C_p^i xⁱ)(Σⱼ C_q^j xʲ) ; le coefficient de xⁿ dans ce produit est Σ(k=0 à n) C_p^k·C_q^{n−k} (les termes où k>p ou n−k>q sont nuls car les combinaisons correspondantes valent 0).
R_{p+q}=Rₚ·R_q est une identité polynomiale : les coefficients de xⁿ de chaque membre sont donc égaux, ce qui donne C_{p+q}^n = Σ(k=0 à n) C_p^k·C_q^{n−k} (identité de Vandermonde généralisée).

Coefficient central de (x+1)²ⁿ — deux expressions

● Difficile

Soit P le polynôme défini par P(x)=(x+1)²ⁿ.

Quel est le coefficient aₙ du terme de degré n de P ?
En appliquant la formule du binôme à l'égalité P(x)=(x+1)ⁿ(x+1)ⁿ, trouver une autre expression de aₙ.
En déduire que : ∀n∈ℕ*, Σ(k=0 à n) k(Cₙᵏ)² = (n/2)·C_{2n}^n.

Correction

P(x)=(x+1)²ⁿ=Σ C_{2n}^m xᵐ, donc aₙ = C_{2n}^n.
En développant (x+1)ⁿ(x+1)ⁿ = (ΣCₙⁱxⁱ)(ΣCₙʲxʲ), le coefficient de xⁿ est Σ(k=0 à n) Cₙᵏ·Cₙⁿ⁻ᵏ = Σ(k=0 à n)(Cₙᵏ)² (car Cₙⁿ⁻ᵏ=Cₙᵏ). Donc aₙ = Σ(k=0 à n)(Cₙᵏ)², d'où l'on retrouve Σ(Cₙᵏ)² = C_{2n}^n.
Posons S=Σ(k=0 à n) k(Cₙᵏ)². Le changement d'indice k→n−k et la symétrie Cₙᵏ=Cₙⁿ⁻ᵏ donnent S = Σ(k=0 à n)(n−k)(Cₙᵏ)² = n·Σ(Cₙᵏ)² − S = n·C_{2n}^n − S. D'où 2S = n·C_{2n}^n, soit S = (n/2)·C_{2n}^n.

Somme Σk²Cₙᵏ = n(n+1)·2ⁿ⁻²

● Difficile

Démontrer que : ∀n∈ℕ*, Σ(k=1 à n) k²Cₙᵏ = n(n+1)·2ⁿ⁻².

Correction

D'après l'identité kCₙᵏ=nCₙ₋₁ᵏ⁻¹ (voir Approfondissement, ex. 3), on a k²Cₙᵏ = k·(kCₙᵏ) = n·k·Cₙ₋₁ᵏ⁻¹.
En appliquant à nouveau la même identité (à l'ordre n−1) avec k=(k−1)+1 : k·Cₙ₋₁ᵏ⁻¹ = (n−1)Cₙ₋₂ᵏ⁻² + Cₙ₋₁ᵏ⁻¹.
D'où k²Cₙᵏ = n(n−1)Cₙ₋₂ᵏ⁻² + nCₙ₋₁ᵏ⁻¹. En sommant pour k=1,...,n : Σk²Cₙᵏ = n(n−1)·2ⁿ⁻² + n·2ⁿ⁻¹ = n·2ⁿ⁻²[(n−1)+2] = n(n+1)·2ⁿ⁻².
Vérification pour n=3 : 1²C₃¹+2²C₃²+3²C₃³ = 3+12+9 = 24 = 3×4×2¹ = 24. ✓

Répartitions de boules dans des tiroirs

● Moyen

On répartit n boules numérotées dans k tiroirs numérotés. Combien y a-t-il de répartitions possibles ?
On répartit n boules identiques dans k tiroirs numérotés. Combien y a-t-il de répartitions possibles ?
Application : l'espace étant muni du repère (O,i,j,k), combien y a-t-il de points du plan d'équation x+y+z−20=0 à coordonnées entières positives ou nulles ?

Correction

Chaque boule, étant numérotée (distincte), peut être placée indépendamment dans l'un quelconque des k tiroirs : il y a kⁿ répartitions possibles.
Les boules étant identiques, une répartition revient à choisir les nombres x₁,...,x_k de boules dans chaque tiroir avec x₁+...+x_k=n, xᵢ≥0 : c'est le problème classique des « étoiles et barres ». Il y a C_{n+k−1}^{k−1} répartitions possibles.
Chercher les points (x;y;z) à coordonnées entières ≥0 tels que x+y+z=20 revient à répartir n=20 unités dans k=3 « tiroirs » (les variables x, y, z). Il y a donc C_{20+3−1}^{3−1} = C_{22}^{2} = 22×21/2 = 231 points.

Trois termes consécutifs de Pascal en progression arithmétique

● Difficile

Olympiades nationales de mathématiques, Burkina Faso 1994.

Dans le triangle de Pascal, trouver 4 lignes telles que sur chacune d'elles on trouve trois termes consécutifs formant une suite arithmétique.

Correction

Sur la ligne n, cherchons trois termes consécutifs Cₙᵏ⁻¹, Cₙᵏ, Cₙᵏ⁺¹ tels que 2Cₙᵏ = Cₙᵏ⁻¹+Cₙᵏ⁺¹. En posant m=n−k et en utilisant les rapports Cₙᵏ/Cₙᵏ⁻¹=(n−k+1)/k et Cₙᵏ⁺¹/Cₙᵏ=(n−k)/(k+1), la condition se ramène à (k−m)² = n+2.
n+2 doit donc être un carré parfait : n+2=t². Les quatre plus petites valeurs exploitables (avec 1≤k≤n−1) sont t=3,4,5,6, soit n = 7, 14, 23, 34.
Vérifications : ligne n=7 (k=1) : 7, 21, 35 (2×21=42=7+35 ✓) ; ligne n=14 (k=4) : 1001, 2002, 3003 (2×2002=4004=1001+3003 ✓) ; ligne n=23 (k=8) : 490 314, 817 190, 1 144 066 (2×817190=1 634 380 ✓) ; ligne n=34 (k=13) : 927 983 760, 1 391 975 640, 1 855 967 520 (2×1 391 975 640=2 783 951 280 ✓).