Combinatoire et dénombrement
Combinatoire et dénombrement
Un ensemble fini est un ensemble qui contient un nombre limité d'éléments. Le cardinal d'un ensemble \(A\), noté \(\text{Card}(A)\), est le nombre d'éléments dans cet ensemble.
Concepts fondamentaux
Cardinal
Pour un ensemble \(A = \{a_1, a_2, \ldots, a_n\}\), on a \(\text{Card}(A) = n\).
Principe additif
Si \(A\) et \(B\) sont deux ensembles disjoints, alors :
\(\text{Card}(A \cup B) = \text{Card}(A) + \text{Card}(B)\)
Factorielle
La factorielle d'un entier naturel \(n\), notée \(n!\), est définie par :
\(n! = n \times (n-1) \times (n-2) \times \ldots \times 1 \quad \text{avec } 0! = 1\)
Produit cartésien
Le produit cartésien de deux ensembles \(A\) et \(B\), noté \(A \times B\), est l'ensemble de toutes les paires \((a, b)\) où \(a \in A\) et \(b \in B\). Le cardinal du produit cartésien est donné par :
\(\text{Card}(A \times B) = \text{Card}(A) \times \text{Card}(B)\)
Principe multiplicatif
Si un choix peut être fait de \(m\) manières et un autre choix de \(n\) manières, alors le nombre total de manières de faire ces deux choix est donné par :
\(\text{Card}(A \times B) = \text{Card}(A) \times \text{Card}(B)\)
Exercice
Dans une classe, il y a \(4\) livres de mathématiques et \(3\) livres de physique. Si un élève choisit un livre de mathématiques et un livre de physique, combien de choix différents peut-il faire ?
Résolution
1. Identification des ensembles :
- Soit \(A\) l'ensemble des livres de mathématiques : \(A = \{M_1, M_2, M_3, M_4\}\), donc \(\text{Card}(A) = 4\).
- Soit \(B\) l'ensemble des livres de physique : \(B = \{P_1, P_2, P_3\}\), donc \(\text{Card}(B) = 3\).
2. Application du principe multiplicatif :
Le nombre total de manières de choisir un livre de chaque discipline est donné par le principe multiplicatif :
\(\text{Card}(A \times B) = \text{Card}(A) \times \text{Card}(B)\)
3. Calcul :
En substituant les valeurs :
\(\text{Card}(A \times B) = 4 \times 3 = 12\)
Conclusion : L'élève peut faire \(12\) choix différents en sélectionnant un livre de mathématiques et un livre de physique.
k-uplet d'un ensemble fini
Soit \( A \) un ensemble fini contenant \( n \) éléments. Un k-uplet d'un ensemble \( A \) est une suite ordonnée de \( k \) éléments choisis dans \( A \), où les éléments peuvent être répétés. On note un k-uplet comme \( (a_1, a_2, \ldots, a_k) \), où chaque \( a_i \) appartient à \( A \) pour \( i = 1, 2, \ldots, k \).
Le nombre total de k-uplets distincts formés à partir de \( A \) est donné par la formule suivante :
\[ N = n^k \]
où \( n \) représente le cardinal de l'ensemble \( A \) et \( k \) le nombre d'éléments dans le k-uplet.
Une permutation d'un ensemble \( A \) est un k-uplet qui contient tous les éléments de \( A \) disposés dans un certain ordre. Pour un ensemble contenant \( n \) éléments, le nombre total de permutations est donné par la relation :
\[ P(n) = n! \]
où \( n! \) (factorielle de \( n \)) est le produit de tous les entiers positifs jusqu'à \( n \).
Nom | Définition |
---|---|
k-uplet | Suite ordonnée de \( k \) éléments de \( A \) pouvant être répétés. |
Quantité de k-uplets | \( N = n^k \) où \( n \) est le cardinal de \( A \). |
Permutation | Arrangement des \( n \) éléments de \( A \) dans un certain ordre. Nombre total : \( P(n) = n! \). |
Exercice
Considérez un ensemble \( A \) contenant 4 éléments distincts : \( \{a, b, c, d\} \).
- Combien de k-uplets de longueur 3 peut-on former à partir de cet ensemble ?
- Combien de permutations peut-on réaliser avec cet ensemble ?
Résolution
Pour répondre à la première question, on utilise la formule du nombre de k-uplets de longueur 3 :
\[ N = n^k \]
où \( n = 4 \) et \( k = 3 \). Ainsi :
\[ N = 4^3 = 64 \]
Il est donc possible de former 64 k-uplets distincts de longueur 3 à partir de l'ensemble \( A \).
Pour la deuxième question, le nombre de permutations de l'ensemble \( A \) est donné par :
\[ P(n) = n! \]
où \( n = 4 \) :
\[ P(4) = 4! = 4 \times 3 \times 2 \times 1 = 24 \]
Ainsi, il y a 24 permutations possibles de l'ensemble \( A \).
Quantités de parties d'un ensemble et combinaisons
Dans le cadre de la combinatoire, une question fréquente est de savoir combien de sous-ensembles (ou parties) un ensemble fini peut avoir.
Pour un ensemble \( A \) contenant \( n \) éléments, le nombre de sous-ensembles possibles est donné par la formule :
\[ \text{Nombre de parties} = 2^{\text{Card}(A)} \]
Cela signifie qu'un ensemble de \( n \) éléments a \( 2^n \) sous-ensembles, incluant l'ensemble vide et l'ensemble lui-même.
Les combinaisons permettent de sélectionner des éléments d'un ensemble sans tenir compte de l'ordre. La quantité de combinaisons de \( k \) éléments parmi \( n \) éléments est notée \( \binom{n}{k} \) et se calcule comme suit :
\[ \binom{n}{k} = \frac{n!}{k! \times (n - k)!} \]
où \( n! \) (factorielle de \( n \)) est le produit des entiers de \( 1 \) à \( n \).
Définition des combinaisons
La quantité de combinaisons de \( k \) éléments parmi \( n \) éléments est notée \( \binom{n}{k} \).
Exemple :
Si on souhaite savoir combien de façons il y a de choisir 3 éléments parmi un ensemble de 5 éléments \( \{a, b, c, d, e\} \), on peut utiliser la formule des combinaisons :
\[ \binom{5}{3} = \frac{5!}{3! \times 2!} = \frac{5 \times 4}{2 \times 1} = 10 \]
Ainsi, il y a 10 façons de sélectionner 3 éléments parmi 5.
Exercice
Dans un groupe de 6 étudiants, combien de manières différentes peut-on former un comité de 4 étudiants ?
Résolution
Pour résoudre cet exercice, nous allons utiliser la formule des combinaisons. Ici, \( n = 6 \) (le nombre total d'étudiants) et \( k = 4 \) (le nombre d'étudiants à choisir).
En utilisant la formule des combinaisons :
\[ \binom{6}{4} = \frac{6!}{4! \times (6 - 4)!} = \frac{6!}{4! \times 2!} \]
Calculons maintenant les factorielles :
\[ 6! = 720, \quad 4! = 24, \quad 2! = 2 \]
En substituant ces valeurs dans la formule :
\[ \binom{6}{4} = \frac{720}{24 \times 2} = \frac{720}{48} = 15 \]
Donc, il y a 15 manières différentes de former un comité de 4 étudiants parmi 6.
Propriétés algébriques des combinaisons et triangle de Pascal
Les combinaisons, notées \(\binom{n}{k}\), représentent le nombre de façons de choisir \(k\) éléments parmi un ensemble de \(n\) éléments sans tenir compte de l'ordre. Elles répondent à plusieurs propriétés algébriques importantes qui seront présentées ci-dessous.
Propriétés des combinaisons
- \(\binom{n}{0} = 1\) pour tout \(n \geq 0\).
- \(\binom{n}{n} = 1\) pour tout \(n \geq 0\).
- \(\binom{n}{k} = \binom{n}{n-k}\) pour tout \(0 \leq k \leq n\).
- \(\binom{n}{k} = 0\) si \(k > n\).
- \(\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}\) pour tout \(1 \leq k \leq n\).
Le triangle de Pascal est un arrangement triangulaire des coefficients binomiaux, où chaque nombre est la somme des deux nombres directement au-dessus de lui. Le triangle commence par le sommet avec \(1\) :
n \ k | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 1 | |||||
1 | 1 | 1 | ||||
2 | 1 | 2 | 1 | |||
3 | 1 | 3 | 3 | 1 | ||
4 | 1 | 4 | 6 | 4 | 1 | |
5 | 1 | 5 | 10 | 10 | 5 | 1 |
Exercice
Soit \(n = 5\). Calculez les valeurs de \(\binom{5}{0}\), \(\binom{5}{1}\), \(\binom{5}{2}\), \(\binom{5}{3}\), \(\binom{5}{4}\) et \(\binom{5}{5}\).Résolution
Nous allons utiliser la définition des combinaisons :- \(\binom{5}{0} = 1\) (par définition)
- \(\binom{5}{1} = 5\) (choix d'un élément parmi cinq)
- \(\binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10\)
- \(\binom{5}{3} = \frac{5 \times 4}{2 \times 1} = 10\) (symétrie avec \(\binom{5}{2}\))
- \(\binom{5}{4} = 5\) (choix de quatre éléments parmi cinq)
- \(\binom{5}{5} = 1\) (choix de tous les éléments)
Capacités attendues
- Comprendre et appliquer les principes additifs et multiplicatifs pour résoudre des problèmes de dénombrement.
- Calculer le cardinal d'un ensemble fini et en déduire des informations pertinentes.
- Établir et manipuler des k-uplets d'un ensemble fini.
- Compter le nombre de combinaisons d'éléments et utiliser la notation adéquate.
- Analyser et utiliser le triangle de Pascal pour résoudre des problèmes de combinaisons.
- Appliquer des propriétés algébriques liées aux combinaisons dans divers contextes.
- Développer des compétences en raisonnement logique et en résolution de problèmes mathématiques complexes.
Librairies :
- Bootstrap: https://getbootstrap.com
- Font Awesome: https://fontawesome.com
- jQuery: https://jquery.com
- MathJax: https://www.mathjax.org