Relation de récurrence de Pascal nk = n-1k-1 + n-1k
Terminale générale Spé · Mathématiques Spé Terminale
À retenir
• Formule de Pascal : nk = n-1k-1 + n-1k (1 k n - 1). • Interprétation : partition des parties selon qu'elles contiennent ou non un élément distingué x_0. • Permet de calculer les coefficients sans calculatrice par additions itérées.
Le cours
La célèbre formule de Pascal Pour tous entiers naturels n et k tels que 1 k n-1 : nk = n-1k-1 + n-1k Tout coefficient binomial est la somme des deux coefficients situés directement au-dessus de lui dans le triangle de Pascal. Démonstration combinatoire élégante Soit E à n éléments et fixons un élément x_0 E. Pour former une partie à k éléments, il y a deux cas disjoints : 1. La partie contient x_0 : il reste à choisir k-1 éléments parmi les n-1 restants n-1k-1 choix. 2. La partie ne contient pas x_0 : on choisit les k éléments parmi les n-1 restants n-1k choix. Par le principe additif : nk = n-1k-1 + n-1k. Démonstration algébrique Par mise au même dénominateur k!(n-k)! : (n-1)!/(k-1)!(n-k)! + (n-1)!/k!(n-1-k)! = (n-1)! [k + (n-k)]/k!(n-k)! = n!/k!(n-k)! Moteur algorithmique du triangle Cette relation de récurrence permet de calculer de proche en proche tous les coefficients binomiaux par de simples additions, sans aucune multiplication ni division !
Dans ce chapitre
- Arbres de choix, dénombrement intuitif et cardinal d'ensembles de Première
- Réunion, intersection et formule du crible Card(A B) de Première
- Produit cartésien d'ensembles finis et cardinal Card(A B) = n p
- Ensembles disjoints, partitions d'un univers et complémentaire de Première
- Principe multiplicatif pour des choix successifs indépendants
- k-uplets d'un ensemble à n éléments et formule n^k
- Nombre de sous-ensembles d'un ensemble fini et cardinal 2^n
- Permutations d'un ensemble fini à n éléments et factorielle n!
- Dénombrement des anagrammes et permutations d'éléments avec répétition
- Arrangements et tirages ordonnés sans remise A_n^k = n!/(n-k)!
- Combinaisons et tirages non ordonnés sans remise
- Formule du coefficient binomial nk = n!/k!(n-k)!
- Propriétés de symétrie des coefficients binomiaux nk = nn-k
- Relation de récurrence de Pascal nk = n-1k-1 + n-1k
- Construction et lecture du triangle de Pascal
- Formule du binôme de Newton (a+b)^n = _k=0^n nk a^k b^n-k
- Application du binôme au calcul de sommes combinatoires usuelles
- Stratégies de dénombrement par partition en cas disjoints (principe additif)
- Stratégies de dénombrement par passage au complémentaire (événement 'au moins un')
- Dénombrement avec contraintes : fixations d'éléments et ordres partiels
- Arbre de décision et méthodologie pour choisir le modèle de dénombrement adéquat
- Bilan : Synthèse et méthode sur Combinatoire et dénombrement