Combinatoire et dénombrement

I. Principes fondamentaux

1. Principe additif

Principe additif

A

B

sont deux ensembles finis disjoints (

A \cap B = \emptyset

), alors :

card (A \cup B) = card (A) + card (B)

Généralisation : Si

A_{1}, A_{2}, \dots, A_{k}

sont des ensembles finis deux à deux disjoints, alors :

card (A_{1} \cup A_{2} \cup \dots \cup A_{k}) = card (A_{1}) + card (A_{2}) + \dots + card (A_{k})

Exemple

On lance un dé à 6 faces. Soit

A = {2, 4, 6}

(faces paires) et

B = {1}

.

Les ensembles

A

B

sont disjoints car

A \cap B = \emptyset

.

Donc

card (A \cup B) = card (A) + card (B) = 3 + 1 = 4

2. Principe multiplicatif

Principe multiplicatif

Si une expérience se décompose en deux étapes successives, la première ayant

p

issues possibles et la seconde ayant

q

issues possibles, alors le nombre total d'issues est :

p \times q

Généralisation : Pour

k

étapes successives ayant respectivement

n_{1}, n_{2}, \dots, n_{k}

issues, le nombre total d'issues est :

n_{1} \times n_{2} \times \dots \times n_{k}

Démonstration via le produit cartésien

Le produit cartésien de deux ensembles

A

B

est :

A \times B = {(a, b) ∣ a \in A et b \in B}

Chaque élément de

A

peut être associé à chaque élément de

B

, ce qui donne :

card (A \times B) = card (A) \times card (B)

Exemple

Un restaurant propose 3 entrées et 4 plats principaux. Un menu se compose d'une entrée et d'un plat.

Nombre de menus possibles

= 3 \times 4 = 12

3. Inclusion-exclusion

Formule d'inclusion-exclusion (deux ensembles)

Pour deux ensembles finis

A

B

quelconques :

card (A \cup B) = card (A) + card (B) - card (A \cap B)

Démonstration

On décompose

A \cup B

en trois parties disjointes :

•

A ∖ B

: éléments dans

A

mais pas dans

B

•

A \cap B

: éléments dans

A

et dans

B

•

B ∖ A

: éléments dans

B

mais pas dans

A

Donc

card (A \cup B) = card (A ∖ B) + card (A \cap B) + card (B ∖ A)

.

Or

card (A) = card (A ∖ B) + card (A \cap B)

card (B) = card (B ∖ A) + card (A \cap B)

.

En substituant :

card (A \cup B) = card (A) + card (B) - card (A \cap B)

Exemple

Dans une classe de 35 élèves, 20 étudient l'anglais, 18 l'espagnol, et 8 étudient les deux langues.

Nombre d'élèves qui étudient au moins une langue :

card (A \cup E) = 20 + 18 - 8 = 30

Donc

35 - 30 = 5

élèves n'étudient aucune de ces deux langues.

Formule pour trois ensembles

Pour trois ensembles finis

A

B

C

card (A \cup B \cup C) = card (A) + card (B) + card (C) - card (A \cap B) - card (A \cap C) - card (B \cap C) + card (A \cap B \cap C)

II. $p$ -listes ( $p$ -uplets)

1. $p$ -listes avec répétition

p

-liste avec répétition

Soit

E

un ensemble à

n

éléments. Une $p$ -liste avec répétition de

E

est un

p

-uplet

(x_{1}, x_{2}, \dots, x_{p})

où chaque

x_{i} \in E

.

• L'ordre compte :

(a, b) \neq = (b, a)

• Les répétitions sont autorisées :

(a, a, b)

est valide

Nombre de

p

-listes avec répétition

Le nombre de

p

-listes d'un ensemble à

n

éléments est :

n^{p}

Démonstration

Par le principe multiplicatif : pour chaque position du

p

-uplet, on a

n

choix possibles. Les choix sont indépendants.

Donc le nombre total est

p fois n \times n \times \dots \times n = n^{p}

Exemple

Un code PIN est composé de 4 chiffres (de 0 à 9). Chaque chiffre peut être répété.

C'est une 4-liste avec répétition de

E = {0, 1, \dots, 9}

(

n = 10

).

Nombre de codes PIN possibles

= 1 0^{4} = 10000

2. $p$ -listes sans répétition (arrangements)

Arrangement (

p

-liste sans répétition)

Soit

E

un ensemble à

n

éléments. Un arrangement de

p

éléments de

E

est un

p

-uplet

(x_{1}, x_{2}, \dots, x_{p})

où tous les

x_{i}

sont distincts.

• L'ordre compte
• Les répétitions sont interdites
• On a nécessairement

p \leq n

Nombre d'arrangements

Le nombre d'arrangements de

p

éléments parmi

n

est :

A_{n}^{p} = \frac{n !}{( n - p )!} = n (n - 1) (n - 2) \dots (n - p + 1)

C'est le produit de

p

entiers consécutifs décroissants à partir de

n

Démonstration

Par le principe multiplicatif :

• 1ère position :

n

choix
• 2ème position :

n - 1

choix (un élément déjà utilisé)
• 3ème position :

n - 2

choix
•

⋮

•

p

-ème position :

n - p + 1

choix

Donc

A_{n}^{p} = n (n - 1) (n - 2) \dots (n - p + 1) = \frac{n !}{( n - p )!}

Exemple

De combien de façons peut-on former un podium (or, argent, bronze) à partir de 10 athlètes ?

C'est un arrangement de

p = 3

parmi

n = 10

