OpenYourMath

Programme de mathématiques BCPST, première année · semestre 1

Outils 7 – Dénombrement

Rechercher dans cette partie du programme

55 exercices

Texte officiel du programme

Le but de ce chapitre est de mettre en place un vocabulaire efficace pour décrire (ou modéliser) et analyser les problèmes combinatoires, ainsi que quelques résultats fondamentaux associés. Les résultats de ce chapitre seront justifiés intuitivement, sans recours à des démonstrations formelles. De façon générale, on évitera tout excès de technicité dans les dénombrements.

Tous les ensembles considérés dans ce chapitre sont finis.

Dans les définitions qui suivent, on suppose que $\mathrm{card}(E) = n$.

Contenus	Capacités et commentaires
Cardinal, notation $\mathrm{card}(E)$ ou $\#E$.	On définit le cardinal grâce à la notion intuitive de nombre d’éléments. En particulier, deux ensembles en bijection ont même cardinal.
Cardinal d’une union disjointe. Formule $\mathrm{card}(A \cup B) = \mathrm{card}A + \mathrm{card}B - \mathrm{card}(A \cap B)$.
Cardinal d’un produit cartésien.	$\mathrm{card}(E \times F)$ est aussi le nombre de façons de choisir de façon indépendante un élément de $E$ et un élément de $F$.
Un élément de $E^p$ est appelé un $p$-uplet ou une $p$-liste de $E$. Il y a $n^p$ $p$-uplets de $E$.	$\mathrm{card}(E^p)$ est le nombre de façons de choisir successivement $p$ objets parmi $n$ objets distincts, avec d’éventuelles répétitions.
Un $p$-uplet est dit sans répétition lorsque ses éléments sont distincts deux à deux. il y a $n(n-1)\cdots(n-p+1)$ $p$-uplets sans répétition de $E$.	Le nombre de $p$-uplets sans répétition est le nombre de façons de choisir successivement $p$ objets parmi $n$ objets distincts, sans répétition.
Un $n$-uplet de $E$ contenant exactement une fois chaque élément de $E$ est appelé une permutation de $E$. Il y a $n!$ permutations de $E$.	$n!$ est le nombre de façons de choisir successivement tous les objets d’un ensemble, sans répétition.
Si $p \leq n$, une $p$-combinaison de $E$ est une partie de $E$ à $p$ éléments. Il y a $\dbinom{n}{p}$ $p$-combinaisons de $E$. Cardinal de l’ensemble des parties de $E$.	$\dbinom{n}{p}$ est le nombre de façons de choisir simultanément $p$ objets parmi $n$ objets distincts. On peut sur cette base réinterpréter la formule du binôme.