Combinatoire et Dénombrement

1. Produit cartésien

Le produit cartésien de deux ensembles A et B, noté A × B, est l’ensemble de tous les couples (a, b) avec a ∈ A et b ∈ B.

Si |A| = n et |B| = p, alors |A × B| = n × p.

2. k-upléts

Un k-uplet est une suite de k éléments d’un ensemble A, éventuellement avec répétitions, notée (a₁, a₂, ..., a_k).

Le nombre total de k-upléts formés à partir d’un ensemble de n éléments est n^k.

3. Permutations

Une permutation est une disposition de tous les éléments d’un ensemble en un ordre précis.

Le nombre de permutations de n éléments distincts est n! (factorielle de n): n! = n × (n-1) × ... × 1.

Pour permuter k éléments parmi n, le nombre est P(n, k) = n! / (n - k)!.

4. 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 est donné par le coefficient binomial:

C(n, k) = n! / (k! × (n - k)!).

Résumé des formules clés

• Produit cartésien: |A × B| = |A| × |B|.
• k-uplet: n^k.
• Permutations de n éléments: n!.
• Permutations de k éléments parmi n: P(n, k) = n! / (n - k)!.
• Combinaisons de k éléments parmi n: C(n, k) = n! / (k! (n - k)!).