Ce cours traite de la combinaison et du dénombrement d'ensembles finis, y compris les principes multiplicatif et additif, les k-uplets, les produits cartésiens, les permutations, les combinaisons, et les relations de dénombrement, avec des applications dans divers domaines scientifiques.
Dans cette section, nous étudions les concepts de combinaatoire et de dénombrement, en nous concentrant sur les ensembles finis. Nous introduisons également les notions de couple, triplet, k-uplet (ou k-liste), le produit cartésien de deux, trois ou k ensembles, ainsi que l'ensemble A^k des k-uplets d'éléments d'un ensemble A.
Le principe additif stipule que le nombre d'éléments dans l'union de deux ensembles disjoints est égal à la somme des nombres d'éléments dans ces ensembles. En d'autres termes, si A et B sont deux ensembles disjoints, alors |A ∪ B| = |A| + |B|, où |A| représente le nombre d'éléments dans l'ensemble A.
Le principe multiplicatif énonce que le nombre d'éléments dans un produit cartésien d'ensembles est égal au produit des nombres d'éléments dans ces ensembles. En d'autres termes, si A et B sont deux ensembles, alors |A × B| = |A| × |B|, où |A| représente le nombre d'éléments dans l'ensemble A.
Le nombre de k-uplets (ou k-listes) d'un ensemble à n éléments peut être calculé en utilisant le principe multiplicatif. En effet, pour former un k-uplet, nous avons n choix pour le premier élément, n - 1 choix pour le deuxième élément, et ainsi de suite, jusqu'à n - k + 1 choix pour le k-ème élément. Ainsi, le nombre total de k-uplets d'un ensemble à n éléments est donné par la formule suivante :
où nPk représente le nombre de k-uplets d'un ensemble à n éléments. (Il est noté sous la forme "nPk" et se lit comme "n permutation k".)
Le nombre de parties d'un ensemble à n éléments peut être calculé en utilisant les n-uplets de {0,1}. En effet, chaque partie d'un ensemble à n éléments peut être représentée par un n-uplet de {0,1}, où la i-ème position du n-uplet est égale à 1 si l'élément i appartient à la partie, et 0 sinon. Ainsi, le nombre total de parties d'un ensemble à n éléments est égal à 2^n.
Le nombre de k-uplets d'éléments distincts d'un ensemble à n éléments peut être calculé en utilisant la factorielle n!. En effet, pour former un k-uplet d'éléments distincts, nous avons n choix pour le premier élément, n - 1 choix pour le deuxième élément, et ainsi de suite, jusqu'à n - k + 1 choix pour le k-ème élément. Ainsi, le nombre total de k-uplets d'éléments distincts d'un ensemble à n éléments est donné par la formule suivante :
où nCk représente le nombre de k-uplets d'un ensemble à n éléments. (Il est noté sous la forme "nCk" et se lit comme "n choisit k".)