Combinatoire et Dénombrement

Introduction

La combinatoire s'intéresse au comptage du nombre de configurations possibles dans différents contextes. Ici, nous abordons le produit cartésien, les \(k\)-uplets, les combinaisons et les permutations.

Produit cartésien

Le produit cartésien de deux ensembles \(A\) et \(B\), noté \(A imes B\), est l'ensemble de toutes les paires \((a, b)\) où \(a \in A\) et \(b \in B\).

Exemple :

\(A = \{1, 2\}\), \(B = \{x, y\}\) :

\(A imes B = \{ (1, x), (1, y), (2, x), (2, y) \}\).

\(k\)-uplets

Un \(k\)-uplet est une succession de \(k\) éléments, chacun provenant d'un ensemble donné. Par exemple, un 3-uplet de \(A\) est une famille \((a_1, a_2, a_3)\).

Nombre total de \(k\)-uplets possibles si chaque élément appartient à un ensemble \(A\) de cardinal \(n\) :

\[ n^k \]

Combinatoires : permutations, combinaisons

Permutations

Une permutation est une disposition ordonnée de tout ou partie d'un ensemble. Si l'ensemble a \(n\) éléments et que l'on souhaite en disposer tous, le nombre de permutations est :

\[ P_n = n! \]

Pour arranger \(k\) éléments parmi \(n\), le nombre de permutations est :

\[ P_{n}^{k} = rac{n!}{(n-k)!} \]

Combinaisons

Une combinaison est une sélection d'éléments sans tenir compte de l'ordre. Le nombre de combinaisons de \(k\) éléments parmi \(n\) est :

\[ C_{n}^{k} = inom{n}{k} = rac{n!}{k! (n-k)!} \]

Résumé

• Produit cartésien : \(A imes B\)
• \(k\)-uplets : la famille \((a_1, \dots, a_k)\) avec \(|A| = n\), nombre de options : \(n^k\)
• Permutations : arrangements de tous ou partie, avec ou sans ordre
• Combinaisons : choix sans ordre, \(inom{n}{k}\)