Rappel · 1

Un restaurant propose un menu composé d'une entrée choisie parmi 4 entrées et d'un plat choisi parmi 6 plats. Combien de menus différents peut-on composer ?

Remarque

D'après le principe multiplicatif du produit cartésien, si un premier choix offre $4$ possibilités et un second choix indépendant offre $6$ possibilités, le nombre total de couples possibles est $\text{card}(E \times F) = 4 \times 6 = 24$ .

Définition · 2

Définition et Théorème

Soit $E$ un ensemble fini non vide de cardinal $n$ et $p$ un entier naturel non nul.

$E^p = \underbrace{E \times E \times \dots \times E}_{p \text{ fois}}$

Un élément de $E^p$ est un $p$ -uplet $(x_1, x_2, \dots, x_p)$ , c'est-à-dire une liste ordonnée de $p$ éléments de $E$ , deux à deux distincts ou non.

$\text{card}(E^p) = (\text{card}(E))^p = n^p$

Le nombre d'applications d'un ensemble à $p$ éléments dans un ensemble à $n$ éléments est également égal à $n^p$ .

Exemple travaillé · 3

Un code d'accès est composé d'une lettre choisie parmi $\{A, B, C\}$ suivie de 3 chiffres choisis parmi $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ (les répétitions de chiffres sont autorisées). Déterminer le nombre de codes possibles.

1

La formation du code se décompose en deux choix indépendants successifs : le choix de la lettre, puis le choix de la séquence de 3 chiffres.

2

Pour la lettre, il y a 3 choix possibles dans l'ensemble $\{A, B, C\}$ .

3

Pour la séquence de 3 chiffres avec répétition, il s'agit d'un 3-uplet d'un ensemble à 9 éléments, soit $9^3 = 729$ possibilités.

4

N = 3 \times 9^3 = 3 \times 729 = 2187

5

Il y a donc $2187$ codes d'accès possibles.

Exemple travaillé · 4

Trente voyageurs montent dans un bus qui dessert dix stations. Chaque voyageur choisit librement et indépendamment sa station de descente. De combien de façons peut-on envisager les descentes des trente voyageurs ?

1

Chaque voyageur choisit une station parmi les 10 stations possibles.

2

L'ensemble des 30 voyageurs forme l'ensemble de départ ( $p = 30$ ) et l'ensemble des 10 stations forme l'ensemble d'arrivée ( $n = 10$ ).

3

Une configuration de descente correspond à une application de l'ensemble des 30 voyageurs vers l'ensemble des 10 stations.

4

\text{Nombre de choix} = 10^{30}

Piège classique · 5

Quatre amis entrent dans un cinéma qui propose trois salles différentes. Chacun choisit une salle. Combien y a-t-il de choix possibles pour le groupe ?

Attention

Calculer $4^3 = 64$ en prenant le nombre de personnes comme base.

À la place : Il faut calculer $3^4 = 81$ . Chaque ami parmi les 4 a 3 choix de salle indépendants : $3 \times 3 \times 3 \times 3 = 3^4$ .

Vérification · 6

Un questionnaire comporte 5 questions à choix multiples. Pour chaque question, 3 réponses sont proposées et une seule est cochée. Combien y a-t-il de grilles de réponses possibles ?

Remarque

Pour chacune des 5 questions indépendantes, il y a 3 options de réponse. Le nombre total de grilles de réponses possibles est $3^5 = 243$ .

Point de départ · 7

On veut aligner 3 élèves sur 3 chaises numérotées 1, 2 et 3. Combien de dispositions différentes peut-on former ?

Remarque

Pour la 1ère chaise, il y a 3 élèves possibles. Pour la 2ème, il ne reste que 2 élèves disponibles. Pour la 3ème, il ne reste qu'un seul élève. Par le principe multiplicatif, le nombre de dispositions est $3 \times 2 \times 1 = 6$ .

Définition · 8

Définition et Théorème

Soit $E$ un ensemble fini non vide de cardinal $n$ .

