Matez les Maths

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.

1

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\} \).

  1. Combien de k-uplets de longueur 3 peut-on former à partir de cet ensemble ?
  2. 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 \).

2

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.

3

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)
Les résultats sont donc : \[ \begin{align*} \binom{5}{0} &= 1, \\ \binom{5}{1} &= 5, \\ \binom{5}{2} &= 10, \\ \binom{5}{3} &= 10, \\ \binom{5}{4} &= 5, \\ \binom{5}{5} &= 1. \end{align*} \]
4

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.