Exercices Denombrement et Analyse Combinatoire
Rappel
- \((\Omega, \mathcal{T}, p)\) : espace probabilisé.
- Cardinalité :
- \(\text{card}(A \cup B) = \text{card}(A) + \text{card}(B) - \text{card}(A \cap B)\)
- Si \(A\) et \(B\) sont incompatibles : \(\text{card}(A \cup B) = \text{card}(A) + \text{card}(B)\)
- Si \(A\) et \(B\) sont deux ensembles finis :
- \(A \times B = \{(x, y) / x \in A, \, y \in B\}\)
- \(\text{card}(A_1 \times \dots \times A_n) = \text{card}(A_1) \dots \text{card}(A_n)\)
- Produits cartésiens :
- \(\{(x_1, \dots, x_n) / x_i \in A_i, \, \forall i \in [1, n]\}\)
- Si \(A_i = A\) pour tous les \(i\), alors :
- \(A^n = \{(x_1, \dots, x_n) / x_i \in A, \, \forall i \in [1, n]\}\)
- \(\text{card}(A^n) = (\text{card}(A))^n\)
- Combien de possibilités de choisir \(p\) éléments d'un ensemble \(E\) à \(n\) éléments avec ordre ?
- On obtient des \(p\)-uplets d'éléments de \(E\).
- Ordre et répétition :
- \(\{(x_1, \dots, x_p) / x_i \in E, \, \forall i \in [1, p]\} = E^p\)
- Le nombre est : \(\text{card}(E^p) = (\text{card}(E))^p = n^p\)
- Modèle type : tirages successifs avec remise (ordre et répétition)
- Exemples de tirages :
- \(\{x_1, \dots, x_n\}\)
- \((x_1, x_2, \dots, x_n)\)
- \(\{x, y\} \neq \{y, x\}\) si \(x \neq y\)
- Ordre et pas de répétition : Ce sont des arrangements de \(p\) éléments de \(E\).
- Le nombre d'arrangements est \(A_n^p = \frac{n!}{(n - p)!}\) si \(p \leq n\).
- Si \(p > n\), alors \(A_n^p = 0\).
- Cas particulier : si \(n = p\), alors ce sont les permutations des éléments de \(E\), et il y en a \(n!\).
- Pas d'ordre et pas de répétition :Ce sont les combinaisons de \(p\) éléments parmi les \(n\) éléments de \(E\).
- Le nombre de combinaisons est \(\binom{n}{p} = C_n^p = \frac{n!}{p!(n - p)!}\) si \(p \leq n\).
- Si \(p > n\), alors \(\binom{n}{p} = 0\).
- Exemples de calculs de combinaisons :
- \(\binom{n}{0} = 1\)
- \(\binom{n}{1} = n\)
- \(\binom{n}{n} = 1\)
- \(\binom{n}{n-1} = n\)
- \(\binom{n}{2} = \frac{n(n-1)}{2}\)
- \(\binom{n}{p} + \binom{n}{p-1} = \binom{n+1}{p}\)
Exercice 1
- Dans mon armoire, il y a , et
. Je peux distinguer toutes ces chaussures les unes des autres. Un
matin, mal réveillé, je choisis .
- Combien y-a-t-il de ?
Correction
-
On choisit 2 chaussures parmi 20. Il y a \( \binom{20}{2} = 190 \) choix possibles.
- Combien y-a-t-il de choix où j'obtiens ?
Correction
-
Soit \( E_i = \{ (x, y) \mid x, y \text{ chaussures ; couleur avec } x \neq y \} \).
- \( E_N = \{ (x, y) \mid x, y \text{ chaussures noires avec } x \neq y \} \)
- \( E_M = \{ (x, y) \mid x, y \text{ chaussures marrons avec } x \neq y \} \)
- \( E_B = \{ (x, y) \mid x, y \text{ chaussures blanches avec } x \neq y \}
\)
- Or \( E_N \), \( E_M \), \( E_B \) sont deux à deux incompatibles, donc :
-
\( \text{card}(E_N \cup E_M \cup E_B) = \text{card}(E_N) + \text{card}(E_M)
+ \text{card}(E_B) \)
-
\( \text{card}(E_N \cup E_M \cup E_B) = \binom{10}{2} + \binom{6}{2} +
\binom{4}{2} = 66 \)
- Combien de choix amènent ?
Correction
-
Chaque chaussure gauche a 10 choix possibles pour la chaussure droite. Donc :
-
\( \text{card}(G \times D) = \text{card}(G) \times \text{card}(D) = 10
\times 10 = 100 \) choix possibles
- Combien de choix amènent ?
Correction
-
On a :
- \( A_N = \{ (x, y) \mid x : \text{ chaussure noire gauche } ; y : \text{
chaussure noire droite } \} \)
- \( A_M = \{ (x, y) \mid x : \text{ chaussure marron gauche } ; y : \text{
chaussure marron droite } \} \)
- \( A_B = \{ (x, y) \mid x : \text{ chaussure blanche gauche } ; y : \text{
chaussure blanche droite } \} \)
- Or : \( A_N \), \( A_M \), \( A_B \) sont deux à deux incompatibles, donc :
-
\( \text{card}(A_N \cup A_M \cup A_B) = \text{card}(A_N) +
\text{card}(A_M) + \text{card}(A_B) \)
-
\( = 5^2 + 3^2 + 2^2 = 38 \) choix possibles
- Combien de choix amènent ?
Correction
- On compte d'abord le nombre de choix de deux chaussures qui amènent la même paire :
il y en a \(10\) (autant que de paires de chaussures).
- Par différence, le nombre de choix qui amènent à deux chaussures qui ne sont pas de
la même paire est
\( \binom{20}{2} - 10 = 180 \).
Exercice 2
- Un sac contient et . On suppose que les jetons sont (numérotés par exemple) et on effectue un tirage de
de ce sac.
- On suppose que les jetons sont tirés successivement en à chaque fois le jeton tiré.
- Donner le nombre de résultats possibles.
Correction
-
Les tirages sont successifs (avec ordre) et avec remise (répétition), donc il y
a :
\(13^6\) résultats possibles.
- Combien de ces résultats amènent
- exactement ?
Correction
-
Pour obtenir un jeton noir, on doit choisir à quel tirage on va tirer le
jeton noir,
donc on a :
\(\binom{6}{1}\) choix possibles.
Ensuite, à chaque tirage, on a \(8\) choix possibles de jeton noir et, pour
les
\(5\) autres tirages, on a \(5\) choix possibles de jeton blanc.
Alors, on a :
- \(\binom{6}{1} \times 8 \times 5 \times 5 \times 5 \times 5 = 6 \times 8
\times 5^5\) résultats
- au moins ?
Correction
-
On a:
- \(\text{card}(\overline{A})\) : , donc \(5^6\)
- \(\text{card}(A) = \text{card}(\Omega) - \text{card}(\overline{A})\)
- \(\text{card}(A) = 13^6 - 5^6\)
- au plus ?
Correction
-
On a :
- \( {T_B} = \overline{A}= \{ \text{Pas de jeton noir} \} \)
- \( T_{1N} = \{ \text{exactement 1 jeton noir} \} \)
- Or \( {T_B} \) et \( T_{1N} \) sont incompatibles, donc :
- \( \text{card}({T_B} \cup T_{1N}) =
\text{card}({T_B}) + \text{card}(T_{1N}) \)
- \( \text{card}({T_B} \cup T_{1N}) = 5^6 + 6 \times 8 \times
5^5 \)
- de jetons noirs que de jetons blancs ?
Correction
-
On a :
- On commence par fixer les tirages parmi les 6 pour lesquels on a
tiré un jeton noir : il y en a \( \binom{6}{4} \).
- Ce choix fixé, il y a \( 8^4 \) choix pour les jetons noirs et \(
5^2 \) choix pour les jetons blancs.
- Finalement, on obtient : \( \binom{6}{4} \times 8^4 \times 5^2 \)
tirages possibles.
Exercice 3
- On dispose de CD dont de
Bach et de Mozart.
- Combien y a-t-il de façons de ranger les CD sur une étagère de sorte que les disques de ?
Correction
- On doit choisir les places pour les disques de . Il y a donc \( \binom{7}{1} \)
façons.
- Ensuite, il y a \( 4! \) façons possibles pour les disques de , puis pour
les autres disques, \( 6! \).
- Au total, on a : \( \binom{7}{1} \times 4! \times 6! \) .
- qu'à la fois les disques de et les disques de restent ?
Correction
- Même principe :
- On a \( \binom{3}{1} \times 4! \times 4! \times 2! \times 2 \) façons.
- Combien y a-t-il de façons de ranger les CD de sorte que les 8 CD de Bach ou Mozart restent
groupés, mais en alternant ?
Correction
- Il y a deux façons :
-
- Donc : \( \binom{3}{1} \times 4! \times 4! \times 2! \times 2 \)
Exercice 4
- Calculer les expressions suivantes :
- \(\sum_{k=0}^{n} (-1)^k \binom{n}{k}\)
Correction
- On a : \((a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}\)
- Soit \(a = -1\) et \(b = 1\), alors :
\(
\sum_{k=0}^{n} \binom{n}{k} (-1)^k = 0^n
\)
- Donc :
- Si \(n = 0\), alors \(\sum_{k=0}^{n} (-1)^k = 1\)
- Si \(n \geq 1\), alors \(\sum_{k=0}^{n} (-1)^k = 0\)
- En résumé :
\(
\sum_{k=0}^{n} \binom{n}{k} (-1)^k =
\begin{cases}
1 & \text{si } n = 0 \\
0 & \text{si } n \geq 1
\end{cases}
\)
- \(\sum_{k=0}^{n} k \binom{n}{k}\)
Correction
Methode 1
- On a : \(k \binom{n}{k} = k \frac{n!}{k!(n-k)!} =
\frac{n!}{(k-1)!(n-k)!} = \frac{n (n-1)!}{(k-1)!(n-k)!} = n
\binom{n-1}{k-1}\)
- Posons \(j = k - 1\)
- Si \(k = 0 \Rightarrow j = 0\)
- Si \(k = n \Rightarrow j = n - 1\)
- Donc :
\(
\sum_{k=0}^{n} k \binom{n}{k} = \sum_{j=0}^{n-1} n
\binom{n-1}{j} = n \sum_{j=0}^{n-1} \binom{n-1}{j}
\)
- Or, on sait que :
\(
\sum_{k=0}^{n} \binom{n}{k} = 2^n
\)
donc :
\(
\sum_{k=0}^{n} k \binom{n}{k} = n \times 2^{n-1}
\)
Methode 2
- Soit \(f(x) = \sum_{k=0}^{n} \binom{n}{k} a^k\)
- On a :
\(
(1 + a)^n = \sum_{k=0}^{n} \binom{n}{k} a^k
\)
- On dérive :
\(
[(1 + a)^n]' = \sum_{k=0}^{n} \binom{n}{k} k a^{k-1}
\)
donc :
\(
n(1 + a)^{n-1} = \sum_{k=0}^{n} k \binom{n}{k} a^{k-1}
\)
- Si \(a = 1\), on a :
\(
\sum_{k=0}^{n} k \binom{n}{k} = n \times 2^{n-1}
\)
Exercice 5
- On compose un numéro de téléphone à 10 chiffres.
- Quelle est le nombre de possibilités que tous les chiffres soient distincts ?
Correction
- Avec ordre et sans répétition (distinction des chiffres) :
- \(A_{10}^{10} = 10!\)
- Quelle est le nombre de possibilités qu'il commence par 01 ?
Correction
- Les deux premiers chiffres sont 0 et 1, donc il reste 8 chiffres à choisir :
- \(A_{8}^{8} = 8!\)
- Quelle est le nombre de possibilités que ses chiffres forment une suite strictement croissante ?
Correction
- La seule façon pour que les chiffres forment une suite strictement croissante est de choisir la suite : \(0123456789\).
- Il n'existe donc qu'une seule possibilité.