(l'ordre compte : or ≠ argent).

A_{10}^{3} = 10 \times 9 \times 8 = 720

Remarque

La notation

A_{n}^{p}

n'est pas au programme officiel du baccalauréat. Elle est cependant très pratique et largement utilisée.

III. Permutations

Permutation

Une permutation d'un ensemble

E

n

éléments est une liste ordonnée de tous les éléments de

E

.

C'est le cas particulier d'un arrangement avec

p = n

: on choisit tous les éléments et l'ordre compte.

Nombre de permutations

Le nombre de permutations d'un ensemble à

n

éléments est :

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

Convention :

0! = 1

Démonstration

C'est le cas

p = n

de la formule des arrangements :

A_{n}^{n} = \frac{n !}{( n - n )!} = \frac{n !}{0 !} = \frac{n !}{1} = n!

Exemple

De combien de façons peut-on ranger 5 livres sur une étagère ?

Il s'agit de permuter 5 éléments :

5! = 5 \times 4 \times 3 \times 2 \times 1 = 120

Méthode : reconnaître une permutation

Question clé : « De combien de façons peut-on ordonner tous les éléments d'un ensemble ? »

Si la réponse est « oui, on ordonne tous les éléments » → penser à

n!

IV. Combinaisons

1. Définition et formule

Combinaison

Soit

E

un ensemble à

n

éléments. Une combinaison de

p

éléments de

E

est un sous-ensemble de

E

ayant exactement

p

éléments.

• L'ordre ne compte pas :

{a, b, c} = {c, a, b}

• Pas de répétition : chaque élément est choisi au plus une fois
• On a nécessairement

0 \leq p \leq n

Nombre de combinaisons

Le nombre de combinaisons de

p

éléments parmi

n

est le coefficient binomial :

(p n) = \frac{n !}{p ! ( n - p )!}

Démonstration

Chaque combinaison de

p

éléments peut être ordonnée de

p!

façons, donnant ainsi un arrangement.

Donc : nombre d'arrangements

=

nombre de combinaisons

\times

p!

A_{n}^{p} = (p n) \times p!

D'où :

(p n) = \frac{A _{n}^{p}}{p !} = \frac{n !}{p ! ( n - p )!}

Exemple

On choisit 3 délégués parmi 10 élèves (l'ordre ne compte pas).

(3 10) = \frac{10 !}{3 ! \times 7 !} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120

Astuce de calcul

Pour calculer

(p n)

, on écrit

p

facteurs au numérateur en descendant depuis

n

, puis on divise par

p!

(p n) = \frac{n \times ( n - 1 ) \times \dots \times ( n - p + 1 ) p facteurs}{p !}

Exemple :

(4 12) = \frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} = \frac{11 880}{24} = 495

2. Propriétés des coefficients binomiaux

Valeurs particulières

Pour tout entier

n \geq 0

(0 n) = (n n) = 1 et (1 n) = n

Symétrie

Pour tous entiers

0 \leq p \leq n

(p n) = (n - p n)

Démonstration de la symétrie

(n - p n) = \frac{n !}{( n - p )! [ n - ( n - p )]!} = \frac{n !}{( n - p )! p !} = (p n)

Interprétation : Choisir

p

éléments à prendre parmi

n

, c'est la même chose que choisir

n - p

éléments à laisser.

3. Triangle de Pascal

Formule de Pascal

Pour tous entiers

1 \leq p \leq n - 1

(p n) = (p - 1 n - 1) + (p n - 1)

Démonstration combinatoire

On fixe un élément

a

dans l'ensemble

E

n

éléments. Les combinaisons de

p

éléments parmi

n

se répartissent en deux catégories disjointes :

• Celles qui contiennent

a

: il reste à choisir

p - 1

éléments parmi les

n - 1

restants →

(p - 1 n - 1)

• Celles qui ne contiennent pas

a

: il faut choisir

p

éléments parmi les

n - 1

restants →

(p n - 1)

Par le principe additif :

(p n) = (p - 1 n - 1) + (p n - 1)

Triangle de Pascal (lignes

n = 0

n = 6

) :

n = 0

1

n = 1

11

n = 2

121

n = 3

1331

n = 4

14641

n = 5

15101051

n = 6

1615201561

Chaque nombre est la somme des deux nombres situés au-dessus de lui.

4. Binôme de Newton

Formule du binôme de Newton

Pour tous réels

a, b

et tout entier

n \geq 0

(a + b)^{n} = k = 0 \sum n (k n) a^{n - k} b^{k}

Idée de la démonstration

On développe le produit

(a + b)^{n} = n facteurs (a + b) (a + b) \dots (a + b)

.

Dans chaque facteur, on choisit

a

b

. Un terme

a^{n - k} b^{k}

apparaît chaque fois qu'on choisit

b

exactement

k

fois parmi les

n

facteurs.

Le nombre de façons de choisir ces

k

facteurs est

(k n)

Cas particuliers importants

En posant

a = b = 1

k = 0 \sum n (k n) = 2^{n}

La somme de tous les coefficients binomiaux de la ligne $n$ vaut $2^{n}$ .

En posant

a = 1, b = - 1

k = 0 \sum n (- 1)^{k} (k n) = 0

La somme alternée des coefficients binomiaux est nulle.

Exemple

Développer

(2 + x)^{4}

(2 + x)^{4} = k = 0 \sum 4 (k 4) 2^{4 - k} x^{k}

= (0 4) 2^{4} + (1 4) 2^{3} x + (2 4) 2^{2} x^{2} + (3 4) 2 x^{3} + (4 4) x^{4}

= 16 + 32 x + 24 x^{2} + 8 x^{3} + x^{4}

V. Méthodes et stratégies de dénombrement

1. Schéma de décision

Les 3 questions à se poser

Face à un problème de dénombrement, se poser dans l'ordre :

Q1. L'ordre compte-t-il ?
• OUI si on parle de : classement, rang, podium, code, mot, numéro, position
• NON si on parle de : groupe, équipe, comité, lot, main, délégation

Q2. Les répétitions sont-elles possibles ?
• OUI → éléments réutilisables
• NON → éléments tous distincts

Q3. Prend-on tous les éléments ou une partie ?
• Tous les

n

→ permutation
•

p

parmi

n

→ arrangement ou combinaison

Arbre de décision :

L'ordre compte ?
• Non →

(p n)

(combinaison)
• Oui → Répétitions possibles ?

- Oui →

n^{p}

(

p

-liste avec répétition)

- Non → Tous les éléments ?

- Oui →

n!

(permutation)

- Non →

\frac{n !}{( n - p )!}

(arrangement)

2. Passer par le complémentaire

Dénombrement par le complémentaire

Ω

est l'ensemble de tous les cas possibles et

A

l'événement recherché :

card (A) = card (Ω) - card (\overline{A})

Mot-clé : « au moins un » → Total

-

« aucun ».

Exemple

Combien de mots de 4 lettres (parmi 26) contiennent au moins un A ?

• Total de mots de 4 lettres :

2 6^{4}

• Mots sans aucun A (25 lettres possibles) :

2 5^{4}

Mots avec au moins un A

= 2 6^{4} - 2 5^{4} = 456976 - 390625 = 66351

3. Décomposer en étapes

Décomposer en choix indépendants

Séparer le problème en étapes indépendantes, puis multiplier les résultats de chaque étape (principe multiplicatif).

Exemple

Former un comité de 4 personnes composé de 2 garçons parmi 8 et 2 filles parmi 6.

• Étape 1 : choisir 2 garçons parmi 8 →

(2 8) = 28

• Étape 2 : choisir 2 filles parmi 6 →

(2 6) = 15

Total

= 28 \times 15 = 420

comités.

4. Distinguer des cas

Cas disjoints → additionner

Quand un problème se décompose en cas disjoints, on additionne le nombre de possibilités de chaque cas (principe additif).

Exemple

Former un comité de 4 personnes parmi 8 garçons et 6 filles avec au moins 1 fille.

On distingue les cas selon le nombre de filles :

• 3G, 1F :

(3 8) \times (1 6) = 56 \times 6 = 336

• 2G, 2F :

(2 8) \times (2 6) = 28 \times 15 = 420

• 1G, 3F :

(1 8) \times (3 6) = 8 \times 20 = 160

• 0G, 4F :

(0 8) \times (4 6) = 1 \times 15 = 15

Total

= 336 + 420 + 160 + 15 = 931

.

Vérification par le complémentaire :

(4 14) - (4 8) = 1001 - 70 = 931

✓

5. Fixer un élément

Fixer un élément imposé

Quand un élément précis doit faire partie de la sélection, on le fixe et on choisit le reste parmi les éléments restants.

Exemple

Combien de comités de 3 personnes parmi 10 contiennent Alice ?

Alice est fixée dans le comité. Il reste à choisir 2 personnes parmi les 9 autres :

(2 9) = 36

6. Placer d'abord les contraintes

Traiter les contraintes en premier

Quand certains éléments ont des contraintes (voisinage, exclusion, position imposée), les placer en premier, puis arranger les éléments restants.

Exemple : éléments côte à côte

6 personnes se placent en ligne. A et B doivent être côte à côte.

1. On forme le bloc {A, B} → on a maintenant 5 objets à placer (le bloc + 4 autres personnes)
2. Permutations de ces 5 objets :

5!

3. À l'intérieur du bloc, A et B peuvent permuter :

2!

Total

= 5! \times 2! = 120 \times 2 = 240

Anagrammes avec répétitions

Le nombre d'anagrammes d'un mot de

n

lettres où la lettre

i

apparaît

r_{i}

fois est :

\frac{n !}{r _{1} ! \times r _{2} ! \times \dots \times r _{k} !}

Exemple

Nombre d'anagrammes du mot MAMA (4 lettres : M apparaît 2 fois, A apparaît 2 fois) :

\frac{4 !}{2 ! \times 2 !} = \frac{24}{4} = 6

Ce sont : MMAA, MAMA, MAAM, AMMA, AMAM, AAMM.

Tableau récapitulatif

Situation	Ordre	Répétition	Formule
$p$ -liste avec répétition	Oui	Oui	$n^{p}$
Arrangement	Oui	Non	$\frac{n !}{( n - p )!}$
Permutation	Oui	Non	$n!$
Combinaison	Non	Non	$(p n) = \frac{n !}{p ! ( n - p )!}$
Anagrammes (avec rép.)	Oui	—	$\frac{n !}{r _{1} ! \times r _{2} ! \times \dots \times r _{k} !}$

Situation	Ordre	Répétition	Formule
$p$ -liste avec rép.	Oui	Oui	$n^{p}$
Arrangement	Oui	Non	$\frac{n !}{( n - p )!}$
Permutation	Oui	Non	$n!$
Combinaison	Non	Non	$(p n) = \frac{n !}{p ! ( n - p )!}$
Anagrammes (rép.)	Oui	—	$\frac{n !}{r _{1} ! \times \dots \times r _{k} !}$

40 exercices disponibles

Exercice 1

Facile

Un code PIN est composé de 4 chiffres choisis parmi

\{0, 1, 2, \ldots, 9\}

. Les répétitions sont autorisées.

Combien de codes PIN peut-on former ?

Chaque position du code offre 10 choix (les chiffres de 0 à 9), et les répétitions sont autorisées. C'est une 4-liste avec répétition d'un ensemble à 10 éléments.

D'après le principe multiplicatif :

10 \times 10 \times 10 \times 10 = 10^4 = \boxed{10\,000}

Combien de codes PIN ont leurs 4 chiffres tous distincts ?

On cherche le nombre de 4-listes sans répétition (arrangements) de 4 chiffres parmi 10 :

A_{10}^4 = 10 \times 9 \times 8 \times 7 = \boxed{5\,040}

En effet, le 1er chiffre a 10 choix, le 2e a 9 (un chiffre déjà pris), le 3e a 8, le 4e a 7.

Combien de codes PIN commencent par un chiffre non nul ?

Le premier chiffre est choisi parmi

\{1, 2, \ldots, 9\}

: 9 choix.

Les 3 chiffres suivants sont choisis librement parmi

\{0, 1, \ldots, 9\}

: 10 choix chacun.

Par le principe multiplicatif :

9 \times 10 \times 10 \times 10 = 9 \times 10^3 = \boxed{9\,000}

Exercice 2

Facile

Un restaurant propose 4 entrées, 5 plats principaux et 3 desserts.

Combien de menus complets (entrée + plat + dessert) peut-on composer ?

Un menu complet se compose de 3 choix successifs indépendants. Par le principe multiplicatif :

4 \times 5 \times 3 = \boxed{60}

On peut former 60 menus complets.

Combien de menus si le dessert est optionnel (on peut ne pas en prendre) ?

Si le dessert est optionnel, on a 4 choix pour le dessert : les 3 desserts ou « pas de dessert ».

Nombre de menus :

4 \times 5 \times (3 + 1) = 4 \times 5 \times 4 = \boxed{80}

Combien de menus si 2 plats sont indisponibles ?

Il reste

5 - 2 = 3

plats disponibles. Le nombre de menus complets est :

4 \times 3 \times 3 = \boxed{36}

Exercice 3

Facile

Calculer les combinaisons suivantes.

Calculer

\binom{7}{3}

en utilisant la formule

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

On applique la formule :

\binom{7}{3} = \dfrac{7!}{3! \times 4!} = \dfrac{7 \times 6 \times 5}{3 \times 2 \times 1} = \dfrac{210}{6} = \boxed{35}

Calculer

\binom{10}{7}

en utilisant la propriété de symétrie

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

Par la propriété de symétrie :

\binom{10}{7} = \binom{10}{10-7} = \binom{10}{3} = \dfrac{10 \times 9 \times 8}{3 \times 2 \times 1} = \dfrac{720}{6} = \boxed{120}

Cette propriété permet de simplifier le calcul en choisissant le plus petit entre

k

n-k

Calculer

\binom{8}{0} + \binom{8}{1} + \binom{8}{8}

On utilise les cas particuliers connus :

\binom{8}{0} = 1 \quad ; \quad \binom{8}{1} = 8 \quad ; \quad \binom{8}{8} = 1

Donc :

\binom{8}{0} + \binom{8}{1} + \binom{8}{8} = 1 + 8 + 1 = \boxed{10}

Exercice 4

Facile

On considère le mot MARDI (5 lettres toutes distinctes).

Combien d'anagrammes peut-on former avec les lettres de MARDI ?

Le mot MARDI comporte 5 lettres toutes distinctes. Le nombre d'anagrammes est le nombre de permutations de 5 éléments :

5! = 5 \times 4 \times 3 \times 2 \times 1 = \boxed{120}

Combien d'anagrammes commencent par la lettre M ?

Si M est fixé en première position, il reste 4 lettres (A, R, D, I) à permuter dans les 4 positions restantes :

4! = 4 \times 3 \times 2 \times 1 = \boxed{24}

Combien d'anagrammes commencent par une voyelle ?

Les voyelles de MARDI sont A et I, soit 2 choix pour la première lettre.

Pour chacun de ces choix, les 4 lettres restantes se permutent librement :

4!

possibilités.

Par le principe multiplicatif :

2 \times 4! = 2 \times 24 = \boxed{48}

Exercice 5

Facile

On lance un dé équilibré à 6 faces trois fois de suite.

Combien de résultats possibles y a-t-il ?

Chaque lancer a 6 issues possibles. Les lancers sont indépendants. C'est une 3-liste avec répétition de

\{1, 2, 3, 4, 5, 6\}

6^3 = \boxed{216}

Combien de résultats ne contiennent que des faces paires ?

Les faces paires sont

\{2, 4, 6\}

, soit 3 choix par lancer.

3^3 = \boxed{27}

Combien de résultats contiennent au moins un 6 ?

On utilise le dénombrement par complémentaire.

Nombre de résultats sans aucun 6 : chaque lancer a 5 choix

\{1,2,3,4,5\}

, soit

5^3 = 125

.

Nombre de résultats avec au moins un 6 :

6^3 - 5^3 = 216 - 125 = \boxed{91}

Exercice 6

Facile

Dans une classe de 32 élèves, 20 pratiquent l'anglais et 18 l'espagnol. Seulement 4 élèves ne pratiquent aucune de ces deux langues.

Combien d'élèves pratiquent au moins une des deux langues ?

Si 4 élèves ne pratiquent aucune langue, alors le nombre d'élèves qui pratiquent au moins une langue est :

32 - 4 = \boxed{28}

En utilisant la formule d'inclusion-exclusion, déterminer le nombre d'élèves qui pratiquent les deux langues.

Notons

A

l'ensemble des élèves qui font anglais et

E

ceux qui font espagnol.

Par la formule d'inclusion-exclusion :

\text{card}(A \cup E) = \text{card}(A) + \text{card}(E) - \text{card}(A \cap E)

28 = 20 + 18 - \text{card}(A \cap E)

\text{card}(A \cap E) = 20 + 18 - 28 = \boxed{10}

10 élèves pratiquent les deux langues.

Combien d'élèves pratiquent exactement une seule langue ?

Nombre d'élèves qui pratiquent uniquement l'anglais :

20 - 10 = 10

.

Nombre d'élèves qui pratiquent uniquement l'espagnol :

18 - 10 = 8

.

Nombre d'élèves qui pratiquent exactement une langue :

10 + 8 = \boxed{18}

Vérification :

10 + 8 + 10 + 4 = 32

✓ (une seule langue + deux langues + aucune).

Exercice 7

Facile

Soit

E = \{1, 2, 3, 4, 5, 6\}

Combien

E

possède-t-il de sous-ensembles ?

Le nombre de sous-ensembles (ou parties) d'un ensemble à

n

éléments est

2^n

.

Ici

n = 6

, donc :

2^6 = \boxed{64}

(Cela inclut l'ensemble vide

\varnothing

E

lui-même.)

Combien de sous-ensembles à 2 éléments

E

possède-t-il ?

On choisit 2 éléments parmi 6 sans ordre : c'est une combinaison.

\binom{6}{2} = \dfrac{6!}{2! \times 4!} = \dfrac{6 \times 5}{2} = \boxed{15}

Combien de sous-ensembles contiennent au moins 4 éléments ?

Les sous-ensembles d'au moins 4 éléments sont ceux de taille 4, 5 ou 6 :

\binom{6}{4} + \binom{6}{5} + \binom{6}{6} = 15 + 6 + 1 = \boxed{22}

On a utilisé

\binom{6}{4} = \binom{6}{2} = 15

\binom{6}{5} = \binom{6}{1} = 6

Exercice 8

Facile

On s'intéresse au triangle de Pascal.

Écrire la ligne

n = 5

du triangle de Pascal.

La ligne

n = 5

contient les coefficients

\binom{5}{k}

pour

k = 0, 1, \ldots, 5

\binom{5}{0} = 1 \;; \; \binom{5}{1} = 5 \;; \; \binom{5}{2} = 10 \;; \; \binom{5}{3} = 10 \;; \; \binom{5}{4} = 5 \;; \; \binom{5}{5} = 1

La ligne

n=5

est donc :

\boxed{1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1}

Vérifier que

\binom{5}{2} + \binom{5}{3} = \binom{6}{3}

D'après la ligne calculée :

\binom{5}{2} + \binom{5}{3} = 10 + 10 = 20

Calculons

\binom{6}{3}

\binom{6}{3} = \dfrac{6 \times 5 \times 4}{3 \times 2 \times 1} = \dfrac{120}{6} = 20

On vérifie bien

\binom{5}{2} + \binom{5}{3} = \binom{6}{3} = 20

✓.

C'est la formule de Pascal :

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

Calculer la somme des coefficients de la ligne

n = 5

La somme des coefficients de la ligne

n

du triangle de Pascal vaut

2^n

. Vérifions :

1 + 5 + 10 + 10 + 5 + 1 = 32 = 2^5 \quad

Ce résultat découle de la formule du binôme avec

a = b = 1

\sum_{k=0}^{n} \binom{n}{k} = (1+1)^n = 2^n

Exercice 9

Facile

Les plaques d'immatriculation sont composées de 2 lettres (parmi 26) suivies de 3 chiffres (parmi 10).

Combien de plaques peut-on former (répétitions autorisées) ?

Par le principe multiplicatif :

26 \times 26 \times 10 \times 10 \times 10 = 26^2 \times 10^3 = 676 \times 1\,000 = \boxed{676\,000}

Combien de plaques ont leurs 3 chiffres tous distincts ?

Les 2 lettres sont libres :

26^2

choix.

Les 3 chiffres doivent être distincts : c'est un arrangement de 3 parmi 10, soit

10 \times 9 \times 8 = 720

26^2 \times 720 = 676 \times 720 = \boxed{486\,720}

Combien de plaques commencent par AB ?

Les 2 lettres sont fixées (A puis B) : 1 seul choix.

Les 3 chiffres sont libres :

10^3 = 1\,000

choix.

1 \times 1\,000 = \boxed{1\,000}

Exercice 10

Facile

On tire simultanément 3 cartes d'un jeu de 32 cartes.

Combien de tirages de 3 cartes peut-on effectuer ?

On tire 3 cartes simultanément (donc sans ordre et sans répétition). C'est une combinaison :

\binom{32}{3} = \dfrac{32 \times 31 \times 30}{3!} = \dfrac{29\,760}{6} = \boxed{4\,960}

Combien de tirages contiennent exactement 3 cœurs ?

Un jeu de 32 cartes contient 8 cœurs. On choisit 3 cœurs parmi 8 :

\binom{8}{3} = \dfrac{8 \times 7 \times 6}{6} = \boxed{56}

Combien de tirages ne contiennent aucun as ?

Un jeu de 32 cartes contient 4 as. Les cartes « non-as » sont

32 - 4 = 28

.

On choisit 3 cartes parmi ces 28 :

\binom{28}{3} = \dfrac{28 \times 27 \times 26}{6} = \dfrac{19\,656}{6} = \boxed{3\,276}

Exercice 11

Intermédiaire

On considère les anagrammes du mot CLASSE (6 lettres dont S apparaît 2 fois).

Combien d'anagrammes peut-on former ?

Le mot CLASSE comporte 6 lettres : C, L, A, S, S, E avec la lettre S répétée 2 fois.

Le nombre d'anagrammes est :

\dfrac{6!}{2!} = \dfrac{720}{2} = \boxed{360}

On divise par

2!

car les deux S sont indiscernables.

Combien d'anagrammes commencent par la lettre C ?

Si C est fixé en 1ère position, il reste 5 lettres (L, A, S, S, E) avec S répété 2 fois :

\dfrac{5!}{2!} = \dfrac{120}{2} = \boxed{60}

Combien d'anagrammes ont les deux S consécutifs ?

On regroupe les deux S en un bloc [SS]. On obtient 5 « objets » à permuter : C, L, A, [SS], E, tous distincts.

5! = \boxed{120}

Combien d'anagrammes commencent par CL ?

Si C est en position 1 et L en position 2, il reste 4 lettres (A, S, S, E) à permuter :

\dfrac{4!}{2!} = \dfrac{24}{2} = \boxed{12}

Exercice 12

Intermédiaire

On considère une grille rectangulaire de 4 colonnes et 3 lignes. On se déplace du coin bas-gauche

(0,0)

au coin haut-droit

(4,3)

en ne faisant que des pas vers la droite (D) ou vers le haut (H).

Combien de chemins mènent de

(0,0)

(4,3)

Chaque chemin est composé de 4 pas D et 3 pas H, soit 7 pas au total.

Un chemin est entièrement déterminé par le choix des positions des 3 pas H parmi les 7 :

\binom{7}{3} = \dfrac{7 \times 6 \times 5}{3!} = \dfrac{210}{6} = \boxed{35}

Combien de chemins passent par le point

(2,1)

Un chemin passant par

(2,1)

se décompose en :

- Un chemin de

(0,0)

(2,1)

\binom{3}{1} = 3

chemins (3 pas dont 1 H)
- Un chemin de

(2,1)

(4,3)

\binom{4}{2} = 6

chemins (4 pas dont 2 H)

Par le principe multiplicatif :

3 \times 6 = \boxed{18}

Combien de chemins ne passent PAS par

(2,1)

Par dénombrement du complémentaire :

Nombre de chemins ne passant pas par

(2,1)

= nombre total

-

nombre passant par

(2,1)

35 - 18 = \boxed{17}

Exercice 13

Intermédiaire

Un groupe est composé de 8 hommes et 6 femmes. On forme un comité de 5 personnes.

Combien de comités peut-on former ?

On choisit 5 personnes parmi

8 + 6 = 14

\binom{14}{5} = \dfrac{14 \times 13 \times 12 \times 11 \times 10}{5!} = \dfrac{240\,240}{120} = \boxed{2\,002}

Combien de comités contiennent exactement 2 femmes ?

On choisit 2 femmes parmi 6 et 3 hommes parmi 8 :

\binom{6}{2} \times \binom{8}{3} = 15 \times 56 = \boxed{840}

Combien de comités contiennent au moins une femme ?

Par le complémentaire, on retire les comités sans aucune femme (5 hommes parmi 8) :

\binom{14}{5} - \binom{8}{5} = 2\,002 - 56 = \boxed{1\,946}

Combien de comités contiennent plus de femmes que d'hommes ?

Pour que les femmes soient majoritaires dans un comité de 5, il faut au moins 3 femmes.

3 femmes et 2 hommes :

\binom{6}{3} \times \binom{8}{2} = 20 \times 28 = 560

4 femmes et 1 homme :

\binom{6}{4} \times \binom{8}{1} = 15 \times 8 = 120

5 femmes :

\binom{6}{5} \times \binom{8}{0} = 6 \times 1 = 6

Total :

560 + 120 + 6 = \boxed{686}

Exercice 14

Intermédiaire

On utilise la formule du binôme de Newton pour développer

(2x - 1)^4

Rappeler la formule du binôme de Newton.

Pour tous réels

a, b

et tout entier

n \geq 0

(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k

Développer

(2x - 1)^4

On pose

a = 2x

b = -1

n = 4

(2x-1)^4 = \sum_{k=0}^{4} \binom{4}{k} (2x)^{4-k}(-1)^k

= \binom{4}{0}(2x)^4 - \binom{4}{1}(2x)^3 + \binom{4}{2}(2x)^2 - \binom{4}{3}(2x) + \binom{4}{4}

= 16x^4 - 4 \times 8x^3 + 6 \times 4x^2 - 4 \times 2x + 1

= \boxed{16x^4 - 32x^3 + 24x^2 - 8x + 1}

Quel est le coefficient de

x^2

dans ce développement ?

D'après le développement, le terme en

x^2

est

24x^2

.

Le coefficient de

x^2

est donc

\boxed{24}

.

On pouvait le calculer directement :

\binom{4}{2}(2)^2(-1)^2 = 6 \times 4 \times 1 = 24

En posant

x = 10

, calculer

19^4

On a

(2 \times 10 - 1)^4 = 19^4

.

En remplaçant

x

par 10 dans le développement :

19^4 = 16 \times 10^4 - 32 \times 10^3 + 24 \times 10^2 - 8 \times 10 + 1

= 160\,000 - 32\,000 + 2\,400 - 80 + 1 = \boxed{130\,321}

Exercice 15

Intermédiaire

On tire simultanément 5 cartes d'un jeu de 52 cartes.

Combien de mains de 5 cartes peut-on former ?

\binom{52}{5} = \dfrac{52 \times 51 \times 50 \times 49 \times 48}{5!} = \dfrac{311\,875\,200}{120} = \boxed{2\,598\,960}

Combien de mains contiennent exactement 2 as ?

On choisit 2 as parmi 4, puis 3 cartes non-as parmi 48 :

\binom{4}{2} \times \binom{48}{3} = 6 \times 17\,296 = \boxed{103\,776}

Où

\binom{48}{3} = \dfrac{48 \times 47 \times 46}{6} = 17\,296

Combien de mains contiennent les 4 as ?

Les 4 as sont dans la main. Il reste à choisir 1 carte parmi les 48 restantes :

\binom{4}{4} \times \binom{48}{1} = 1 \times 48 = \boxed{48}

Combien de mains ne contiennent aucun as ?

On choisit 5 cartes parmi les 48 cartes qui ne sont pas des as :

\binom{48}{5} = \dfrac{48 \times 47 \times 46 \times 45 \times 44}{120} = \boxed{1\,712\,304}

Vérification : on peut vérifier que la somme des mains avec 0, 1, 2, 3 ou 4 as donne bien

\binom{52}{5}

Exercice 16

Intermédiaire

Un mot de passe est composé de 6 caractères choisis parmi les 26 lettres minuscules et les 10 chiffres (36 caractères au total).

Combien de mots de passe peut-on former ?

C'est une 6-liste avec répétition d'un ensemble à 36 éléments :

36^6 = \boxed{2\,176\,782\,336}

Soit environ

2{,}18

milliards de mots de passe.

Combien de mots de passe ne contiennent que des lettres (aucun chiffre) ?

On n'utilise que les 26 lettres :

26^6 = \boxed{308\,915\,776}

En déduire le nombre de mots de passe contenant au moins un chiffre.

Par dénombrement du complémentaire :

Mots de passe avec au moins un chiffre = Total

-

mots de passe sans aucun chiffre :

36^6 - 26^6 = 2\,176\,782\,336 - 308\,915\,776 = \boxed{1\,867\,866\,560}

Exercice 17

Intermédiaire

Montrer que

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

en utilisant la formule du binôme de Newton.

Correction détaillée

D'après la formule du binôme de Newton, pour tous réels

a

b

(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k

Posons

a = 1

b = 1

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

Donc :

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

Interprétation combinatoire : Le membre de gauche compte tous les sous-ensembles d'un ensemble à

n

éléments (classés par taille

k

). Le membre de droite les compte directement (chaque élément est soit pris, soit non).

Exercice 18

Intermédiaire

Lors d'une conférence, 12 personnes se rencontrent et chacune serre la main de toutes les autres.

Combien de poignées de mains sont échangées ?

Une poignée de mains correspond à un choix non ordonné de 2 personnes parmi 12 :

\binom{12}{2} = \dfrac{12 \times 11}{2} = \boxed{66}

Si les 12 personnes se répartissent en 2 groupes de 6, combien de poignées de mains se font entre personnes de groupes différents ?

Chaque personne du groupe 1 serre la main de chaque personne du groupe 2 :

6 \times 6 = \boxed{36}

poignées de mains inter-groupes.

En déduire le nombre de poignées de mains intra-groupes (au sein du même groupe).

Le nombre total de poignées de mains est 66. Les poignées inter-groupes sont 36.

Poignées intra-groupes :

66 - 36 = 30

.

Vérification : Chaque groupe de 6 échange

\binom{6}{2} = 15

poignées. Deux groupes :

2 \times 15 = 30

✓.

\boxed{30}

Exercice 19

Intermédiaire

On choisit 3 livres parmi 10 livres différents.

De combien de façons peut-on distribuer ces 3 livres comme 1er, 2e et 3e prix ?

L'ordre compte (1er prix ≠ 2e prix). C'est un arrangement de 3 parmi 10 :

A_{10}^3 = 10 \times 9 \times 8 = \boxed{720}

De combien de façons peut-on simplement choisir 3 livres (sans distinction de prix) ?

L'ordre ne compte pas. C'est une combinaison :

\binom{10}{3} = \dfrac{10 \times 9 \times 8}{3!} = \dfrac{720}{6} = \boxed{120}

Vérifier la relation

A_n^p = p! \times \binom{n}{p}

sur cet exemple.

On a

A_{10}^3 = 720

\binom{10}{3} = 120

.

Vérifions :

3! \times \binom{10}{3} = 6 \times 120 = 720 = A_{10}^3

✓.

Explication : pour passer d'une combinaison à un arrangement, on ordonne les

p

éléments choisis, ce qui donne

p!

possibilités supplémentaires.

Exercice 20

Intermédiaire

Un code binaire est un mot de longueur 5 composé de 0 et de 1.

Combien de codes binaires de longueur 5 existe-t-il ?

Chaque position a 2 choix (0 ou 1). C'est une 5-liste avec répétition de

\{0,1\}

2^5 = \boxed{32}

Combien de codes contiennent exactement 3 fois le chiffre 1 ?

On choisit les 3 positions (parmi 5) qui contiendront un 1 :

\binom{5}{3} = 10

Il y a

\boxed{10}

codes avec exactement trois 1.

Combien de codes contiennent au plus 2 fois le chiffre 1 ?

On additionne les codes avec 0, 1 ou 2 fois le chiffre 1 :

\binom{5}{0} + \binom{5}{1} + \binom{5}{2} = 1 + 5 + 10 = \boxed{16}

Remarque : c'est exactement la moitié de 32. En effet, par symétrie du triangle de Pascal, les codes avec au plus 2 uns sont en bijection avec les codes avec au moins 3 uns.

Exercice 21

Difficile

On considère les anagrammes du mot BANANE (6 lettres : B, A, N, A, N, E).

Combien d'anagrammes peut-on former ?

Le mot BANANE contient 6 lettres avec les répétitions : A apparaît 2 fois et N apparaît 2 fois.

\dfrac{6!}{2! \times 2!} = \dfrac{720}{4} = \boxed{180}

Combien d'anagrammes commencent par B et finissent par E ?

B est fixé en position 1, E en position 6. Il reste 4 lettres (A, N, A, N) à permuter, avec A×2 et N×2 :

\dfrac{4!}{2! \times 2!} = \dfrac{24}{4} = \boxed{6}

Combien d'anagrammes ont les deux A consécutifs ?

On regroupe les deux A en un bloc [AA]. On obtient 5 objets à permuter : B, [AA], N, N, E avec N répété 2 fois.

\dfrac{5!}{2!} = \dfrac{120}{2} = \boxed{60}

Combien d'anagrammes ont les deux A NON consécutifs ?

Par le complémentaire :

Anagrammes avec A non consécutifs = Total

-

anagrammes avec A consécutifs :

180 - 60 = \boxed{120}

Exercice 22

Difficile

Six personnes s'installent autour d'une table ronde.

Combien de dispositions différentes y a-t-il ?

Pour des permutations circulaires de

n

personnes, on fixe une personne pour éliminer les rotations identiques.

Nombre de dispositions :

(6-1)! = 5! = \boxed{120}

Combien de dispositions si deux personnes A et B doivent être voisines ?

On regroupe A et B en un bloc. On obtient 5 « objets » à placer en cercle :

(5-1)! = 4! = 24

.

Mais à l'intérieur du bloc, A et B peuvent être dans 2 ordres (AB ou BA).

4! \times 2 = 24 \times 2 = \boxed{48}

Combien de dispositions si A et B ne doivent PAS être voisins ?

Par complémentaire :

5! - 4! \times 2 = 120 - 48 = \boxed{72}

Parmi les 6 personnes, 3 sont des femmes (F) et 3 des hommes (H). Combien de dispositions alternent hommes et femmes ?

Fixons la position d'une femme (pour éliminer les rotations). Les 2 autres femmes se placent dans les 2 sièges « femmes » restants :

2!

façons.

Les 3 hommes se placent dans les 3 sièges « hommes » :

3!

façons.

2! \times 3! = 2 \times 6 = \boxed{12}

Exercice 23

Difficile

Formule de Pascal :

\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}

pour

1 \leq p \leq n-1

Démontrer cette formule en utilisant l'expression factorielle de

\binom{n}{p}

Calculons

\binom{n-1}{p-1} + \binom{n-1}{p}

\dfrac{(n-1)!}{(p-1)!(n-p)!} + \dfrac{(n-1)!}{p!(n-1-p)!}

Factorisons par

\dfrac{(n-1)!}{p!(n-p)!}

= \dfrac{(n-1)!}{p!(n-p)!} \times p + \dfrac{(n-1)!}{p!(n-p)!} \times (n-p)

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

Donner une démonstration combinatoire de cette formule.

Soit

E

un ensemble à

n

éléments. Fixons un élément

a \in E

.

Les parties de

E

p

éléments se répartissent en deux catégories disjointes :

- Celles qui contiennent

a

: on choisit les

p-1

éléments restants parmi les

n-1

autres →

\binom{n-1}{p-1}

- Celles qui ne contiennent pas

a

: on choisit les

p

éléments parmi les

n-1

autres →

\binom{n-1}{p}

Donc

\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}

En utilisant cette formule, calculer

\binom{20}{18}

rapidement.

Par symétrie :

\binom{20}{18} = \binom{20}{2}

\binom{20}{2} = \dfrac{20 \times 19}{2} = \boxed{190}

Alternative avec Pascal :

\binom{20}{18} = \binom{19}{17} + \binom{19}{18} = \binom{19}{2} + 19 = 171 + 19 = 190

✓.

En déduire par récurrence que

\binom{n}{p}

est un entier naturel pour tous

0 \leq p \leq n

Initialisation :

\binom{n}{0} = 1

\binom{n}{n} = 1

sont des entiers pour tout

n

.

Récurrence sur $n$ : Supposons que tous les

\binom{n-1}{k}

sont des entiers (

0 \leq k \leq n-1

).

Pour

1 \leq p \leq n-1

\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}

