Combinatoire et dénombrement

477

Aimé MARCANT

Membre éducatif vérifié
Mode lecture
Vidéo-projeter
Plus d'actions

Combinatoire et dénombrement

Résumé du cours

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.

I. Introduction

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.


II. Principe additif

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.


III. Principe multiplicatif

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.


IV. Nombre de k-uplets d'un ensemble à n éléments

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 :

n×(n1)×(n2)×...×(nk+1)=nPkn × (n - 1) × (n - 2) × ... × (n - k + 1) = nPk

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".)


V. Nombre de parties d'un ensemble à n éléments

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.


VI. Nombre de k-uplets d'éléments distincts d'un ensemble à n éléments

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 :

n!/(nk)!=nCkn! / (n - k)! = nCk

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".)


Commentaires (1)

Hugo DERIGNY il y a 5 mois

Il faudrait ajouter des exemples !