Mathématiques — LFIA Agadir

Principes de dénombrement

DéfinitionPrincipe additif

Si deux expériences incompatibles (disjointes) ont respectivement

p

et

q

issues possibles,

alors l'expérience globale « l'une ou l'autre » a

p + q

issues possibles.

Exemple : Choisir un entier entre 1 et 5 ou une lettre parmi

\{a, b, c\}

→

5 + 3 = 8

choix.

DéfinitionPrincipe multiplicatif (des choix successifs)

Si une expérience s'effectue en deux étapes indépendantes ayant respectivement

p

et

q

issues,

alors l'expérience globale a

p \times q

issues possibles.

Généralisation :

k

étapes avec

n_1, n_2, \ldots, n_k

issues →

n_1 \times n_2 \times \cdots \times n_k

issues au total.

Exemple : Un menu avec 3 entrées, 4 plats et 2 desserts →

3 \times 4 \times 2 = 24

repas possibles.

ExempleApplication directe

Combien de mots de 3 lettres peut-on former avec l'alphabet $\{a, b, c, d\}$ ?

Avec répétition : chaque position a 4 choix → $4^3 = 64$ mots.

Sans répétition : $4 \times 3 \times 2 = 24$ mots (chaque lettre utilisée au plus une fois).

$k$-uplets, arrangements et permutations

Définition$k$-uplets d\'un ensemble

Un $k$ -uplet d'un ensemble

E

à

n

éléments est une liste ordonnée de

k

éléments de

E

(répétitions possibles).

Le nombre de

k

-uplets de

E

est

n^k

.

DéfinitionPermutations

Une permutation d'un ensemble à

n

éléments est un

n

-uplet sans répétition, c'est-à-dire un rangement de tous les éléments.

Le nombre de permutations de

n

éléments est

n! = n \times (n-1) \times \cdots \times 2 \times 1

.

Convention :

0! = 1

.

ExempleFactorielles

$1! = 1, \quad 2! = 2, \quad 3! = 6, \quad 4! = 24, \quad 5! = 120, \quad 6! = 720, \quad 10! = 3\,628\,800$ .

Exemple : De combien de façons peut-on ranger 5 livres sur une étagère ? Réponse : $5! = 120$ .

AttentionCroissance de $n!$

La factorielle croit extrêmement vite :

20! \approx 2{,}4 \times 10^{18}

. Pour

n \geq 13

,

n!

dépasse la capacité des calculatrices standard.

C'est pourquoi on préfère souvent travailler avec les combinaisons plutôt qu'avec les factorielles directement.

Combinaisons

DéfinitionCombinaison — définition

Une combinaison de

k

éléments parmi

n

est un sous-ensemble (non ordonné, sans répétition) de taille

k

extrait d'un ensemble à

n

éléments.

Le nombre de telles combinaisons est noté

\dbinom{n}{k}

(lu «

k

parmi

n

»).

ThéorèmeFormule des combinaisons

\binom{n}{k} = \frac{n!}{k!\,(n-k)!}

Propriétés immédiates :

\binom{n}{0} = \binom{n}{n} = 1

\quad

(un seul choix : prendre rien ou tout).

\binom{n}{1} = n

\quad

(autant de singletons que d'éléments).

\binom{n}{k} = \binom{n}{n-k}

\quad

(symétrie : choisir

k

éléments revient à en exclure

n-k

).

ExempleCalculs de combinaisons

$\binom{5}{2} = \dfrac{5!}{2!\cdot 3!} = \dfrac{5 \times 4}{2 \times 1} = 10$

$\binom{6}{3} = \dfrac{6!}{3!\cdot 3!} = \dfrac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$

Application : Au loto (6 numéros tirés parmi 49), le nombre de grilles possibles est $\binom{49}{6} = 13\,983\,816$ .

Remarque

Différence fondamentale : choisir 2 lettres parmi $\{a,b,c\}$ dans l'ordre → $3 \times 2 = 6$ façons (arrangements).

Choisir 2 lettres sans ordre (combinaisons) → $\binom{3}{2} = 3$ façons : $\{a,b\}$ , $\{a,c\}$ , $\{b,c\}$ .

Triangle de Pascal et coefficients binomiaux

ThéorèmeFormule de Pascal (démonstration exigée)

\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}