, qui est une somme de deux entiers (par hypothèse de récurrence), donc un entier.

Conclusion : Par récurrence,

\binom{n}{p} \in \mathbb{N}

pour tous

0 \leq p \leq n

.

(Ce résultat n'est pas évident a priori car

\binom{n}{p} = \dfrac{n!}{p!(n-p)!}

est un quotient de factorielles.)

Exercice 24

Difficile

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

Combien de tirages de 5 boules peut-on effectuer ?

On choisit 5 boules parmi

5 + 4 + 3 = 12

\binom{12}{5} = \dfrac{12 \times 11 \times 10 \times 9 \times 8}{5!} = \dfrac{95\,040}{120} = \boxed{792}

Combien de tirages contiennent exactement 2 rouges et 1 verte ?

On choisit 2 rouges parmi 5, 1 verte parmi 3, et les 2 restantes parmi les 4 bleues :

\binom{5}{2} \times \binom{3}{1} \times \binom{4}{2} = 10 \times 3 \times 6 = \boxed{180}

Combien de tirages contiennent au moins une boule de chaque couleur ?

Par le complémentaire, on retire les tirages où au moins une couleur est absente.

Notation :

A

= pas de rouge,

B

= pas de bleu,

C

= pas de vert.

|A| = \binom{7}{5} = 21