On appelle permutation des $n$ éléments de $E$ tout $n$ -uplet d'éléments deux à deux distincts de $E$ .

Pour tout entier naturel non nul $n$ , on appelle factorielle de $n$ , et on note $n!$ , l'entier :

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

Le nombre de permutations des $n$ éléments de $E$ est égal à $n!$ .

0! = 1

Exemple travaillé · 9

On considère le mot $\text{NATUREL}$ . Combien d'anagrammes de ce mot peut-on former ?

1

Le mot $\text{NATUREL}$ contient 7 lettres, et ces 7 lettres sont toutes deux à deux distinctes.

2

Former une anagramme revient à ordonner ces 7 lettres distinctes sur 7 positions, c'est-à-dire former une permutation de l'ensemble des 7 lettres.

3

N = 7!

4

On calcule le produit : $7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5040$ .

5

Il y a donc $5040$ anagrammes possibles.

Exemple travaillé · 10

À partir des 7 lettres distinctes du mot $\text{BLANCHE}$ , combien d'anagrammes peut-on former dans lesquelles les lettres H et E apparaissent consécutivement dans cet ordre (le bloc $\text{HE}$ ) ?

1

Puisque la lettre E doit suivre immédiatement la lettre H, on regroupe le couple $(\text{HE})$ en un seul bloc indissociable.

2

On dénombre les entités à permuter : le bloc $(\text{HE})$ et les 5 autres lettres distinctes (B, L, A, N, C), ce qui fait $1 + 5 = 6$ entités au total.

3

Ces 6 entités permutent librement entre elles.

4

N = 6!

5

On calcule : $6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$ anagrammes.

Piège classique · 11

On place 5 livres distincts sur une étagère, dont 2 livres de Mathématiques et 3 livres d'Informatique. De combien de façons peut-on les ranger si les 2 livres de Mathématiques doivent obligatoirement être côte à côte (dans un ordre quelconque) ?

Attention

Calculer uniquement $4! = 24$ en oubliant que les 2 livres de Mathématiques peuvent permuter à l'intérieur de leur bloc.

À la place : On permute d'abord les 4 entités (le bloc de Mathématiques et les 3 livres d'Informatique), soit $4! = 24$ façons. Puis on multiplie par les $2! = 2$ ordres possibles des livres à l'intérieur du bloc : $4! \times 2! = 48$ .

Vérification · 12

On dispose de 6 personnes, dont 3 amies qui souhaitent impérativement s'asseoir côte à côte sur un banc à 6 places. Combien de dispositions différentes peut-on réaliser ?

Remarque

On groupe les 3 amies en un bloc unique. On permute 4 entités (le bloc et les 3 autres personnes), soit $4! = 24$ manières. À l'intérieur du bloc, les 3 amies permutent de $3! = 6$ manières. Le nombre total de dispositions est $4! \times 3! = 24 \times 6 = 144$ .

Point de départ · 13

Dans une classe de 10 élèves, on doit élire un président et un trésorier (une même personne ne peut pas cumuler les deux fonctions). Si Ali est élu président et Sara trésorière, est-ce la même issue que si Sara est présidente et Ali trésorier ?

Remarque

Non, les deux postes étant distincts, le couple (Ali, Sara) et le couple (Sara, Ali) représentent deux attributions différentes. L'ordre de choix des personnes détermine directement l'issue.

Définition · 14

Définition et Théorème

Soit $E$ un ensemble fini non vide de cardinal $n$ et $p$ un entier naturel tel que $1 \le p \le n$ .

On appelle arrangement de $p$ éléments de $E$ tout $p$ -uplet d'éléments deux à deux distincts de $E$ .

Le nombre d'arrangements de $p$ éléments choisis parmi $n$ est noté $A_n^p$ et vaut :

$A_n^p = n \times (n-1) \times \dots \times (n-p+1) = \frac{n!}{(n-p)!}$

A_n^0 = 1

Exemple travaillé · 15

