Dénombrement et combinatoire

Coefficient binomial, arrangements, permutations, formule du binôme.

Formules fondamentales

Coefficient binomial C(n, k): C(n, k) = n! ÷ (k! × (n−k)!) = nombre de façons de choisir k éléments parmi n sans tenir compte de l'ordre. On dit « k parmi n ». Valeurs limites : C(n, 0) = C(n, n) = 1 et C(n, 1) = n.
Arrangements A(n, k) (avec ordre): A(n, k) = n! ÷ (n−k)! = n × (n−1) × … × (n−k+1) = nombre de façons d'ordonner k éléments parmi n. Différent de C(n, k) : ici l'ordre compte. A(n, k) = k! × C(n, k).
Permutations P(n): Nombre d'arrangements de n objets tous distincts : P(n) = n! = n × (n−1) × … × 2 × 1. Exemple : 3! = 6 façons d'ordonner {A, B, C}.

Relation de Pascal: C(n+1, k) = C(n, k−1) + C(n, k). Cette relation permet de construire le triangle de Pascal sans calculer de factorielles. Elle se démontre algébriquement en développant les fractions.
Formule du binôme de Newton: (a + b)ⁿ = Σ_{k=0}^{n} C(n, k) × aⁿ⁻ᵏ × bᵏ. Donne les coefficients des puissances de (a+b). Cas particulier : (1+1)ⁿ = 2ⁿ → la somme des C(n,k) pour k de 0 à n vaut 2ⁿ (nombre de sous-ensembles d'un ensemble à n éléments).

: C(n, k) = C(n, n−k) : choisir k éléments parmi n revient à choisir ceux qu'on laisse (n−k). Utile pour réduire les calculs quand k > n/2.
: Distinguer arrangement (ordre compte, A(n,k)) et combinaison (ordre ne compte pas, C(n,k)). Toujours se demander si l'ordre des choix change le résultat.

Flashcards, mode examen et suivi de progression — gratuit pour commencer.