(5 parmi les 4B+3V)

|B| = \binom{8}{5} = 56

(5 parmi les 5R+3V)

|C| = \binom{9}{5} = 126

(5 parmi les 5R+4B)

|A \cap B| = \binom{3}{5} = 0

(impossible : seulement 3 vertes)

|A \cap C| = \binom{4}{5} = 0

(impossible : seulement 4 bleues)

|B \cap C| = \binom{5}{5} = 1

(les 5 rouges)

|A \cap B \cap C| = 0

Par inclusion-exclusion :

|A \cup B \cup C| = 21 + 56 + 126 - 0 - 0 - 1 + 0 = 202

.

Tirages avec au moins une de chaque couleur :

792 - 202 = \boxed{590}

Combien de tirages contiennent 5 boules de la même couleur ?

• 5 rouges parmi 5 :

\binom{5}{5} = 1

- 5 bleues parmi 4 :

\binom{4}{5} = 0

(impossible)
- 5 vertes parmi 3 :

\binom{3}{5} = 0

(impossible)

Total :

\boxed{1}

seul tirage (les 5 boules rouges).

Exercice 25

Difficile

Un QCM comporte 10 questions. Chaque question propose 4 réponses dont une seule est correcte.

De combien de façons peut-on remplir le QCM en répondant à toutes les questions ?