Une association comporte 50 membres. On doit élire un bureau composé de 4 personnes occupant des postes distincts : un président, un vice-président, un secrétaire et un trésorier. Combien de bureaux différents peut-on former ?

1

On doit choisir 4 personnes parmi 50 et leur attribuer 4 fonctions distinctes sans cumul possible.

2

L'ordre d'attribution a de l'importance et les personnes choisies sont toutes distinctes (tirage sans remise).

3

Il s'agit donc d'un arrangement de 4 éléments parmi 50.

4

A_{50}^4 = 50 \times 49 \times 48 \times 47

5

On calcule le produit : $A_{50}^4 = 5527200$ bureaux possibles.

Exemple travaillé · 16

Combien de nombres de 3 chiffres distincts peut-on former avec les chiffres de l'ensemble $\{2, 3, 5, 6, 7, 9\}$ ?

1

Former un nombre de 3 chiffres distincts revient à choisir et ordonner 3 chiffres différents parmi les 6 chiffres disponibles.

2

L'ordre des chiffres modifie la valeur du nombre et la répétition d'un même chiffre est exclue.

3

Il s'agit donc d'un arrangement de 3 éléments parmi 6.

4

A_6^3 = 6 \times 5 \times 4

5

On calcule : $A_6^3 = 120$ nombres possibles.

Piège classique · 17

Dans une course hippique réunissant 8 chevaux, on cherche le nombre de tiercés gagnants dans l'ordre (les 3 premiers chevaux à franchir la ligne d'arrivée). Quel calcul modélise cette situation ?

Attention

Utiliser une combinaison $C_8^3$ en considérant uniquement le sous-ensemble des 3 chevaux sans tenir compte de leur ordre d'arrivée.

À la place : L'ordre d'arrivée est primordial (1er, 2ème, 3ème) et un même cheval ne peut pas occuper deux places : il s'agit d'un arrangement $A_8^3 = 8 \times 7 \times 6 = 336$ .

Vérification · 18

Un sac contient 6 jetons numérotés de 10 à 15. On tire successivement et sans remise 3 jetons du sac. Combien de tirages différents peut-on obtenir ?

Remarque

