1ʳᵉ Bac · Sciences Maths · Chapitre 13

Dénombrement

1 · Résumé du cours

1.1 Cardinal et principes de comptage

Définition Le cardinal d'un ensemble fini \(E\), noté \(\mathrm{Card}(E)\) (ou \(|E|\)), est le nombre de ses éléments.

Principe additif Si \(A\) et \(B\) sont finis, \(\mathrm{Card}(A\cup B)=\mathrm{Card}(A)+\mathrm{Card}(B)-\mathrm{Card}(A\cap B)\). En particulier, si \(A\cap B=\varnothing\) (parties disjointes) : \(\mathrm{Card}(A\cup B)=\mathrm{Card}(A)+\mathrm{Card}(B)\).

Principe multiplicatif Si une configuration se construit en \(p\) étapes successives, l'étape \(i\) offrant \(n_i\) choix (indépendamment des précédentes), alors le nombre total de configurations est \[n_1\times n_2\times\cdots\times n_p.\] C'est l'arbre des choix : chaque niveau est une étape, chaque branche un choix ; le nombre de feuilles est le produit des nombres de branches.

« ET » multiplie, « OU » additionne Deux réflexes suffisent. Des étapes reliées par un « et » (on choisit ceci puis cela) : on multiplie. Des cas reliés par un « ou » (soit ce cas, soit l'autre, exclusifs) : on additionne.

1.2 \(p\)-listes (tuples)

Définition Une \(p\)-liste (ou \(p\)-uplet) d'un ensemble \(E\) à \(n\) éléments est une suite ordonnée de \(p\) éléments de \(E\), avec répétition possible.

Propriété Le nombre de \(p\)-listes d'un ensemble à \(n\) éléments est \(n^{\,p}\) (par le principe multiplicatif : \(n\) choix à chacune des \(p\) étapes).
Exemple : un code de \(4\) chiffres (de \(0\) à \(9\), répétition permise) : \(10^4=10\,000\) codes.

1.3 Arrangements

Définition Un arrangement de \(p\) éléments parmi \(n\) est une suite ordonnée de \(p\) éléments distincts de \(E\) (ordre important, sans répétition), avec \(0\le p\le n\).

Propriété \[A_n^p=n(n-1)(n-2)\cdots(n-p+1)=\frac{n!}{(n-p)!}.\] Exemple : un podium (or, argent, bronze) parmi \(8\) athlètes : \(A_8^3=8\times7\times6=336\).

1.4 Permutations

Définition Une permutation d'un ensemble à \(n\) éléments est un rangement ordonné de tous ses éléments — c'est un arrangement de \(n\) parmi \(n\).

Propriété \[A_n^n=n!=n(n-1)\cdots2\cdot1\qquad\text{avec la convention }0!=1.\] Exemple : ranger \(5\) livres distincts sur une étagère : \(5!=120\) façons.

1.5 Combinaisons

Définition Une combinaison de \(p\) éléments parmi \(n\) est une partie (sous-ensemble) à \(p\) éléments de \(E\) : l'ordre ne compte pas, sans répétition.

Propriété \[C_n^p=\binom np=\frac{A_n^p}{p!}=\frac{n!}{p!\,(n-p)!}.\]

Ordre : le seul critère qui sépare \(A\) de \(C\) Arrangement et combinaison prennent les mêmes \(p\) éléments distincts ; la différence tient à l'ordre. Comme \(p\) éléments se rangent de \(p!\) façons, chaque combinaison correspond à \(p!\) arrangements : d'où \(C_n^p=\frac{A_n^p}{p!}\). On choisit un comité → combinaison ; on élit un bureau ordonné → arrangement.

Propriétés des combinaisons Pour \(0\le p\le n\) : \[C_n^0=C_n^n=1,\qquad C_n^1=n,\qquad C_n^p=C_n^{\,n-p}\ \ (\text{symétrie}),\] \[C_n^p+C_n^{\,p+1}=C_{n+1}^{\,p+1}\qquad(\text{relation de Pascal}).\]

Triangle de Pascal La relation de Pascal calcule les \(C_n^p\) de proche en proche : chaque terme est la somme des deux situés juste au-dessus. \[\begin{array}{c|ccccc} n\backslash p & 0 & 1 & 2 & 3 & 4\\ \hline 0 & 1 & & & & \\ 1 & 1 & 1 & & & \\ 2 & 1 & 2 & 1 & & \\ 3 & 1 & 3 & 3 & 1 & \\ 4 & 1 & 4 & 6 & 4 & 1\end{array}\]

1.6 Formule du binôme de Newton

Théorème Pour tous réels (ou complexes) \(a,b\) et tout entier \(n\ge1\) : \[(a+b)^n=\sum_{p=0}^{n}C_n^p\,a^{\,n-p}\,b^{\,p}.\] Les coefficients \(C_n^p\) sont exactement la \(n^\text{e}\) ligne du triangle de Pascal.

Exemple \((a+b)^3=C_3^0a^3+C_3^1a^2b+C_3^2ab^2+C_3^3b^3=a^3+3a^2b+3ab^2+b^3.\)

Deux conséquences à connaître En choisissant bien \(a\) et \(b\) : avec \(a=b=1\), \(\sum_{p=0}^{n}C_n^p=2^n\) (nombre total de parties d'un ensemble à \(n\) éléments) ; avec \(a=1,\ b=-1\), \(\sum_{p=0}^{n}(-1)^pC_n^p=0\).

1.7 Comment choisir le bon modèle

Méthode — les deux questions qui décident Face à un problème de comptage, se demander, dans l'ordre : 1. L'ordre compte-t-il ? 2. Peut-on répéter un élément ? \[\begin{array}{|l|c|c|}\hline \text{Ordre / Répétition} & \text{avec répétition} & \text{sans répétition}\\ \hline \text{ordre important} & p\text{-liste : }n^p & \text{arrangement : }A_n^p\\ \hline \text{ordre indifférent} & - & \text{combinaison : }C_n^p\\ \hline\end{array}\] (Le cas « ordre indifférent, avec répétition » n'est pas au programme.)

2 · Exercices résolus

Tirages

Exercice 1

Une urne contient \(10\) boules distinctes. On en tire \(3\). Combien de tirages possibles (a) successifs avec remise, (b) successifs sans remise, (c) simultanés ?

Voir la correction

(a) Ordre important, répétition permise : \(p\)-listes, \(10^3=1000\).

(b) Ordre important, sans répétition : arrangements, \(A_{10}^3=10\times9\times8=720\).

(c) Ordre indifférent, sans répétition : combinaisons, \(C_{10}^3=\frac{10\times9\times8}{3!}=120\). ∎

Bureau & comité

Exercice 2

Une classe compte \(20\) élèves. On choisit un délégué et un délégué adjoint (distincts), puis, séparément, un comité de \(3\) élèves. Combien de possibilités dans chaque cas ?

Voir la correction

Délégué + adjoint : deux rôles ordonnés distincts, donc arrangement \(A_{20}^2=20\times19=380\).

Comité de \(3\) : simple sous-ensemble, donc combinaison \(C_{20}^3=\frac{20\times19\times18}{6}=1140\). ∎

Binôme

Exercice 3

Développer \((x+2)^4\) à l'aide de la formule du binôme.

Voir la correction

\((x+2)^4=\sum_{p=0}^{4}C_4^p\,x^{4-p}2^p=x^4+4\cdot2\,x^3+6\cdot4\,x^2+4\cdot8\,x+16\), soit \[(x+2)^4=x^4+8x^3+24x^2+32x+16.\] ∎

L'essentiel du chapitre

Principes : « et » → on multiplie, « ou » (disjoint) → on additionne.
\(p\)-liste \(n^p\) (ordre + répétition) ; arrangement \(A_n^p=\frac{n!}{(n-p)!}\) (ordre, sans répétition) ; permutation \(n!\) ; combinaison \(C_n^p=\frac{n!}{p!(n-p)!}\) (ni ordre ni répétition).
Combinaisons : symétrie \(C_n^p=C_n^{n-p}\), relation et triangle de Pascal.
Binôme : \((a+b)^n=\sum_{p=0}^{n}C_n^p a^{n-p}b^p\) ; d'où \(\sum C_n^p=2^n\).

QCM interactifTeste-toi sur ce chapitre — 22 questions auto-corrigéesCommencer le QCM