Chaque question offre 4 choix, et les choix sont indépendants. C'est une 10-liste de

\{A,B,C,D\}

4^{10} = \boxed{1\,048\,576}

De combien de façons peut-on remplir le QCM si on a le droit de ne pas répondre à certaines questions ?

Chaque question offre 5 choix : A, B, C, D, ou ne pas répondre.

5^{10} = \boxed{9\,765\,625}

Combien de grilles contiennent exactement 7 bonnes réponses ?

On choisit les 7 questions où la réponse est correcte :

\binom{10}{7}

façons.

Pour les 3 questions restantes, on choisit une mauvaise réponse parmi 3 possibles.

\binom{10}{7} \times 3^3 = 120 \times 27 = \boxed{3\,240}

Combien de grilles contiennent au moins 8 bonnes réponses ?

On additionne les cas 8, 9 et 10 bonnes réponses :

8 bonnes :

\binom{10}{8} \times 3^2 = 45 \times 9 = 405

9 bonnes :

\binom{10}{9} \times 3^1 = 10 \times 3 = 30

10 bonnes :

\binom{10}{10} \times 3^0 = 1

Total :

405 + 30 + 1 = \boxed{436}

Exercice 26

Difficile

Montrer l'identité :

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

pour

1 \leq k \leq n

Démontrer cette identité par le calcul factoriel.

Calculons le membre de gauche :

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

Calculons le membre de droite :

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

Les deux expressions sont égales.

\square

En déduire la valeur de

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

Le terme

k=0

est nul. Pour

k \geq 1

, on utilise l'identité :

\sum_{k=1}^{n} k \binom{n}{k} = \sum_{k=1}^{n} n \binom{n-1}{k-1} = n \sum_{k=1}^{n} \binom{n-1}{k-1}

Par le changement d'indice

j = k-1

= n \sum_{j=0}^{n-1} \binom{n-1}{j} = n \times 2^{n-1}

Donc :

\boxed{\sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1}}

Application : calculer

\displaystyle\sum_{k=0}^{10} k \binom{10}{k}

On applique directement la formule :

\sum_{k=0}^{10} k \binom{10}{k} = 10 \times 2^9 = 10 \times 512 = \boxed{5\,120}

Exercice 27

Difficile

On distribue un jeu de 32 cartes à 4 joueurs, chacun recevant 8 cartes.

De combien de façons peut-on distribuer les 32 cartes à 4 joueurs ?

On choisit 8 cartes pour le joueur 1 parmi 32, puis 8 pour le joueur 2 parmi 24, etc. :

\binom{32}{8} \times \binom{24}{8} \times \binom{16}{8} \times \binom{8}{8} = \dfrac{32!}{(8!)^4}

Ce nombre est appelé coefficient multinomial.

\boxed{\dfrac{32!}{(8!)^4}}

Combien de mains de 8 cartes le joueur 1 peut-il recevoir ?

\binom{32}{8} = \dfrac{32!}{8! \times 24!} = \boxed{10\,518\,300}

Combien de distributions donnent les 4 as au joueur 1 ?

Le joueur 1 a les 4 as + 4 cartes parmi les 28 restantes :

\binom{28}{4}

choix.

Puis les 28 cartes restantes sont distribuées aux 3 autres joueurs :

\dfrac{28!}{(8!)^3} \div \binom{28}{4}

...

Plus simplement : on fixe les 4 as chez J1, on choisit 4 cartes parmi 28 pour compléter sa main, puis on distribue le reste :

\binom{28}{4} \times \binom{24}{8} \times \binom{16}{8} \times \binom{8}{8} = \binom{28}{4} \times \dfrac{24!}{(8!)^3}

= \boxed{20\,475 \times \dfrac{24!}{(8!)^3}}

Exercice 28

Difficile

On utilise la formule du binôme de Newton.

Déterminer le coefficient de

x^3

dans le développement de

(1+x)^8

Le terme général de

(1+x)^8

est

\binom{8}{k}x^k

.

Pour

k = 3

: le coefficient est

\binom{8}{3} = \dfrac{8 \times 7 \times 6}{6} = \boxed{56}

Déterminer le coefficient de

x^4

dans

(1 - 2x)^6

Le terme général de

(1-2x)^6

est

\binom{6}{k}(1)^{6-k}(-2x)^k = \binom{6}{k}(-2)^k x^k

.

Pour

k = 4

\binom{6}{4}(-2)^4 = 15 \times 16 = \boxed{240}

Calculer la somme des coefficients du développement de

(3x + 2)^5

La somme des coefficients d'un polynôme

P(x)

est

P(1)

(3 \times 1 + 2)^5 = 5^5 = \boxed{3\,125}

Déterminer

n

tel que

\binom{n}{3} = 84

On résout

\binom{n}{3} = 84

\dfrac{n(n-1)(n-2)}{6} = 84 \implies n(n-1)(n-2) = 504

On teste :

8 \times 7 \times 6 = 336

(trop petit),

9 \times 8 \times 7 = 504

✓.

Donc

\boxed{n = 9}

Exercice 29

Difficile

Dénombrement par complémentaire.

Combien de mots de 5 lettres (parmi 26) contiennent au moins une voyelle ?

Total de mots de 5 lettres :

26^5 = 11\,881\,376

.

Mots sans aucune voyelle (21 consonnes) :

21^5 = 4\,084\,101

.

Mots avec au moins une voyelle :

26^5 - 21^5 = 11\,881\,376 - 4\,084\,101 = \boxed{7\,797\,275}

Combien d'entiers de 1 à 1000 ne sont divisibles ni par 3, ni par 5 ?

Notons

A

= multiples de 3 et

B

= multiples de 5 dans

\{1, \ldots, 1000\}

|A| = \lfloor 1000/3 \rfloor = 333

|B| = \lfloor 1000/5 \rfloor = 200

|A \cap B| = \lfloor 1000/15 \rfloor = 66

(multiples de 15)

Par inclusion-exclusion :

|A \cup B| = 333 + 200 - 66 = 467

.

Entiers divisibles ni par 3 ni par 5 :

1000 - 467 = \boxed{533}

Combien d'entiers de 1 à 999 contiennent au moins un chiffre 7 dans leur écriture ?

Considérons les entiers de 000 à 999 (en écrivant sur 3 chiffres, avec des zéros non significatifs).

Entiers sans aucun 7 : chaque chiffre a 9 choix (0-9 sauf 7), soit

9^3 = 729

.

Entiers avec au moins un 7 parmi

\{000, \ldots, 999\}

1000 - 729 = 271

.

Mais 000 n'est pas dans

\{1, \ldots, 999\}

et ne contient pas de 7. Donc le résultat est le même pour

\{1, \ldots, 999\}

\boxed{271}

Exercice 30

Difficile

Soit

E = \{1, 2, 3, \ldots, n\}

avec

n \geq 2

Dénombrer les paires

\{a, b\}

d'éléments de

E

avec

a < b

C'est le nombre de combinaisons de 2 éléments parmi

n

\binom{n}{2} = \dfrac{n(n-1)}{2}

Dénombrer les triplets