Les mentions « successivement » (l'ordre intervient) et « sans remise » (éléments distincts) caractérisent un arrangement de 3 éléments parmi 6 : $A_6^3 = 6 \times 5 \times 4 = 120$ tirages.

Point de départ · 19

On tire 3 cartes simultanément d'un paquet de 5 cartes distinctes $\{A, B, C, D, E\}$ . Si on tirait ces cartes dans l'ordre, on aurait $A_5^3 = 60$ tirages ordonnés. Pourquoi le tirage simultané donne-t-il un nombre d'issues plus petit ?

Dans un tirage simultané, l'ordre n'intervient pas : les triplets $(A, B, C)$ , $(A, C, B)$ , $(B, A, C)$ , $(B, C, A)$ , $(C, A, B)$ et $(C, B, A)$ forment une seule et même main.

Chaque groupe de 3 cartes possède $3! = 6$ ordres possibles. Pour obtenir le nombre de mains sans tenir compte de l'ordre, on divise le nombre d'arrangements par $3!$ :

$\frac{A_5^3}{3!} = \frac{60}{6} = 10$

Définition · 20

Définition et Théorème

Soit $E$ un ensemble fini non vide de cardinal $n$ et $p$ un entier naturel tel que $0 \le p \le n$ .

On appelle combinaison de $p$ éléments de $E$ toute partie (ou sous-ensemble) à $p$ éléments de $E$ .

Le nombre de combinaisons de $p$ éléments parmi $n$ est noté $C_n^p$ (ou $\binom{n}{p}$ ) et vaut :

$C_n^p = \frac{A_n^p}{p!} = \frac{n!}{p!(n-p)!}$

C_n^0 = 1 \quad \text{et} \quad C_n^n = 1

Un tirage simultané de $p$ éléments parmi $n$ correspond à une combinaison de $p$ éléments parmi $n$ : l'ordre ne compte pas et les éléments sont deux à deux distincts.

Exemple travaillé · 21

Une urne contient 3 boules blanches et 5 boules noires. On tire simultanément 4 boules de l'urne. Déterminer le nombre de tirages contenant exactement 2 boules blanches et 2 boules noires.

1

Le tirage est simultané, l'ordre n'a donc pas d'importance et les boules sont sans remise : on utilise les combinaisons.

2

Choisir 2 boules blanches parmi les 3 boules blanches disponibles correspond à $C_3^2 = 3$ choix.

3

Choisir 2 boules noires parmi les 5 boules noires disponibles correspond à $C_5^2 = \frac{5 \times 4}{2 \times 1} = 10$ choix.

4

N = C_3^2 \times C_5^2 = 3 \times 10 = 30

5

Il y a donc $30$ tirages contenant exactement 2 boules blanches et 2 boules noires.

Exemple travaillé · 22

Dans une urne contenant 3 boules blanches et 5 boules noires, on tire simultanément 4 boules. Déterminer le nombre de tirages contenant au moins une boule blanche.

1

Le nombre total de tirages simultanés de 4 boules parmi les 8 boules de l'urne est $C_8^4 = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70$ .

2

L'événement contraire de « obtenir au moins une boule blanche » est « n'obtenir aucune boule blanche », c'est-à-dire tirer 4 boules parmi les 5 boules noires.

3

Le nombre de tirages ne contenant aucune boule blanche est $C_5^4 = 5$ .

4

N = C_8^4 - C_5^4 = 70 - 5 = 65

5

Il y a donc $65$ tirages contenant au moins une boule blanche.

Piège classique · 23

On forme un comité de 3 personnes choisies parmi 5 hommes et 4 femmes. On veut dénombrer les comités comprenant au moins une femme. Quelle démarche est mathématiquement correcte ?

Attention

Choisir 1 femme par $C_4^1$ puis choisir librement les 2 autres membres parmi les 8 personnes restantes par $C_8^2$ , ce qui donne $C_4^1 \times C_8^2 = 112$ .

À la place : Cette démarche produit un surcomptage : un comité contenant 2 femmes (par exemple Sara et Mariem) est compté deux fois (une fois avec Sara fixée et Mariem choisie parmi les 8, et une fois avec Mariem fixée et Sara choisie parmi les 8). La méthode correcte passe par l'événement contraire : $C_9^3 - C_5^3 = 84 - 10 = 74$ .

Vérification · 24

Dans un jeu de 32 cartes (contenant 4 as), on tire simultanément une main de 5 cartes. Combien de mains contiennent au moins un as ?

Remarque

Le nombre total de mains possibles est $C_{32}^5 = 201376$ . Le nombre de mains ne contenant aucun as (5 cartes parmi les 28 cartes non-as) est $C_{28}^5 = 98280$ . Le nombre de mains contenant au moins un as est $C_{32}^5 - C_{28}^5 = 201376 - 98280 = 103096$ .

Point de départ · 25

Dans une classe de 10 élèves, on doit choisir 8 élèves pour former une équipe. Combien d'équipes distinctes peut-on former ? Est-il plus rapide de choisir les 8 élèves qui partent ou les 2 élèves qui restent ?

Choisir les 8 élèves à inclure revient exactement à désigner les 2 élèves exclus de l'équipe.

$C_{10}^8 = C_{10}^2$

Remarque

Calculer $C_{10}^2 = \frac{10 \times 9}{2 \times 1} = 45$ est immédiat, alors que $C_{10}^8$ comporterait 8 facteurs au numérateur et au dénominateur.

Définition · 26

Propriétés algébriques fondamentales

Soient $n$ et $p$ deux entiers naturels tels que $0 \le p \le n$ .

Propriété de symétrie : Choisir une partie à $p$ éléments parmi $n$ équivaut à choisir son complémentaire à $n-p$ éléments.

$C_n^p = C_n^{n-p}$

Relation fondamentale de Pascal : Pour $1 \le p \le n-1$ , en isolant un élément particulier, on sépare les parties qui le contiennent de celles qui ne le contiennent pas.

$C_n^p = C_{n-1}^p + C_{n-1}^{p-1}$

C_n^0 = 1, \quad C_n^1 = n, \quad C_n^n = 1

Exemple travaillé · 27

Montrer que pour tous entiers naturels $n$ et $p$ admissibles : $C_n^p + 2C_n^{p+1} + C_n^{p+2} = C_{n+2}^{p+2}$ .

1

On sépare le terme central $2C_n^{p+1}$ en $C_n^{p+1} + C_n^{p+1}$ pour regrouper les termes consécutifs.

2

C_n^p + 2C_n^{p+1} + C_n^{p+2} = (C_n^p + C_n^{p+1}) + (C_n^{p+1} + C_n^{p+2})

3

On applique la relation de Pascal à chaque parenthèse : $C_n^p + C_n^{p+1} = C_{n+1}^{p+1}$ et $C_n^{p+1} + C_n^{p+2} = C_{n+1}^{p+2}$ .

4

(C_n^p + C_n^{p+1}) + (C_n^{p+1} + C_n^{p+2}) = C_{n+1}^{p+1} + C_{n+1}^{p+2}

5

On applique une seconde fois la relation de Pascal à cette dernière somme :

6

C_{n+1}^{p+1} + C_{n+1}^{p+2} = C_{n+2}^{p+2}

Exemple travaillé · 28

Résoudre dans $\mathbb{N}$ l'équation : $C_n^2 + C_n^3 = 2n^2 - 2n$ .

1

Condition d'existence : les coefficients $C_n^2$ et $C_n^3$ imposent que $n \in \mathbb{N}$ et $n \ge 3$ .

2

D'après la formule de Pascal, $C_n^2 + C_n^3 = C_{n+1}^3$ .

3

L'équation devient $C_{n+1}^3 = 2n(n-1)$ , soit en développant le coefficient binomial :

4

\frac{(n+1)n(n-1)}{6} = 2n(n-1)

5

Puisque $n \ge 3$ , le produit $n(n-1)$ est strictement non nul : on simplifie les deux membres par $n(n-1)$ .

6

\frac{n+1}{6} = 2 \iff n+1 = 12 \iff n = 11

7

La valeur $11$ satisfait la condition $n \ge 3$ . L'ensemble des solutions dans $\mathbb{N}$ est $S = \{11\}$ .

Piège classique · 29

Pour résoudre dans $\mathbb{N}$ l'équation $C_n^3 = 4C_n^4$ , quelle est la condition d'existence sur l'inconnue $n$ ?

Attention

Poser seulement $n \ge 3$ en ne regardant que le membre de gauche.

À la place : Le membre de droite contient $C_n^4$ , qui n'est défini que pour $n \ge 4$ . L'inconnue doit satisfaire simultanément $n \ge 3$ et $n \ge 4$ , soit $n \ge 4$ .

Vérification · 30

En utilisant la formule de Pascal puis la propriété de symétrie, calculer la valeur exacte de la somme $C_8^6 + C_8^7$ .

Remarque

D'après la formule de Pascal, $C_8^6 + C_8^7 = C_9^7$ . Par symétrie, $C_9^7 = C_9^{9-7} = C_9^2 = \frac{9 \times 8}{2 \times 1} = 36$ .

Point de départ · 31

Comment développer $(a+b)^n$ pour un entier naturel $n$ quelconque ?

Pour $n = 2$ , on sait que :

$(a+b)^2 = a^2 + 2ab + b^2 = C_2^0 a^2 + C_2^1 ab + C_2^2 b^2$

Pour $n = 3$ , on sait que :

$(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 = C_3^0 a^3 + C_3^1 a^2b + C_3^2 ab^2 + C_3^3 b^3$

Remarque

Les coefficients du développement correspondent exactement aux coefficients binomiaux $C_n^k$ de la ligne $n$ du triangle de Pascal.

Définition · 32

Théorème du binôme de Newton et ensemble des parties

Soient $a$ et $b$ deux nombres réels et $n$ un entier naturel non nul.

$(a+b)^n = \sum_{k=0}^n C_n^k a^{n-k}b^k = C_n^0 a^n + C_n^1 a^{n-1}b + \dots + C_n^n b^n$

Soit $E$ un ensemble fini de cardinal $n$ . L'ensemble de toutes les parties de $E$ est noté $\mathcal{P}(E)$ .

$\text{card}(\mathcal{P}(E)) = \sum_{k=0}^n C_n^k = 2^n$

Exemple travaillé · 33

Soit $n$ un entier naturel non nul. Calculer la somme $S_1 = C_n^0 + C_n^1 + \dots + C_n^n$ et la somme alternée $S_2 = C_n^0 - C_n^1 + C_n^2 - \dots + (-1)^n C_n^n$ .

1

Pour la somme $S_1$ , on applique la formule du binôme de Newton en posant $a = 1$ et $b = 1$ .

2

(1+1)^n = \sum_{k=0}^n C_n^k 1^{n-k} 1^k = \sum_{k=0}^n C_n^k = S_1

3

Comme $1+1=2$ , on obtient $S_1 = 2^n$ .

4

Pour la somme alternée $S_2$ , on applique la formule du binôme de Newton en posant $a = 1$ et $b = -1$ .

5

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

6

Comme $n \ge 1$ , $(1-1)^n = 0^n = 0$ , donc $S_2 = 0$ .

Exemple travaillé · 34

Soit $n$ un entier naturel non nul. Calculer la somme pondérée $S = C_n^1 + 2C_n^2 + 3C_n^3 + \dots + nC_n^n$ .

1

Pour tout entier $k$ tel que $1 \le k \le n$ , on simplifie le produit $k C_n^k$ en utilisant la définition factorielle :

2

k C_n^k = k \times \frac{n!}{k!(n-k)!} = n \times \frac{(n-1)!}{(k-1)!((n-1)-(k-1))!} = n C_{n-1}^{k-1}

3

On réécrit la somme $S$ en factorisant par $n$ :

4

S = \sum_{k=1}^n k C_n^k = \sum_{k=1}^n n C_{n-1}^{k-1} = n \sum_{k=1}^n C_{n-1}^{k-1}

5

En posant $j = k-1$ , la somme d'indice $j$ allant de $0$ à $n-1$ représente la somme complète des coefficients de la ligne $n-1$ du triangle de Pascal, qui vaut $2^{n-1}$ .

6

S = n \cdot 2^{n-1}

Piège classique · 35

Un ensemble $E$ contient 6 éléments. On cherche le nombre de parties non vides de $E$ . Quelle est la valeur exacte ?

Attention

Calculer $2^6 = 64$ en oubliant que ce nombre inclut l'ensemble vide.

À la place : L'ensemble des parties $\mathcal{P}(E)$ contient $2^6 = 64$ sous-ensembles au total. Parmi eux figure la partie vide $\emptyset$ , qui correspond à $C_6^0 = 1$ . Le nombre de parties non vides est donc $2^6 - 1 = 64 - 1 = 63$ .

Vérification · 36

Calculer la valeur de la somme $S = C_4^0 + 2 C_4^1 + 2^2 C_4^2 + 2^3 C_4^3 + 2^4 C_4^4$ .

Remarque

D'après la formule du binôme de Newton avec $a = 1$ et $b = 2$ au rang $n = 4$ : $S = (1+2)^4 = 3^4 = 81$ .

Dénombrement — cours

Le cours

Définition et Théorème

Définition et Théorème

Définition et Théorème

Définition et Théorème

Propriétés algébriques fondamentales

Théorème du binôme de Newton et ensemble des parties

Chapitres liés

Continuer sur Lumio