Preuve algébrique :

\binom{n}{k} + \binom{n}{k+1} = \dfrac{n!}{k!(n-k)!} + \dfrac{n!}{(k+1)!(n-k-1)!}

= \dfrac{n!(k+1)}{(k+1)!(n-k)!} + \dfrac{n!(n-k)}{(k+1)!(n-k)!} = \dfrac{n![(k+1)+(n-k)]}{(k+1)!(n-k)!} = \dfrac{n!(n+1)}{(k+1)!(n-k)!} = \binom{n+1}{k+1}

.

\square

Preuve combinatoire : Parmi

n+1

objets (dont un distingué

*

), les sous-ensembles de taille

k+1

soit contiennent

*

(

\binom{n}{k}

façons), soit ne le contiennent pas (

\binom{n}{k+1}

façons).

\square

ExempleTriangle de Pascal (premières lignes)

| $n \backslash k$ | 0 | 1 | 2 | 3 | 4 | 5 |

|---|---|---|---|---|---|---|

| 0 | 1 | | | | | |

| 1 | 1 | 1 | | | | |

| 2 | 1 | 2 | 1 | | | |

| 3 | 1 | 3 | 3 | 1 | | |

| 4 | 1 | 4 | 6 | 4 | 1 | |

| 5 | 1 | 5 | 10 | 10 | 5 | 1 |

Chaque coefficient est la somme des deux au-dessus (formule de Pascal).

ThéorèmeSomme des coefficients binomiaux (démonstration exigée)

\sum_{k=0}^{n} \binom{n}{k} = 2^n

Preuve algébrique : En développant

(1+1)^n

par le binôme de Newton :

(1+1)^n = \displaystyle\sum_{k=0}^{n} \binom{n}{k} 1^k \cdot 1^{n-k} = \sum_{k=0}^{n} \binom{n}{k}

. Or

(1+1)^n = 2^n

.

\square

Preuve combinatoire : Un ensemble à

n

éléments a autant de sous-ensembles que de listes binaires de longueur

n

(inclure ou non chaque élément), soit

2^n

. Et la somme

\sum_{k} \binom{n}{k}

compte ces sous-ensembles par taille.

\square

Premières applications aux probabilités

PropriétéDénombrement et probabilité sur un espace équiprobable

Sur un univers

\Omega

à

n

éléments équiprobables, la probabilité d'un événement

A

est :

P(A) = \frac{\text{Card}(A)}{\text{Card}(\Omega)} = \frac{\text{nombre de cas favorables}}{\text{nombre de cas possibles}}

Les outils de dénombrement (

k

-uplets, permutations, combinaisons) permettent de calculer numérateur et dénominateur.

ExempleApplication — tirage dans une urne

Une urne contient 5 boules rouges et 3 boules bleues. On tire 3 boules simultanément.

1. Combien de tirages possibles ? $\binom{8}{3} = 56$ .

2. Combien de tirages avec exactement 2 rouges et 1 bleue ?

Choisir 2 rouges parmi 5 : $\binom{5}{2} = 10$ . Choisir 1 bleue parmi 3 : $\binom{3}{1} = 3$ .

Par le principe multiplicatif : $10 \times 3 = 30$ tirages favorables.

3. Probabilité : $P = \dfrac{30}{56} = \dfrac{15}{28} \approx 0{,}536$ .

Remarque

La loi binomiale (Séquence 9) généralisera ce type de calcul : on verra que $P(X=k) = \binom{n}{k}p^k(1-p)^{n-k}$ .

Le coefficient $\binom{n}{k}$ comptera exactement le nombre de chemins favorables dans un arbre de probabilités.

Combinatoire et dénombrement

A –Principes de dénombrement

B –$k$-uplets, arrangements et permutations

C –Combinaisons

D –Triangle de Pascal et coefficients binomiaux

E –Premières applications aux probabilités

Principes de dénombrement

$k$-uplets, arrangements et permutations

Combinaisons

Triangle de Pascal et coefficients binomiaux

Premières applications aux probabilités