(a, b, c)

d'éléments de

E

avec

a < b < c

C'est le nombre de combinaisons de 3 éléments parmi

n

(un choix de 3 éléments détermine un unique triplet ordonné) :

\binom{n}{3} = \dfrac{n(n-1)(n-2)}{6}

Montrer que le nombre de sous-ensembles de

E

de taille paire est égal au nombre de sous-ensembles de taille impaire.

On utilise le binôme avec

a = 1, b = -1

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

Donc

\displaystyle\sum_{k \text{ pair}} \binom{n}{k} - \sum_{k \text{ impair}} \binom{n}{k} = 0

.

Ainsi

\displaystyle\sum_{k \text{ pair}} \binom{n}{k} = \sum_{k \text{ impair}} \binom{n}{k}

.

Comme leur somme vaut

2^n

, chacune vaut

\boxed{2^{n-1}}

Exercice 31

Avancé

Un tournoi de tennis rassemble 8 joueurs en élimination directe (quarts de finale, demi-finales, finale).

De combien de façons peut-on constituer le tableau des quarts de finale (4 matchs) ?

Le tableau consiste à répartir les 8 joueurs en 4 paires ordonnées par position dans le tableau.

On choisit l'ordre des 8 joueurs :

8!

permutations. Mais au sein de chaque match, l'ordre des 2 joueurs n'importe pas (

2^4

symétries), et l'ordre des matchs au sein d'une même moitié de tableau non plus.

Plus simplement : on choisit 2 joueurs parmi 8 pour le match 1 :

\binom{8}{2}

, puis 2 parmi 6 pour le match 2 :

\binom{6}{2}

, etc.

\binom{8}{2} \times \binom{6}{2} \times \binom{4}{2} \times \binom{2}{2} = 28 \times 15 \times 6 \times 1 = \dfrac{8!}{2^4} = 2\,520

Si l'ordre des matchs dans le tableau compte (positions fixes) :

\boxed{2\,520}

Combien de parcours différents (séquences de résultats) le tournoi peut-il avoir ?

À chaque match, un des 2 joueurs gagne. Il y a

4 + 2 + 1 = 7

matchs au total.

Pour un tableau fixé, le nombre de parcours est :

2^7 = \boxed{128}

De combien de façons peut-on désigner un vainqueur, un finaliste et deux demi-finalistes ?

• Choix du vainqueur : 8
- Choix du finaliste (battu en finale) : 7
- Choix des 2 demi-finalistes (battus en demi) :

\binom{6}{2} = 15

8 \times 7 \times 15 = \boxed{840}

Si les joueurs sont classés de 1 (meilleur) à 8 et que le meilleur gagne toujours, qui remporte le tournoi ? Montrer que le joueur classé 2 n'est pas nécessairement finaliste.

Le joueur 1 gagne tous ses matchs et remporte le tournoi.

Le joueur 2 n'est pas nécessairement finaliste : si les joueurs 1 et 2 sont dans la même moitié de tableau, ils se rencontrent en demi-finale, et le joueur 2 est éliminé avant la finale.

Par exemple, avec le tableau [1 vs 2, 3 vs 4 | 5 vs 6, 7 vs 8] : le joueur 1 bat 2 en quart, puis bat 3 ou 4 en demi, et affronte le vainqueur de l'autre moitié en finale. Le joueur 2 est éliminé dès le premier tour.

Le finaliste serait le meilleur joueur de l'autre moitié du tableau.

Exercice 32

Avancé

On considère l'identité de Vandermonde :

\displaystyle\binom{m+n}{p} = \sum_{k=0}^{p} \binom{m}{k} \binom{n}{p-k}

Donner une interprétation combinatoire de cette identité.

Considérons un ensemble

E

m+n

éléments, partitionné en un groupe

A

m

éléments et un groupe

B

n

éléments.

Le membre de gauche

\binom{m+n}{p}

compte les parties de

E

p

éléments.

Pour former une telle partie, on choisit

k

éléments dans

A

p-k

éléments dans

B

(avec

0 \leq k \leq p

). Le nombre de choix est

\binom{m}{k}\binom{n}{p-k}

.

En sommant sur toutes les valeurs possibles de

k

, on obtient le membre de droite.

Cette partition en cas disjoints prouve l'identité.

\square

En posant

m = n

p = n

, montrer que

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

En appliquant Vandermonde avec

m = n

p = n

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

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

par symétrie. Donc :

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

Application : calculer

\binom{5}{0}^2 + \binom{5}{1}^2 + \binom{5}{2}^2 + \binom{5}{3}^2 + \binom{5}{4}^2 + \binom{5}{5}^2

D'après la formule précédente avec

n = 5

\sum_{k=0}^{5} \binom{5}{k}^2 = \binom{10}{5} = 252

Vérification :

1 + 25 + 100 + 100 + 25 + 1 = \boxed{252}

✓.

Vérifier l'identité de Vandermonde pour

m = 3

n = 4

p = 3

Membre de gauche :

\binom{7}{3} = 35

.

Membre de droite :

\binom{3}{0}\binom{4}{3} + \binom{3}{1}\binom{4}{2} + \binom{3}{2}\binom{4}{1} + \binom{3}{3}\binom{4}{0}

= 1 \times 4 + 3 \times 6 + 3 \times 4 + 1 \times 1 = 4 + 18 + 12 + 1 = 35 \quad

Exercice 33

Avancé

On répartit 12 élèves en 3 groupes.

Si les groupes sont numérotés (G1, G2, G3) et contiennent chacun 4 élèves, combien de répartitions y a-t-il ?

On choisit 4 élèves parmi 12 pour G1, puis 4 parmi 8 pour G2, puis les 4 restants forment G3 :

\binom{12}{4} \times \binom{8}{4} \times \binom{4}{4} = 495 \times 70 \times 1 = \boxed{34\,650}

On reconnaît le coefficient multinomial

\dfrac{12!}{4! \times 4! \times 4!} = 34\,650

Si les groupes sont indistinguables (non numérotés), combien de répartitions y a-t-il ?

Si les groupes sont identiques, chaque répartition a été comptée

3! = 6

fois (une pour chaque permutation des 3 groupes) dans le calcul précédent.

\dfrac{34\,650}{3!} = \dfrac{34\,650}{6} = \boxed{5\,775}

Combien de répartitions en un groupe de 3, un groupe de 4 et un groupe de 5 (groupes numérotés) ?

On choisit 3 élèves parmi 12 pour le groupe de 3, puis 4 parmi 9 pour le groupe de 4, puis les 5 restants :

\binom{12}{3} \times \binom{9}{4} \times \binom{5}{5} = 220 \times 126 \times 1 = \boxed{27\,720}

Combien de répartitions en un groupe de 3, un groupe de 3 et un groupe de 6 (groupes non numérotés) ?

Groupes numérotés :

\binom{12}{3} \times \binom{9}{3} \times \binom{6}{6} = 220 \times 84 \times 1 = 18\,480

.

Les deux groupes de 3 sont indistinguables, donc on divise par

2!

\dfrac{18\,480}{2} = \boxed{9\,240}

(On ne divise que par

2!

et non

3!

car seuls les deux groupes de même taille sont interchangeables.)

Exercice 34

Avancé

On étudie les propriétés de la formule du binôme de Newton.

Écrire

(1+x)^n

sous forme de somme.

D'après la formule du binôme de Newton :

