Chargement de l'audio en cours
Plus

Plus

3. Combinaisons d'un ensemble fini
P.38

Mode édition
Ajouter

Ajouter

Terminer

Terminer

COURS 3


3
Combinaisons d’un ensemble fini




A
Parties d’un ensemble fini


Vocabulaire

Une partie d’un ensemble A\text{A} est un sous‑ensemble de A\text{ A}.

NOTATION

L’ensemble des parties de A\text{A} est souvent noté P(A)\mathcal{P}(\mathrm{A}).
P(A)\mathcal{P}(\mathrm{A}) est un ensemble d’ensembles.

Exemple

Si A={1 ; 2 ; 3}\text{A}=\{1 ; 2 ; 3\}, alors {1 ; 3}\{1 ; 3\} et \varnothing sont des parties de A\text{A}.

Propriété

Soit A\text{A} un ensemble fini à nn éléments. Le nombre de parties de A\text{A} est égal à 2n2^{n}.

Remarque

On a toujours P(A)\varnothing \in \mathcal{P}(\mathrm{A}).

DÉMONSTRATION

Pour constituer une partie de A\text{A}, il y a deux choix pour chaque élément de A\text{A} : l’incorporer dans cette partie ou pas. Puisque A\text{A} possède nn éléments, cela donne au total 2n2^n parties possibles. Il y a ainsi autant de parties de A\text{A} que de nn-uplet de {0 ; 1}\{0 ; 1\}, soit 2n2^n.

B
Nombre de combinaisons


Définition

Soit A\text{ A} un ensemble fini à nn éléments et kk un entier naturel inférieur ou égal à nn.
Une combinaison de kk éléments de A\text{A} est une partie de A\text{A} de cardinal k.k.
Le nombre de combinaisons de kk éléments parmi nn est noté (nk)\left(\begin{array}{l}n\\k\end{array}\right).

Remarque

Les nombres (nk)\left(\begin{array}{l}n \\k\end{array}\right) sont également appelés coefficients binomiaux et se lisent « kk parmi nn ».

Propriété

Soient nn et kk deux entiers naturels tels que knk \leqslant n. Alors :
1.(nk)=n!k!(nk)!\left(\begin{array}{l}n\\k\end{array}\right)=\dfrac{n !}{k !(n-k) !} et (nk)=(nnk)\left(\begin{array}{c}n \\k\end{array}\right)=\left(\begin{array}{c}n \\n-k\end{array}\right).
2. Relation de Pascal : si 1kn1,(nk)=(n1k1)+(n1k)1 \leqslant k \leqslant n-1,\left(\begin{array}{l}n \\k\end{array}\right)=\left(\begin{array}{l}n-1 \\k-1\end{array}\right)+\left(\begin{array}{c}n-1 \\k\end{array}\right).
3. De plus,(n0)=1\left(\begin{array}{l}n \\0\end{array}\right)=1. Si n1,(n1)=nn \geqslant 1,\left(\begin{array}{l}n \\1\end{array}\right)=n et si n2,(n2)=n(n1)2n \geqslant 2,\left(\begin{array}{l}n \\2\end{array}\right)=\dfrac{n(n-1)}{2}.

Remarque

La 2e égalité du point 1. traduit le fait que choisir kk objets parmi nn revient à choisir les nkn - k objets qu’on ne prend pas.

DÉMONSTRATION

Voir Activité
C
p. 35
, exercice
94
p. 50
et exercice
105
p. 35
.

Remarque

Les combinaisons ne font pas apparaître l’ordre des éléments.

Propriété

Soit nn un entier naturel. Alors k=0n(nk)=2n\displaystyle\sum_{k=0}^{n}\left(\begin{array}{l} n \\k\end{array}\right)=2^{n}.

DÉMONSTRATION

Soit A\text{A} un ensemble fini à nn éléments. Pour tout entier naturel kk inférieur ou égal à nn, on note Ak\text{A}_k l’ensemble des parties de A\text{A} composées de kk éléments. On a ainsi Card(Ak)=(nk)\operatorname{Card}\left(\mathrm{A}_{k}\right)=\left(\begin{array}{l} n \\ k \end{array}\right). Les Ak\text{A}_k sont deux à deux disjoints et leur réunion est P(A)\mathcal{P}(\mathrm{A}). Ainsi :
2n=Card(P(A))=Card(A1An)=k=0nCard(Ak)=k=0n(nk)2^{n}=\operatorname{Card}(\mathcal{P}(\mathrm{A}))=\operatorname{Card}\left(\mathrm{A}_{1} \cup \ldots \cup \mathrm{A}_{n}\right)=\displaystyle\sum_{k=0}^{n} \operatorname{Card}\left(\mathrm{A}_{k}\right)=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right).

Application et méthode - 3

Énoncé

Dans une grille comportant les nombres 0 à 9 et les lettres A\text{A} à F\text{F}, il faut choisir trois nombres et deux lettres. Combien de grilles différentes existe‑t‑il ?

Solution


Pour les nombres, il existe (103)=10!3!7!=120\left(\begin{array}{c}10 \\3\end{array}\right)=\dfrac{10 !}{3 !\,7 !}=120 combinaisons possibles.
Pour les lettres, on dispose de (62)=15\left(\begin{array}{l}6 \\2\end{array}\right)=15 combinaisons.
Au total, il y a donc 120×15=1800120 \times 15=1\,800 grilles possibles.

Pour s'entraîner : exercices 43 et 44 p. 45

Méthode


Cocher des nombres ou des lettres sur une grille revient à choisir un ensemble de nombres ou de lettres et non pas un kk-uplet : il n’y a pas d’ordre.
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.