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

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

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

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$ .

Fiche de révisionL’essentiel du chapitre en une page — formules, méthodes et astucesVoir la fiche QCM interactifTeste-toi sur ce chapitre — 22 questions auto-corrigéesCommencer le QCM

Dénombrement

1 · Résumé du cours

1.1 Cardinal et principes de comptage

1.2 ppp-listes (tuples)

1.3 Arrangements

1.4 Permutations

1.5 Combinaisons

1.6 Formule du binôme de Newton

1.7 Comment choisir le bon modèle

2 · Exercices résolus

Exercice 1

Exercice 2

Exercice 3

1.2 $p$ -listes (tuples)