(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k = \binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + \cdots + \binom{n}{n}x^n

En posant

x = -1

, montrer que

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

(1+(-1))^n = 0^n = 0

pour

n \geq 1

.

Or

(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k

. Avec

x = -1

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

\boxed{\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0}

Ce qui s'écrit aussi :

\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots + (-1)^n\binom{n}{n} = 0

En déduire que

\displaystyle\sum_{\substack{k=0 \ k \text{ pair}}}^{n} \binom{n}{k} = \sum_{\substack{k=0 \ k \text{ impair}}}^{n} \binom{n}{k} = 2^{n-1}

D'après la question 2 :

\sum_{k \text{ pair}} \binom{n}{k} - \sum_{k \text{ impair}} \binom{n}{k} = 0

.

Donc

\sum_{k \text{ pair}} \binom{n}{k} = \sum_{k \text{ impair}} \binom{n}{k}

.

Or leur somme vaut

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

.

Donc chacune vaut

\dfrac{2^n}{2} = \boxed{2^{n-1}}

En posant

x = 2

, calculer

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

(1+2)^n = 3^n

.

Or

(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k

. Avec

x = 2

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

Application numérique pour

n = 5

\binom{5}{0} + 2\binom{5}{1} + 4\binom{5}{2} + 8\binom{5}{3} + 16\binom{5}{4} + 32\binom{5}{5} = 1 + 10 + 40 + 80 + 80 + 32 = 243 = 3^5

✓.

Calculer

\displaystyle\sum_{k=0}^{6} 3^k \binom{6}{k}

D'après la question précédente avec

x = 3

n = 6

\sum_{k=0}^{6} 3^k \binom{6}{k} = (1+3)^6 = 4^6 = \boxed{4\,096}

Exercice 35

Avancé

On étudie les chemins sur une grille

n \times n

(0,0)

(n,n)

Rappeler le nombre de chemins de

(0,0)

(n,n)

(en se déplaçant uniquement vers la droite ou vers le haut).

Chaque chemin est composé de

n

pas à droite (D) et

n

pas en haut (H), soit

2n

pas au total.

Le nombre de chemins est :

\binom{2n}{n}

Application numérique pour

n = 4

\binom{8}{4} = \dfrac{8 \times 7 \times 6 \times 5}{4!} = \dfrac{1680}{24} = \boxed{70}

Combien de chemins de

(0,0)

(4,4)

passent par le point

(2,2)

Un tel chemin se décompose en :

- Un chemin de

(0,0)

(2,2)

\binom{4}{2} = 6

- Un chemin de

(2,2)

(4,4)

\binom{4}{2} = 6

Par le principe multiplicatif :

6 \times 6 = \boxed{36}

Combien de chemins de

(0,0)

(4,4)

passent par

(1,2)

puis par

(3,3)

Le chemin se décompose en 3 étapes :

-

(0,0) \to (1,2)

\binom{3}{2} = 3

(3 pas : 1D + 2H)
-

(1,2) \to (3,3)

\binom{3}{1} = 3

(3 pas : 2D + 1H)
-

(3,3) \to (4,4)

\binom{2}{1} = 2

(2 pas : 1D + 1H)

Total :

3 \times 3 \times 2 = \boxed{18}

Exercice 36

Avancé

Une loterie demande de choisir 6 numéros parmi les entiers de 1 à 49. Un tirage de 6 numéros est effectué au hasard.

Combien de grilles de loto peut-on remplir ?

C'est le nombre de combinaisons de 6 parmi 49 :

\binom{49}{6} = \dfrac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{6!} = \dfrac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{720} = \boxed{13\,983\,816}

Combien de grilles ont exactement 3 numéros en commun avec le tirage ?

On choisit 3 bons numéros parmi 6, et 3 mauvais parmi les

49 - 6 = 43

restants :

\binom{6}{3} \times \binom{43}{3} = 20 \times 12\,341 = \boxed{246\,820}

Où

\binom{43}{3} = \dfrac{43 \times 42 \times 41}{6} = 12\,341

Quelle est la probabilité de trouver les 6 bons numéros ?

Il n'y a qu'une seule grille gagnante :

P = \dfrac{1}{\binom{49}{6}} = \dfrac{1}{13\,983\,816} \approx \boxed{7{,}15 \times 10^{-8}}

Soit environ 1 chance sur 14 millions.

Quelle est la probabilité d'avoir au moins 4 bons numéros ?

On additionne les cas 4, 5 et 6 bons numéros :

4 bons :

\binom{6}{4}\binom{43}{2} = 15 \times 903 = 13\,545

5 bons :

\binom{6}{5}\binom{43}{1} = 6 \times 43 = 258

6 bons :

\binom{6}{6}\binom{43}{0} = 1

P = \dfrac{13\,545 + 258 + 1}{13\,983\,816} = \dfrac{13\,804}{13\,983\,816} \approx \boxed{9{,}87 \times 10^{-4}}

Soit environ 1 chance sur 1\,013.

Exercice 37

Avancé

On considère l'ensemble

E = \{1, 2, 3, \ldots, 10\}

Combien de sous-ensembles de

E

contiennent l'élément 1 ?

Si 1 est dans le sous-ensemble, on choisit librement les 9 autres éléments (chacun est pris ou non) :

2^9 = \boxed{512}

Combien de sous-ensembles de

E

contiennent 1 et 2 mais pas 3 ?

Les éléments 1 et 2 sont imposés, 3 est exclu. Les 7 éléments restants (4 à 10) sont libres :

2^7 = \boxed{128}

Combien de sous-ensembles à 4 éléments contiennent au moins un nombre pair ?

Les nombres pairs de

E

sont

\{2, 4, 6, 8, 10\}

(5 éléments) et les impairs sont

\{1, 3, 5, 7, 9\}

(5 éléments).

Par le complémentaire : sous-ensembles à 4 éléments sans aucun pair (4 impairs parmi 5) :

\binom{5}{4} = 5

Sous-ensembles à 4 éléments avec au moins un pair :

\binom{10}{4} - 5 = 210 - 5 = \boxed{205}

Combien de sous-ensembles à 5 éléments de

E

ont une somme paire ?

La somme est paire si et seulement si le nombre d'éléments impairs est pair (0, 2 ou 4).

Les éléments impairs de

E

\{1,3,5,7,9\}

(5 éléments). Les pairs :

\{2,4,6,8,10\}

(5 éléments).

0 impairs, 5 pairs :

\binom{5}{0}\binom{5}{5} = 1

2 impairs, 3 pairs :

\binom{5}{2}\binom{5}{3} = 10 \times 10 = 100

4 impairs, 1 pair :

\binom{5}{4}\binom{5}{1} = 5 \times 5 = 25

Total :

1 + 100 + 25 = \boxed{126}

Remarque :

126 = \dfrac{252}{2} = \dfrac{\binom{10}{5}}{2}

. Par symétrie, la moitié des sous-ensembles à 5 éléments ont une somme paire.

Exercice 38

Avancé

On utilise le binôme de Newton pour étudier

(1+x)^n(1-x)^n

Simplifier

(1+x)^n(1-x)^n

(1+x)^n(1-x)^n = [(1+x)(1-x)]^n = (1-x^2)^n

Développer

(1+x)^n(1-x)^n

en identifiant le coefficient de

x^{2p}

dans

(1-x^2)^n

En posant

y = x^2

dans

(1-y)^n

(1-x^2)^n = \sum_{p=0}^{n} \binom{n}{p}(-1)^p x^{2p}

Le coefficient de

x^{2p}

est

(-1)^p \binom{n}{p}

, et les termes de degré impair sont nuls.

En identifiant le coefficient de

x^{2p}

dans le produit

(1+x)^n(1-x)^n

développé via le binôme, montrer que

\displaystyle\sum_{k=0}^{2p} (-1)^k \binom{n}{k}\binom{n}{2p-k} = (-1)^p \binom{n}{p}

Le coefficient de

x^{2p}

dans

(1+x)^n

est

\binom{n}{j}

pour

x^j

, et dans

(1-x)^n

est

(-1)^k\binom{n}{k}

pour

x^k

.

Le coefficient de

x^{2p}

dans le produit est :

\sum_{k=0}^{2p} \binom{n}{k}(-1)^k \binom{n}{2p-k}

En identifiant avec le résultat de la question 2 :

\boxed{\sum_{k=0}^{2p} (-1)^k \binom{n}{k}\binom{n}{2p-k} = (-1)^p \binom{n}{p}}

Application : en posant

p = 0

, retrouver un résultat connu.

Pour

p = 0

: le coefficient de

x^0

est :

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

(-1)^0 \binom{n}{0} = 1

. ✓

Pour

p = 1

(plus intéressant) :

\binom{n}{0}\binom{n}{2} - \binom{n}{1}^2 + \binom{n}{2}\binom{n}{0} = -\binom{n}{1}

2\binom{n}{2} - n^2 = -n \implies n(n-1) - n^2 = -n \implies -n = -n \quad

Exercice 39

Avancé

Un sac contient 10 jetons numérotés de 1 à 10. On tire successivement et sans remise 4 jetons.

Combien de tirages ordonnés de 4 jetons peut-on effectuer ?

C'est un arrangement de 4 parmi 10 :

A_{10}^4 = 10 \times 9 \times 8 \times 7 = \boxed{5\,040}

Combien de tirages ordonnés donnent les jetons dans l'ordre croissant ?

Un tirage ordonné croissant correspond à un unique sous-ensemble de 4 jetons (l'ordre est imposé). Il y a autant de tirages ordonnés croissants que de combinaisons de 4 parmi 10 :

\binom{10}{4} = 210

Autrement dit : sur les

4! = 24

ordres possibles d'un même sous-ensemble, un seul est croissant.

\dfrac{5\,040}{24} = \boxed{210}

Combien de tirages non ordonnés contiennent exactement 2 nombres pairs et 2 impairs ?

Nombres pairs dans

\{1, \ldots, 10\}

\{2, 4, 6, 8, 10\}

, soit 5.

Nombres impairs :

\{1, 3, 5, 7, 9\}

, soit 5.

\binom{5}{2} \times \binom{5}{2} = 10 \times 10 = \boxed{100}

Combien de tirages non ordonnés contiennent des jetons dont la somme est paire ?

La somme de 4 nombres est paire si et seulement si le nombre d'impairs est pair (0, 2 ou 4).

0 impairs :

\binom{5}{0}\binom{5}{4} = 1 \times 5 = 5

2 impairs :

\binom{5}{2}\binom{5}{2} = 10 \times 10 = 100

4 impairs :

\binom{5}{4}\binom{5}{0} = 5 \times 1 = 5

5 + 100 + 5 = \boxed{110}

Vérification : Total =

\binom{10}{4} = 210

. Somme impaire :

210 - 110 = 100

. Les cas « somme paire » et « somme impaire » ne sont pas symétriques car les 4 éléments sont tirés sans remise.

Exercice 40

Avancé

On place au hasard

n

points sur un cercle (

n \geq 2

). On trace toutes les cordes possibles.

Combien de cordes peut-on tracer ?

Chaque corde relie 2 points distincts. Le nombre de cordes est :

\binom{n}{2} = \dfrac{n(n-1)}{2}

Application numérique pour

n = 6

n = 10

Pour

n = 6

\binom{6}{2} = \dfrac{6 \times 5}{2} = \boxed{15}

cordes.

Pour

n = 10

\binom{10}{2} = \dfrac{10 \times 9}{2} = \boxed{45}

cordes.

Combien de points d'intersection y a-t-il à l'intérieur du cercle si aucune intersection n'est triple (aucun point intérieur n'appartient à plus de 2 cordes) ?

Deux cordes se coupent à l'intérieur du cercle si et seulement si leurs 4 extrémités sont distinctes. En effet, 4 points sur un cercle déterminent exactement un point d'intersection intérieur (celui des 2 « diagonales » du quadrilatère convexe).

Le nombre de points d'intersection intérieurs est donc le nombre de façons de choisir 4 points parmi

n

\binom{n}{4}

Application numérique pour

n = 6

\binom{6}{4} = \binom{6}{2} = \boxed{15}

Avec 6 points sur un cercle et la condition de position générale, on obtient 15 cordes et 15 points d'intersection intérieurs.

4 problèmes de synthèse

Problème 1 — Codes d'accès et sécurité

Facile

Une entreprise utilise des codes d'accès composés de 4 caractères. Chaque caractère est soit une lettre majuscule (26 lettres), soit un chiffre (0 à 9).

Partie A — Codes sans contrainte

Combien de codes d'accès peut-on former si les répétitions sont autorisées ?

Chaque position offre

26 + 10 = 36

choix. C'est une 4-liste avec répétition de 36 caractères :

36^4 = 1\,679\,616

Il y a

\boxed{1\,679\,616}

codes possibles.

Combien de codes ont tous leurs caractères distincts ?

C'est un arrangement de 4 parmi 36 :

36 \times 35 \times 34 \times 33 = \boxed{1\,413\,720}

Partie B — Codes avec contraintes

Combien de codes commencent par une lettre et finissent par un chiffre ?

Position 1 : 26 choix (lettre). Positions 2 et 3 : 36 choix chacune. Position 4 : 10 choix (chiffre).

26 \times 36 \times 36 \times 10 = 26 \times 12\,960 = \boxed{336\,960}

Combien de codes contiennent au moins un chiffre ?

Par le complémentaire : on retire les codes composés uniquement de lettres.

Codes sans aucun chiffre :

26^4 = 456\,976

.

Codes avec au moins un chiffre :

36^4 - 26^4 = 1\,679\,616 - 456\,976 = \boxed{1\,222\,640}

On impose que le code contienne au moins une lettre ET au moins un chiffre. Combien de tels codes existe-t-il ?

Par inclusion-exclusion. On retire les codes sans lettre (que des chiffres) et les codes sans chiffre (que des lettres) :

- Codes que des chiffres :

10^4 = 10\,000

- Codes que des lettres :

26^4 = 456\,976

Codes avec au moins une lettre et au moins un chiffre :

36^4 - 10^4 - 26^4 = 1\,679\,616 - 10\,000 - 456\,976 = \boxed{1\,212\,640}

Problème 2 — Formation d'une commission municipale

Intermédiaire

Un conseil municipal est composé de 12 membres : 7 élus du parti A et 5 élus du parti B. On souhaite former une commission de 5 membres.

Partie A — Dénombrement de base

Combien de commissions de 5 membres peut-on former sans contrainte ?

\binom{12}{5} = \dfrac{12 \times 11 \times 10 \times 9 \times 8}{5!} = \dfrac{95\,040}{120} = \boxed{792}

Combien de commissions contiennent exactement 3 élus du parti A et 2 du parti B ?

\binom{7}{3} \times \binom{5}{2} = 35 \times 10 = \boxed{350}

Combien de commissions contiennent une majorité d'élus du parti A (au moins 3) ?

On additionne les cas 3A+2B, 4A+1B, 5A+0B :

\binom{7}{3}\binom{5}{2} + \binom{7}{4}\binom{5}{1} + \binom{7}{5}\binom{5}{0} = 350 + 35 \times 5 + 21 \times 1 = 350 + 175 + 21 = \boxed{546}

Partie B — Commission avec président

On désigne un président parmi les 5 membres de la commission. Combien de commissions avec président peut-on former ?

On choisit d'abord la commission (

\binom{12}{5}

), puis le président parmi les 5 membres :

\binom{12}{5} \times 5 = 792 \times 5 = \boxed{3\,960}

Alternative : on choisit d'abord le président (12 choix) puis 4 membres parmi les 11 restants :

12 \times \binom{11}{4} = 12 \times 330 = 3\,960

✓.

Combien de commissions avec président sont telles que le président appartient au parti A et que la commission contient exactement 2 élus du parti B ?

Le président est du parti A : 7 choix.

La commission contient 2 élus du parti B :

\binom{5}{2} = 10

choix.

Il reste 2 places pour des élus du parti A (parmi les 6 restants) :

\binom{6}{2} = 15

7 \times 10 \times 15 = \boxed{1\,050}

Problème 3 — Explorations autour du binôme de Newton

Difficile

On note

\binom{n}{k}

le coefficient binomial «

k

parmi

n

». On rappelle la formule du binôme :

(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k

Partie A — Calcul de sommes

En choisissant des valeurs appropriées de

a

b

, montrer que

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

On pose

a = 1

b = 1

dans la formule du binôme :

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

Donc

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

\square

En posant

a = 1

b = -1

, montrer que la somme alternée des coefficients binomiaux est nulle (pour

n \geq 1

(1+(-1))^n = 0^n = 0

pour

n \geq 1

.

Or

(1+b)^n = \sum_{k=0}^{n} \binom{n}{k} b^k

avec

b = -1

0 = \sum_{k=0}^{n} \binom{n}{k}(-1)^k = \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots + (-1)^n\binom{n}{n}

\square

En additionnant les résultats des questions 1 et 2, en déduire que la somme des

\binom{n}{k}

pour

k

pair vaut

2^{n-1}

Question 1 :

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

(

Question 2 : $\sum_{k=0}^{n} (-1)^k\binom{n}{k} = 0$ $($

En faisant $($ )+( )

(*) + (* *)

2\sum_{\substack{k=0 \ k \text{ pair}}}^{n} \binom{n}{k} = 2^n

Donc

\displaystyle\sum_{k \text{ pair}} \binom{n}{k} = 2^{n-1}

\square

Partie B — Application au calcul approché

Développer

(1+x)^6

en utilisant le binôme.

(1+x)^6 = \sum_{k=0}^{6} \binom{6}{k} x^k = 1 + 6x + 15x^2 + 20x^3 + 15x^4 + 6x^5 + x^6

En posant

x = 0{,}01

, calculer une valeur approchée de

1{,}01^6

1{,}01^6 = (1+0{,}01)^6 = 1 + 6(0{,}01) + 15(0{,}01)^2 + 20(0{,}01)^3 + \cdots

= 1 + 0{,}06 + 15 \times 10^{-4} + 20 \times 10^{-6} + \cdots

= 1 + 0{,}06 + 0{,}0015 + 0{,}00002 + \cdots \approx \boxed{1{,}06152}

Les termes suivants sont négligeables (

< 10^{-7}

Déterminer le coefficient de

x^3

dans

(2-x)^8

On écrit

(2-x)^8 = \sum_{k=0}^{8} \binom{8}{k} 2^{8-k}(-x)^k = \sum_{k=0}^{8} \binom{8}{k}(-1)^k 2^{8-k} x^k

.

Pour

k = 3

\binom{8}{3}(-1)^3 \cdot 2^5 = 56 \times (-1) \times 32 = \boxed{-1\,792}

Problème 4 — Chemins sur une grille et coefficients binomiaux

Avancé

On se place dans un quadrillage. Un chemin part de l'origine

O = (0,0)

et se dirige vers un point

M = (p,q)

(

p, q \in \mathbb{N}

) en effectuant des pas élémentaires : un pas vers la droite (D) ou un pas vers le haut (H).

Partie A — Formule générale

Montrer que le nombre de chemins de

O

M = (p,q)

est

\binom{p+q}{p}

Un chemin de

O

(p,q)

est composé de

p

pas D et

q

pas H, soit

p+q

pas au total.

Un chemin est entièrement déterminé par le choix des positions des

p

pas D parmi les

p+q

pas :

\boxed{\binom{p+q}{p}} = \binom{p+q}{q}

(On aurait aussi pu choisir les positions des

q

pas H.)

Vérifier cette formule pour

(p,q) = (3,2)

Nombre de chemins :

\binom{5}{3} = \dfrac{5 \times 4 \times 3}{3!} = 10

.

On peut les lister : DDDVV, DDVDV, DDVVD, DVDDV, DVDVD, DVVDD, VDDDV, VDDVD, VDVDD, VVDDD.

Bien 10 chemins ✓.

Partie B — Passage par un point intermédiaire

Montrer que le nombre de chemins de

O

(p,q)

passant par un point intermédiaire

I = (a,b)

(avec

0 \leq a \leq p

0 \leq b \leq q

) est

\binom{a+b}{a} \times \binom{(p-a)+(q-b)}{p-a}

Un chemin passant par

I = (a,b)

se décompose en :

- Un chemin de

O

I

\binom{a+b}{a}

chemins
- Un chemin de

I

M

\binom{(p-a)+(q-b)}{p-a}

chemins

Par le principe multiplicatif, le nombre total est :

\boxed{\binom{a+b}{a} \times \binom{(p-a)+(q-b)}{p-a}}

Application : combien de chemins de

(0,0)

(5,4)

passent par

(2,1)

puis par

(4,3)

Le chemin se décompose en 3 étapes :

(0,0) \to (2,1)

\binom{3}{2} = 3

(2,1) \to (4,3)

\binom{4}{2} = 6

(4,3) \to (5,4)

\binom{2}{1} = 2

Total :

3 \times 6 \times 2 = \boxed{36}

Partie C — Retrouver la formule de Pascal

En considérant les chemins de

O

(p,q)

, montrer que

\binom{p+q}{p} = \binom{p+q-1}{p-1} + \binom{p+q-1}{p}

Tout chemin arrivant en

(p,q)

effectue un dernier pas qui est soit D soit H :

- Si le dernier pas est D : le chemin passe par

(p-1,q)

avant. Nombre de chemins de

O

(p-1,q)

\binom{p-1+q}{p-1}

.

- Si le dernier pas est H : le chemin passe par

(p,q-1)

avant. Nombre de chemins de

O

(p,q-1)

\binom{p+q-1}{p}

.

Ces deux cas sont disjoints et couvrent tous les chemins. Donc :

\binom{p+q}{p} = \binom{p+q-1}{p-1} + \binom{p+q-1}{p}

En posant

n = p+q

k = p

, on retrouve la formule de Pascal :

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

En sommant les chemins de

O

(n,0)

(n-1,1)

(n-2,2)

\ldots

(0,n)

passant par la diagonale, retrouver que

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

Les points

(n-k, k)

pour

k = 0, 1, \ldots, n

sont tous les points de la « anti-diagonale »

x + y = n

.

Le nombre de chemins de

O

(n-k,k)

est

\binom{n}{k}

.

Or un chemin de longueur

n

(partant de

O

) arrive nécessairement en un de ces points, et les destinations sont disjointes.

Le nombre total de chemins de longueur

n

est

2^n

(chaque pas est D ou H, indépendamment).

Donc :

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

C'est une démonstration combinatoire de cette identité (sans utiliser le binôme de Newton).

S'entraîner avec les sujets du bac

Voir les sujets corrigés →

Combinatoire et dénombrement

I. Principes fondamentaux

1. Principe additif

2. Principe multiplicatif

3. Inclusion-exclusion

II. p-listes (p-uplets)

1. p-listes avec répétition

2. p-listes sans répétition (arrangements)

III. Permutations

IV. Combinaisons

1. Définition et formule

2. Propriétés des coefficients binomiaux

3. Triangle de Pascal

4. Binôme de Newton

V. Méthodes et stratégies de dénombrement

1. Schéma de décision

2. Passer par le complémentaire

3. Décomposer en étapes

4. Distinguer des cas

5. Fixer un élément

6. Placer d'abord les contraintes

Tableau récapitulatif

1. Formules essentielles

Principes fondamentaux

Les 4 configurations

Propriétés de (pn​)

Binôme de Newton

2. Schéma de décision

3. Les 3 questions à se poser

4. Les 6 méthodes

5. Tableau récapitulatif

Partie A — Codes sans contrainte

Partie B — Codes avec contraintes

Partie A — Dénombrement de base

Partie B — Commission avec président

Partie A — Calcul de sommes

Partie B — Application au calcul approché

Partie A — Formule générale

Partie B — Passage par un point intermédiaire

Partie C — Retrouver la formule de Pascal

S'entraîner avec les sujets du bac

II. $p$ -listes ( $p$ -uplets)

1. $p$ -listes avec répétition

2. $p$ -listes sans répétition (arrangements)

Propriétés de $(p n)$