Combinatoire et Dénombrement : Produit cartésien, k-uplets, combinaisons et permutations

1. Produit cartésien

Le produit cartésien de deux ensembles \(A\) et \(B\), noté \(A \times B\), est l’ensemble de tous les couples où le premier élément appartient à \(A\) et le second à \(B\).
Formellement :

\[ A \times B = \{ (a, b) \mid a \in A,\, b \in B \} \]

Par exemple, si \(A = \{1, 2\}\) et \(B = \{a, b, c\}\), alors

\[ A \times B = \{ (1, a), (1, b), (1, c), (2, a), (2, b), (2, c) \} \]

2. k-uplets

Un k-uplet est une famille de \(k\) éléments ordonnés issus d’un ensemble \(E\).
On note un k-uplet comme \( (x_1, x_2, ..., x_k) \) où chacun \(x_i \in E\).

Le nombre total de k-uplets issus d’un ensemble de \(n\) éléments (avec répétition autorisée) est :

\[ n^k \]

3. Combinaisons

Une combinaison est une sélection de \(k\) éléments d’un ensemble de \(n\) éléments, sans tenir compte de l’ordre. Le nombre de combinaisons possibles, noté \( C(n, k) \), est donné par :

\[ C(n, k) = \binom{n}{k} = \frac{n!}{k! (n - k)!} \]

Où \(n!\) désigne la factorielle de \(n\).

Exemple : Combien y a-t-il de façons de choisir 3 élèves parmi 10 ?
Réponse : \( C(10, 3) = \frac{10!}{3! \times 7!} = 120 \).

4. Permutations

Une permutation d’un ensemble de \(n\) éléments est une disposition ordonnée de tous ces éléments. Le nombre de permutations de \(n\) éléments est :

\[ P_n = n! \]

Si l’on veut permuter \(k\) éléments parmi \(n\), le nombre de permutatioins est :

\[ P(n, k) = \frac{n!}{(n - k)!} \]

Exemple : Combien de façons d’arranger 3 livres sur une étagère parmi un stock de 8 ?
Réponse : \( P(8, 3) = \frac{8!}{(8-3)!} = 8 \times 7 \times 6 = 336 \).

Résumé des formules importantes

• Produit cartésien : \(A \times B = \{ (a, b) \} \)
• K-uplets : \( n^k \) si l’ensemble a \(n\) éléments
• Combinaisons : \( \binom{n}{k} = \frac{n!}{k! (n - k)!} \)
• Permutations : \( n! \) ou \( P(n, k) = \frac{n!}{(n - k)!} \)