Dénombrement
Cours · mathématiques (PCSI), chapitre 14 · CPGE PCSI (1re année) · le début du chapitre, la suite sur Adloun
14.1 Introduction et motivation
Compter sans énumérer : tel est l'art du dénombrement. Cette section est introduite essentiellement en vue de son utilisation en probabilités (le chapitre suivant : probabilités sur un univers fini, où tout calcul de probabilité uniforme est un quotient de deux dénombrements) ; rattachée aux mathématiques discrètes, elle interagit aussi avec l'algèbre (coefficients binomiaux du chapitre 2, formule du binôme) et l'informatique (complexité des algorithmes, structures de données).
L'esprit du programme : toute formalisation excessive est exclue. Les propriétés les plus intuitives du cardinal sont admises sans démonstration, et l'utilisation systématique de bijections n'est pas un attendu — on raisonne par principes de comptage (addition, multiplication) et par modèles (listes, tirages, comités).
14.2 Cardinal d'un ensemble fini
Un ensemble est fini s'il a un nombre fini d'éléments ; ce nombre est son cardinal, noté ou (et ). Tout fondement théorique des notions d'entier naturel et de cardinal est hors programme : on s'appuie sur l'intuition du « nombre d'éléments ».
Si avec fini, alors est fini et , avec égalité si et seulement si .
Soient finis de même cardinal et . Alors :
Version contraposée, dite des tiroirs (ou de Dirichlet) : si l'on range chaussettes dans tiroirs, un tiroir contient au moins deux chaussettes — toute application d'un ensemble de cardinal vers un ensemble de cardinal est non injective. Simple et redoutable (exercice 5). On notera l'analogie parfaite avec la dimension finie (chapitre 10) : même énoncé, les cardinaux remplaçant les dimensions.