Dénombrement

Depuis le début de l'année, les questions posées commençaient toutes par « comment » : comment résoudre, comment décomposer, comment inverser. Celle qui ouvre ce chapitre est d'une autre nature, et elle est plus redoutable qu'elle n'en a l'air : combien ? Combien de mots de cinq lettres, combien de mains de poker contenant exactement une paire, combien d'applications d'un ensemble à dix éléments dans un ensemble à trois, combien de façons de répartir douze objets en quatre paquets. C'est la première fois de l'année que l'on compte pour de bon, c'est-à-dire que le résultat attendu n'est pas un objet mais un entier, et que ce nombre doit être obtenu sans énumérer. Personne ne peut lister les $2598960$ mains de cinq cartes ; il faut donc les compter sans les voir.

L'outil central de cette entreprise n'est pas une formule, et c'est la première chose à comprendre. Compter un ensemble, c'est le mettre en bijection avec un modèle dont on connaît déjà le cardinal. La définition même du mot « cardinal » dit exactement cela : un ensemble a $n$ éléments lorsqu'il est en bijection avec $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$, c'est-à-dire lorsqu'on peut numéroter ses éléments de $1$ à $n$ sans en oublier ni en compter deux fois. Toutes les formules du chapitre, sans exception, sont des bijections déguisées : une main de cinq cartes « est » une partie à cinq éléments d'un ensemble à cinquante-deux éléments, un mot de cinq lettres « est » une application de $[\text{\hspace{0.17em}⁣}[1,5]\text{\hspace{0.17em}⁣}]$ dans l'alphabet, une répartition de $n$ personnes autour d'une table ronde « est » une classe de dispositions numérotées. Le travail du dénombreur consiste à reconnaître le modèle, à écrire la bijection, et à laisser la formule faire le reste.

Le vocabulaire des applications, introduit au premier semestre pour lui-même, change ici de statut : il devient un instrument de mesure. Une injection de $E$ dans $F$ ne sera plus seulement une application qui sépare les points, ce sera la preuve que $E$ n'est pas plus gros que $F$ ; une surjection sera la preuve qu'il n'est pas plus petit ; une bijection, la preuve qu'ils ont exactement la même taille. L'image réciproque $f^{-1}(\{y\})$, cette notation qui semblait n'exister que pour compliquer les énoncés, devient la fibre au-dessus de $y$, c'est-à-dire le paquet des objets qui donnent le même résultat, et compter les paquets deviendra la manière la plus efficace de compter les objets. Rien de nouveau n'est demandé sur ces notions : seul l'usage change.

Une fois ce point de vue adopté, la matière du chapitre se réduit à très peu de choses. Quatre modèles seulement structurent tout ce qui suit, et un tableau à deux entrées les organise : l'ordre des éléments compte-t-il, et les répétitions sont-elles permises ? Si l'ordre compte et que les répétitions sont permises, on compte des listes, et il y en a $n^p$. Si l'ordre compte mais que les répétitions sont interdites, on compte des arrangements, et il y en a $A_n^p$. Si l'ordre ne compte pas et que les répétitions sont interdites, on compte des parties, et il y en a ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{p}\right)}$. La dernière case, celle où l'ordre ne compte pas mais où les répétitions sont permises, ne porte pas de formule au programme et se traite au cas par cas, par une bijection adaptée à la situation. Trois formules et une vigilance : voilà tout l'arsenal.

La difficulté réelle n'est donc jamais le calcul, qui se réduit le plus souvent à une factorielle ou à un coefficient binomial, mais le choix du modèle. Décider si deux objets obtenus dans un ordre différent doivent être comptés une fois ou deux, décider si un élément peut resservir, décider si l'énumération proposée atteint bien tous les objets : c'est là que tout se joue, et c'est là que l'on se trompe. L'erreur la plus fréquente aux concours n'est pas une erreur de calcul, c'est de compter deux fois le même objet ou d'en oublier une famille entière. Le remède est une discipline de rédaction qui ne coûte presque rien : nommer explicitement l'ensemble que l'on compte, exhiber la bijection ou la partition sur laquelle on s'appuie, et vérifier sur un petit cas que le compte est bon. Un dénombrement dont le modèle n'est pas justifié n'est pas un dénombrement, c'est un pari.

Ce travail n'est pas une fin en soi. Le chapitre suivant, consacré aux probabilités sur un univers fini, repose entièrement sur les techniques établies ici, au point que la seule difficulté véritable y sera de dénombrer correctement. Tout ce qui est acquis maintenant sera réinvesti immédiatement.

Le plan suit l'ordre naturel de construction. La première section pose la définition d'un ensemble fini et de son cardinal, et démontre les deux propriétés qui serviront partout : une partie d'un ensemble fini est plus petite que lui, avec égalité seulement si elle lui est égale, et l'image d'un ensemble fini est plus petite que lui, avec égalité seulement si l'application est injective. La deuxième section traduit en termes de cardinaux l'existence d'une injection, d'une surjection ou d'une bijection, en tire le principe des tiroirs et son raffinement quantitatif, puis le théorème qui rend équivalentes injectivité, surjectivité et bijectivité entre deux ensembles finis de même cardinal. La troisième section établit les règles de calcul : addition sur une réunion disjointe, passage au complémentaire, réunion de deux ensembles, multiplication sur un produit cartésien, puis deux principes d'usage constant, le lemme du berger et le double comptage. Les sections suivantes construisent les formules de dénombrement proprement dites, listes, arrangements, permutations, combinaisons et coefficients binomiaux, avant une section de méthodes.

Les notations suivantes valent pour tout le chapitre. Les ensembles d'entiers gardent leurs noms habituels, $\mathbb{N}$, ${\mathbb{N}}^{\ast }$, $\mathbb{Z}$, $\mathbb{R}$, et un intervalle d'entiers se note $[\text{\hspace{0.17em}⁣}[a,b]\text{\hspace{0.17em}⁣}]$, c'est-à-dire $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]=\{1,2,\dots ,n\}$ avec la convention $[\text{\hspace{0.17em}⁣}[1,0]\text{\hspace{0.17em}⁣}]=\mathrm{\varnothing }$. Le cardinal d'un ensemble fini $E$ est noté $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$, et cette notation est la seule employée ici. L'ensemble des parties de $E$ est $\mathcal{P}(E)$, celui des parties à $p$ éléments est ${\mathcal{P}}_p(E)$, l'ensemble des applications de $E$ dans $F$ est $\mathcal{F}(E,F)$, parfois noté $F^E$ dans la littérature, et l'ensemble des bijections de $E$ sur lui-même, ou permutations de $E$, est $\mathfrak{S}(E)$, noté ${\mathfrak{S}}_n$ lorsque $E=[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$. Les nombres qui apparaîtront sont la factorielle $n!$, le nombre d'arrangements $A_n^p$ et le coefficient binomial ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{p}\right)}$. L'inclusion, au sens large, est notée $\subset$ ; le complémentaire d'une partie $A$ dans un ensemble $E$ est noté $\bar{A}$, ou $E\setminus A$ lorsque l'ensemble ambiant doit être rappelé ; la réunion de deux ensembles disjoints est appelée réunion disjointe et notée $A\bigsqcup B$ dès que cette notation aura été introduite. Les inégalités larges s'écrivent $⩽$ et $⩾$, et la fin d'une démonstration est signalée par le symbole $\mathrm{\square }$.

Ensembles finis et cardinal

Définition et unicité du cardinal

Compter les éléments d'un ensemble, dans la vie courante, c'est les désigner l'un après l'autre en disant « un, deux, trois… » jusqu'à épuisement. Cette opération très concrète est exactement la construction d'une bijection entre l'ensemble considéré et un intervalle d'entiers $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ : chaque élément reçoit un numéro et un seul, chaque numéro est attribué à un élément et un seul. La définition qui suit ne fait que prendre cette description au mot.

L'ensemble vide est donc fini, puisque l'unique application de $\mathrm{\varnothing }$ dans $\mathrm{\varnothing }$ est une bijection. Avant de pouvoir parler du nombre d'éléments de $E$, il faut s'assurer que l'entier $n$ de la définition ne dépend pas de la manière de compter : si l'on numérote deux fois le même ensemble et que l'on trouve $n$ la première fois et $m$ la seconde, il faut que $n=m$. C'est l'objet du lemme suivant, dont l'évidence apparente ne dispense pas de la démonstration.

Démonstration. Par récurrence sur $n$. Pour $n\in \mathbb{N}$, notons $P(n)$ l'assertion : « pour tout $m\in \mathbb{N}$, s'il existe une bijection de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$, alors $m=n$ ».

Initialisation. Soit $m\in \mathbb{N}$ tel qu'il existe une bijection $f:[\text{\hspace{0.17em}⁣}[1,0]\text{\hspace{0.17em}⁣}]\to [\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$, c'est-à-dire $f:\mathrm{\varnothing }\to [\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$. Cette application est surjective, donc $[\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]=f(\mathrm{\varnothing })=\mathrm{\varnothing }$. Or si $m⩾1$, l'entier $1$ appartient à $[\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$, qui n'est alors pas vide. Donc $m=0$, et $P(0)$ est vraie.

Hérédité. Supposons $P(n)$ vraie pour un certain $n\in \mathbb{N}$. Soient $m\in \mathbb{N}$ et $f:[\text{\hspace{0.17em}⁣}[1,n+1]\text{\hspace{0.17em}⁣}]\to [\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$ une bijection. L'ensemble $[\text{\hspace{0.17em}⁣}[1,n+1]\text{\hspace{0.17em}⁣}]$ contient l'élément $1$, donc son image par $f$ est non vide, donc $m⩾1$. Posons $a=f(n+1)\in [\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$ et notons $\tau :[\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]\to [\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$ l'application qui échange $a$ et $m$ et laisse fixes tous les autres entiers ; c'est une bijection, égale à sa propre réciproque. L'application $g=\tau \circ f$ est donc une bijection de $[\text{\hspace{0.17em}⁣}[1,n+1]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$, et elle vérifie $g(n+1)=\tau (a)=m$.

Montrons que la restriction de $g$ à $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ est une bijection de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,m-1]\text{\hspace{0.17em}⁣}]$. Elle est injective comme restriction d'une application injective. Elle est bien à valeurs dans $[\text{\hspace{0.17em}⁣}[1,m-1]\text{\hspace{0.17em}⁣}]$ : si $k\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$, alors $k\mathrm{\ne }n+1$, donc $g(k)\mathrm{\ne }g(n+1)=m$ par injectivité, et comme $g(k)\in [\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$, on a $g(k)\in [\text{\hspace{0.17em}⁣}[1,m-1]\text{\hspace{0.17em}⁣}]$. Elle est surjective sur $[\text{\hspace{0.17em}⁣}[1,m-1]\text{\hspace{0.17em}⁣}]$ : si $y\in [\text{\hspace{0.17em}⁣}[1,m-1]\text{\hspace{0.17em}⁣}]$, la surjectivité de $g$ fournit $k\in [\text{\hspace{0.17em}⁣}[1,n+1]\text{\hspace{0.17em}⁣}]$ tel que $g(k)=y$ ; comme $y\mathrm{\ne }m=g(n+1)$, on a $k\mathrm{\ne }n+1$, donc $k\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$.

Il existe donc une bijection de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,m-1]\text{\hspace{0.17em}⁣}]$, et l'hypothèse de récurrence donne $m-1=n$, c'est-à-dire $m=n+1$. Ainsi $P(n+1)$ est vraie, ce qui achève la récurrence. $\mathrm{\square }$

L'unicité annoncée par cette définition est bien celle que garantit le lemme précédent : si $f:[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]\to E$ et $g:[\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]\to E$ sont deux bijections, alors $g^{-1}\circ f$ est une bijection de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$, donc $n=m$. Le même argument, à peine modifié, donne le principe qui gouverne tout le chapitre.

Démonstration. Notons $n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$ et soit $f:[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]\to E$ une bijection. Si $\phi :E\to G$ est une bijection, alors $\phi \circ f$ est une bijection de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $G$, comme composée de deux bijections. Donc $G$ est fini, et son cardinal, unique d'après le lemme d'unicité, vaut $n$. $\mathrm{\square }$

Cardinal d'une partie, cas d'égalité

Toutes les démonstrations qui suivent reposent sur une manipulation élémentaire, retirer ou ajouter un élément, qu'il est plus économique d'isoler une fois pour toutes.

Démonstration. Point 1. Notons $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=n+1$ avec $n\in \mathbb{N}$, ce qui est licite puisque $E$ est non vide donc de cardinal non nul, et soit $f:[\text{\hspace{0.17em}⁣}[1,n+1]\text{\hspace{0.17em}⁣}]\to E$ une bijection. Posons $j=f^{-1}(a)$ et notons $\tau$ l'application de $[\text{\hspace{0.17em}⁣}[1,n+1]\text{\hspace{0.17em}⁣}]$ dans lui-même qui échange $j$ et $n+1$ et fixe les autres entiers ; c'est une bijection. Alors $g=f\circ \tau$ est une bijection de $[\text{\hspace{0.17em}⁣}[1,n+1]\text{\hspace{0.17em}⁣}]$ sur $E$ telle que $g(n+1)=f(j)=a$.

La restriction de $g$ à $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ est injective, à valeurs dans $E\setminus \{a\}$ car $g(k)=a=g(n+1)$ imposerait $k=n+1$, et surjective sur $E\setminus \{a\}$ car tout $y\in E\setminus \{a\}$ s'écrit $y=g(k)$ avec $k\mathrm{\ne }n+1$. C'est donc une bijection de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $E\setminus \{a\}$, d'où $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E\setminus \{a\})=n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)-1$.

Point 2. Notons $n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$ et soit $f:[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]\to E$ une bijection. Définissons $h:[\text{\hspace{0.17em}⁣}[1,n+1]\text{\hspace{0.17em}⁣}]\to E\cup \{c\}$ par $h(k)=f(k)$ pour $k\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ et $h(n+1)=c$. Elle est surjective par construction. Elle est injective : deux entiers distincts de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ ont des images distinctes par injectivité de $f$, et $h(k)=f(k)\in E$ diffère de $h(n+1)=c\mathrm{\notin }E$. Donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E\cup \{c\})=n+1$. $\mathrm{\square }$

Démonstration. Par récurrence sur $n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$. Notons $P(n)$ l'assertion : « pour tout ensemble $E$ de cardinal $n$ et toute partie $A$ de $E$, l'ensemble $A$ est fini, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)⩽n$, et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=n$ si et seulement si $A=E$ ».

Initialisation. Si $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=0$, il existe une bijection de $\mathrm{\varnothing }$ sur $E$, qui est en particulier surjective, donc $E=\mathrm{\varnothing }$. La seule partie de $E$ est alors $A=\mathrm{\varnothing }$, qui est finie de cardinal $0⩽0$, et l'égalité $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=0$ a bien lieu en même temps que $A=E$. Donc $P(0)$ est vraie.

Hérédité. Supposons $P(n)$ vraie et soient $E$ de cardinal $n+1$ et $A\subset E$. Comme $E$ est non vide, on peut choisir $a\in E$ ; posons $E^{\mathrm{\prime }}=E\setminus \{a\}$, qui est de cardinal $n$ d'après le lemme du retrait. Deux cas se présentent.

Premier cas : $a\mathrm{\notin }A$. Alors $A\subset E^{\mathrm{\prime }}$, et l'hypothèse de récurrence appliquée à $E^{\mathrm{\prime }}$ montre que $A$ est finie avec $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)⩽n<n+1$. L'inégalité voulue est donc stricte, et l'égalité $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=n+1$ est impossible ; c'est cohérent puisque $A\mathrm{\ne }E$, l'élément $a$ appartenant à $E$ et pas à $A$. L'équivalence est donc vraie, ses deux membres étant faux.

Second cas : $a\in A$. Posons $A^{\mathrm{\prime }}=A\setminus \{a\}$. Comme $A\subset E$ et $a\in A$, on a $A^{\mathrm{\prime }}\subset E^{\mathrm{\prime }}$. L'hypothèse de récurrence donne : $A^{\mathrm{\prime }}$ est finie, $p=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A^{\mathrm{\prime }})⩽n$, et $p=n$ si et seulement si $A^{\mathrm{\prime }}=E^{\mathrm{\prime }}$. Le point 2 du lemme d'ajout, appliqué à $A^{\mathrm{\prime }}$ et à $c=a\mathrm{\notin }{A}^{\mathrm{\prime }}$, montre que $A=A^{\mathrm{\prime }}\cup \{a\}$ est finie de cardinal $p+1⩽n+1$. Enfin

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=n+1⟺p=n⟺A^{\mathrm{\prime }}=E^{\mathrm{\prime }}⟺A=E,$$

la dernière équivalence venant de ce que $A=A^{\mathrm{\prime }}\cup \{a\}$ et $E=E^{\mathrm{\prime }}\cup \{a\}$. Ainsi $P(n+1)$ est vraie. $\mathrm{\square }$

Démonstration. Par récurrence sur $n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)⩾1$.

Initialisation. Si $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=1$, alors $A=\{a\}$ pour un certain réel $a$, qui est à la fois son plus petit et son plus grand élément.

Hérédité. Supposons le résultat acquis pour toute partie de cardinal $n⩾1$ et soit $A$ de cardinal $n+1$. Choisissons $a\in A$ et posons $A^{\mathrm{\prime }}=A\setminus \{a\}$, de cardinal $n⩾1$ d'après le lemme du retrait, donc non vide. Par hypothèse de récurrence, $A^{\mathrm{\prime }}$ admet un plus petit élément $m^{\mathrm{\prime }}$ et un plus grand élément $M^{\mathrm{\prime }}$. Posons $M=\max (a,M^{\mathrm{\prime }})$, ce qui a un sens puisqu'il s'agit du plus grand de deux réels. Alors $M\in A$, car $M$ vaut $a\in A$ ou $M^{\mathrm{\prime }}\in A^{\mathrm{\prime }}\subset A$ ; et $M$ majore $A$, car tout élément de $A$ est soit $a$, qui est $⩽M$, soit un élément de $A^{\mathrm{\prime }}$, donc $⩽M^{\mathrm{\prime }}⩽M$. Donc $M$ est le plus grand élément de $A$. Le raisonnement pour $m=\min (a,m^{\mathrm{\prime }})$ est identique. $\mathrm{\square }$

Image d'un ensemble fini

Démonstration. Par récurrence sur $n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$, l'assertion $P(n)$ étant : « pour tout ensemble $E$ de cardinal $n$, tout ensemble $F$ et toute application $f:E\to F$, l'ensemble $f(E)$ est fini, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f(E))⩽n$, avec égalité si et seulement si $f$ est injective ».

Initialisation. Si $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=0$, alors $E=\mathrm{\varnothing }$, donc $f(E)=\mathrm{\varnothing }$ est fini de cardinal $0$, l'inégalité est une égalité, et $f$ est injective (la condition d'injectivité porte sur des couples d'éléments de $E$, et il n'y en a aucun). Les deux membres de l'équivalence sont vrais, donc $P(0)$ est vraie.

Hérédité. Supposons $P(n)$ vraie et soient $E$ de cardinal $n+1$ et $f:E\to F$. Choisissons $a\in E$ et posons $E^{\mathrm{\prime }}=E\setminus \{a\}$, de cardinal $n$. On a la décomposition

$$f(E)=f(E^{\mathrm{\prime }})\cup \{f(a)\},$$

et l'hypothèse de récurrence, appliquée à la restriction $f_{\mathrm{\mid }{E}^{\mathrm{\prime }}}$, dit que $f(E^{\mathrm{\prime }})$ est fini, de cardinal $q⩽n$, avec $q=n$ si et seulement si $f_{\mathrm{\mid }{E}^{\mathrm{\prime }}}$ est injective. Deux cas se présentent.

Premier cas : $f(a)\in f(E^{\mathrm{\prime }})$. Alors $f(E)=f(E^{\mathrm{\prime }})$ est fini de cardinal $q⩽n<n+1$, donc l'égalité $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f(E))=n+1$ est fausse. Par ailleurs $f(a)\in f(E^{\mathrm{\prime }})$ signifie qu'il existe $x\in E^{\mathrm{\prime }}$ tel que $f(x)=f(a)$ ; comme $x\mathrm{\ne }a$, l'application $f$ n'est pas injective. Les deux membres de l'équivalence sont faux, elle est donc vraie.

Second cas : $f(a)\mathrm{\notin }f(E^{\mathrm{\prime }})$. Le lemme d'ajout donne alors que $f(E)=f(E^{\mathrm{\prime }})\cup \{f(a)\}$ est fini de cardinal $q+1⩽n+1$. De plus, dans ce cas, $f$ est injective si et seulement si $f_{\mathrm{\mid }{E}^{\mathrm{\prime }}}$ l'est : le sens direct est immédiat, et réciproquement, si $f_{\mathrm{\mid }{E}^{\mathrm{\prime }}}$ est injective, deux éléments distincts $x,y$ de $E$ ont des images distinctes, que ce soit parce qu'ils sont tous deux dans $E^{\mathrm{\prime }}$, ou parce que l'un vaut $a$ et l'autre est dans $E^{\mathrm{\prime }}$, auquel cas $f(a)\mathrm{\notin }f(E^{\mathrm{\prime }})$ conclut. Ainsi

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f(E))=n+1⟺q=n⟺f_{\mathrm{\mid }{E}^{\mathrm{\prime }}}\text{ est injective}⟺f\text{ est injective},$$

ce qui établit $P(n+1)$. $\mathrm{\square }$

Applications entre ensembles finis

Injections, surjections et cardinaux

Démonstration. Point 1. Supposons $f$ injective. D'après la propriété sur l'image d'un ensemble fini, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f(E))=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$. Or $f(E)$ est une partie de $F$, donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f(E))⩽\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$. En combinant, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)⩽\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$.

Point 2. Supposons $f$ surjective, c'est-à-dire $f(E)=F$. La même propriété donne $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f(E))⩽\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$.

Point 3. Une bijection est à la fois injective et surjective : les deux inégalités précédentes donnent l'égalité. On peut aussi invoquer directement le principe de la bijection. $\mathrm{\square }$

Le principe des tiroirs

La contraposée du point 1 de la propriété précédente porte un nom, tient en une phrase, et résout des problèmes qui semblent hors de portée.

Démonstration. Si une application $f:E\to F$ était injective, le point 1 de la propriété précédente donnerait $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)⩽\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$, ce qui contredit l'hypothèse $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)>\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$. Donc aucune application de $E$ dans $F$ n'est injective, ce qui signifie exactement qu'il existe deux éléments distincts de $E$ ayant la même image. $\mathrm{\square }$

Le principe se raffine sans effort : s'il y a beaucoup plus de chaussettes que de tiroirs, un tiroir contient beaucoup de chaussettes. Rappelons que pour $y\in F$, l'image réciproque $f^{-1}(\{y\})=\{x\in E:f(x)=y\}$ s'appelle la fibre de $f$ au-dessus de $y$ : c'est le contenu du tiroir $y$.

Démonstration. Cette démonstration utilise le principe d'addition, établi à la section suivante et dont l'établissement ne dépend d'aucun résultat du présent paragraphe. Raisonnons par l'absurde en supposant que toutes les fibres vérifient $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f^{-1}(\{y\}))⩽k$. Écrivons $F=\{y_1,\dots ,y_m\}$ avec $m=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$ et les $y_j$ deux à deux distincts. Les fibres $f^{-1}(\{y_1\}),\dots ,f^{-1}(\{y_m\})$ sont deux à deux disjointes, car un élément $x$ de $E$ possède une image et une seule, donc appartient à une fibre et une seule ; et leur réunion est $E$ tout entier, car tout $x\in E$ appartient à la fibre au-dessus de $f(x)$. Le principe d'addition donne alors

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=\sum _{j=1}^m\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f^{-1}(\{y_j\}))⩽\sum _{j=1}^{m}k=km=k\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F),$$

ce qui contredit l'hypothèse. Il existe donc une fibre d'au moins $k+1$ éléments. $\mathrm{\square }$

Le théorème fondamental des cardinaux égaux

Démonstration. Notons $n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$.

Le point 1 entraîne le point 2. Supposons $f$ injective. D'après la propriété sur l'image d'un ensemble fini, le cas d'égalité donne $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f(E))=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=n$. Or $f(E)$ est une partie de $F$, qui est de cardinal $n$ : d'après le cas d'égalité de la propriété sur le cardinal d'une partie, l'égalité $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f(E))=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$ impose $f(E)=F$. C'est exactement la surjectivité de $f$.

Le point 2 entraîne le point 1. Supposons $f$ surjective, c'est-à-dire $f(E)=F$. Alors $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f(E))=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)=n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$. Le cas d'égalité de la propriété sur l'image d'un ensemble fini affirme précisément qu'alors $f$ est injective.

Équivalence avec le point 3. Les deux implications précédentes montrent que $f$ est injective si et seulement si elle est surjective ; chacune des deux entraîne donc les deux, c'est-à-dire la bijectivité. Réciproquement, une bijection est injective et surjective. Les trois assertions sont donc équivalentes. $\mathrm{\square }$

Opérations sur les cardinaux

Réunion disjointe et complémentaire

Démonstration. Cas de deux ensembles. Posons $p=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)$ et $q=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)$, et soient $g:[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]\to A$ et $h:[\text{\hspace{0.17em}⁣}[1,q]\text{\hspace{0.17em}⁣}]\to B$ deux bijections. Définissons

$$\phi :[\text{\hspace{0.17em}⁣}[1,p+q]\text{\hspace{0.17em}⁣}]⟶A\cup B,\phi (k)=\{\begin{array}{ll}g(k)& \text{si }1⩽k⩽p,\\ h(k-p)& \text{si }p+1⩽k⩽p+q\mathrm{.}\end{array}$$

Cette application est bien définie : si $p+1⩽k⩽p+q$, alors $1⩽k-p⩽q$, donc $h(k-p)$ a un sens.

Elle est surjective : tout élément de $A\cup B$ est dans $A$, donc de la forme $g(k)$ avec $k\in [\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$, ou dans $B$, donc de la forme $h(j)=\phi (j+p)$ avec $j\in [\text{\hspace{0.17em}⁣}[1,q]\text{\hspace{0.17em}⁣}]$.

Elle est injective. Soient $k\mathrm{\ne }{k}^{\mathrm{\prime }}$ dans $[\text{\hspace{0.17em}⁣}[1,p+q]\text{\hspace{0.17em}⁣}]$. Si tous deux sont $⩽p$, alors $\phi (k)=g(k)\mathrm{\ne }g(k^{\mathrm{\prime }})=\phi (k^{\mathrm{\prime }})$ par injectivité de $g$. Si tous deux sont $>p$, alors $k-p\mathrm{\ne }{k}^{\mathrm{\prime }}-p$ et l'injectivité de $h$ conclut. Si enfin $k⩽p<k^{\mathrm{\prime }}$, alors $\phi (k)\in A$ et $\phi (k^{\mathrm{\prime }})\in B$ ; comme $A\cap B=\mathrm{\varnothing }$, ces deux éléments sont distincts. C'est ici, et seulement ici, que l'hypothèse de disjonction est utilisée.

Donc $\phi$ est une bijection et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\bigsqcup B)=p+q$.

Cas général. Par récurrence sur $m$. Pour $m=1$, l'énoncé est trivial. Supposons-le vrai au rang $m$ et donnons-nous $A_1,\dots ,A_{m+1}$ finis et deux à deux disjoints. Posons $U={\bigcup }_{i=1}^m{A}_i$, qui est fini de cardinal ${\sum }_{i=1}^m\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A_i)$ par hypothèse de récurrence. Les ensembles $U$ et $A_{m+1}$ sont disjoints : si $x\in U\cap A_{m+1}$, alors $x$ appartient à un certain $A_i$ avec $i⩽m$, et à $A_{m+1}$, ce qui contredit $A_i\cap A_{m+1}=\mathrm{\varnothing }$. Le cas de deux ensembles donne alors

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left(\bigcup _{i=1}^{m+1}{A}_i\right)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(U)+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A_{m+1})=\sum _{i=1}^m\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A_i)+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A_{m+1})=\sum _{i=1}^{m+1}\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A_i),$$

ce qui achève la récurrence. $\mathrm{\square }$

Démonstration. Point 1. Les ensembles $A$ et $E\setminus A$ sont disjoints par construction, et leur réunion vaut $E$. Ils sont finis comme parties de $E$. Le principe d'addition donne $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E\setminus A)$, d'où le résultat en retranchant $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)$, ce qui est licite puisque tous ces cardinaux sont des entiers.

Point 2. Les ensembles $A\cap B$ et $B\setminus A$ sont disjoints : un élément du second n'appartient pas à $A$, donc pas à $A\cap B$. Leur réunion vaut $B$ : tout élément de $B$ appartient à $A$, donc à $A\cap B$, ou n'y appartient pas, donc est dans $B\setminus A$. Le principe d'addition donne $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B)+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B\setminus A)$. $\mathrm{\square }$

Réunion de deux ensembles quelconques

Démonstration. Décomposons $A\cup B$ en deux morceaux disjoints :

$$A\cup B=A\bigsqcup (B\setminus A)\mathrm{.}$$

Cette égalité se vérifie sur les éléments. Un élément de $A$ est dans $A\cup B$, et un élément de $B\setminus A$ est dans $B$ donc dans $A\cup B$ : l'inclusion de droite à gauche est acquise. Réciproquement, si $x\in A\cup B$, alors soit $x\in A$, soit $x\mathrm{\notin }A$, et dans ce second cas $x\in B$, donc $x\in B\setminus A$. Enfin les deux morceaux sont bien disjoints, puisque les éléments de $B\setminus A$ ne sont pas dans $A$.

Le principe d'addition donne alors $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cup B)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B\setminus A)$, et le point 2 de la propriété précédente donne $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B\setminus A)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B)$. En reportant,

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cup B)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B)\mathrm{.}\mathrm{\square }$$

Produit cartésien

Démonstration. Notons $n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$ et écrivons $E=\{x_1,\dots ,x_n\}$, les $x_i$ étant deux à deux distincts, ce qui est possible en posant $x_i=f(i)$ pour une bijection $f:[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]\to E$. Pour chaque $i$, posons

$$P_i=\{x_i\}\times F=\{(x_i,y):y\in F\}\mathrm{.}$$

Ces ensembles sont deux à deux disjoints, car un couple appartenant à $P_i$ et à $P_j$ aurait pour première coordonnée à la fois $x_i$ et $x_j$, d'où $i=j$. Leur réunion est $E\times F$, car tout couple $(x,y)$ de $E\times F$ a sa première coordonnée égale à un $x_i$, et appartient donc à $P_i$.

Par ailleurs, pour chaque $i$, l'application $y\mapsto (x_i,y)$ est une bijection de $F$ sur $P_i$ : elle est surjective par définition de $P_i$, et injective car $(x_i,y)=(x_i,y^{\mathrm{\prime }})$ entraîne $y=y^{\mathrm{\prime }}$. Le principe de la bijection donne $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(P_i)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$.

Le principe d'addition s'applique alors :

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E\times F)=\sum _{i=1}^n\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(P_i)=\sum _{i=1}^n\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)=n\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)\times \mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)\mathrm{.}\mathrm{\square }$$

Démonstration. Par récurrence sur $p$. Pour $p=1$, il n'y a rien à démontrer. Supposons le résultat vrai au rang $p$ et donnons-nous $E_1,\dots ,E_{p+1}$ finis. L'application

$$((x_1,\dots ,x_p),x_{p+1})⟼(x_1,\dots ,x_p,x_{p+1})$$

est une bijection de $(E_1\times \cdots \times E_p)\times E_{p+1}$ sur $E_1\times \cdots \times E_{p+1}$ : deux $(p+1)$-uplets sont égaux si et seulement si leurs coordonnées le sont une à une, ce qui donne à la fois l'injectivité et la surjectivité. Le principe de la bijection, puis le cas de deux facteurs, puis l'hypothèse de récurrence donnent successivement

$$\begin{array}{rl}{\displaystyle \mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E_1\times \cdots \times E_{p+1})}& {\displaystyle =\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}((E_1\times \cdots \times E_p)\times E_{p+1})}\\ {\displaystyle }& {\displaystyle =\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E_1\times \cdots \times E_p)\times \mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E_{p+1})}\\ {\displaystyle }& {\displaystyle =(\prod _{i=1}^p\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E_i))\times \mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E_{p+1})=\prod _{i=1}^{p+1}\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E_i)\mathrm{.}}\end{array}$$

Le cas particulier s'obtient en prenant $E_1=\cdots =E_p=E$. $\mathrm{\square }$

Le lemme du berger

Démonstration. L'ensemble $F$ est fini comme image de l'ensemble fini $E$ par $f$, puisque la surjectivité donne $F=f(E)$. Notons $m=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$ et écrivons $F=\{y_1,\dots ,y_m\}$ avec les $y_j$ deux à deux distincts.

Les fibres $f^{-1}(\{y_1\}),\dots ,f^{-1}(\{y_m\})$ sont deux à deux disjointes : si $x$ appartenait à deux d'entre elles, on aurait $f(x)=y_j$ et $f(x)=y_{j^{\mathrm{\prime }}}$ avec $j\mathrm{\ne }{j}^{\mathrm{\prime }}$, ce qui contredirait l'unicité de l'image de $x$. Leur réunion est $E$ : tout $x\in E$ appartient à la fibre au-dessus de $f(x)$, qui est l'un des $y_j$. Elles constituent donc une partition de $E$, aucune n'étant vide puisque leur cardinal commun $k$ est non nul.

Le principe d'addition donne alors

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=\sum _{j=1}^m\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f^{-1}(\{y_j\}))=\sum _{j=1}^{m}k=km=k\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)\mathrm{.}\mathrm{\square }$$

Le double comptage

Un ensemble fini n'a qu'un cardinal. Si l'on parvient à le calculer de deux manières différentes, les deux résultats sont nécessairement égaux, et cette égalité est une identité, souvent non évidente. C'est le principe du double comptage, dont le rendement est sans commune mesure avec la simplicité.

Démonstration. Point 1. C'est le principe d'addition appliqué successivement aux deux familles, chacune calculant le même nombre $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(X)$.

Point 2. Pour $x\in E$, posons $A_x=X\cap (\{x\}\times F)$. Ces ensembles sont deux à deux disjoints, car deux d'entre eux contiennent des couples de premières coordonnées distinctes, et leur réunion est $X$, car tout élément de $X$ est un couple dont la première coordonnée appartient à $E$. De plus l'application $y\mapsto (x,y)$ réalise une bijection de $X_x$ sur $A_x$, donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A_x)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(X_x)$. Le point 1 donne la première égalité, et le même raisonnement mené sur la seconde coordonnée donne la seconde. $\mathrm{\square }$

Listes, arrangements et permutations

Les trois sections précédentes ont mis en place les outils de comptage : le principe d'addition pour une réunion disjointe, le principe multiplicatif pour un produit cartésien, le lemme du berger pour les situations où l'on compte chaque objet plusieurs fois, et le double comptage. Il reste à les faire travailler sur les quatre familles d'objets qui reviennent dans absolument tous les exercices : les listes, les applications, les parties d'un ensemble, et les listes à éléments distincts. Chacune de ces familles est comptée une fois pour toutes, et l'essentiel du travail d'un exercice de dénombrement consiste ensuite à reconnaître laquelle est en jeu.

Dans toute cette section, $E$ désigne un ensemble fini, de cardinal $n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$, et $p$ un entier naturel. Aucune hypothèse n'est faite sur la nature des éléments de $E$ : ce sont des chiffres, des lettres, des personnes ou des cases, cela ne change rien aux formules.

$p$-listes et applications

Démonstration. Par récurrence sur $p$, l'entier $n$ et l'ensemble $E$ étant fixés.

Initialisation. Pour $p=0$, l'ensemble $E^0$ est réduit à la liste vide, donc de cardinal $1$, et $n^0=1$.

Hérédité. Supposons $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E^p)=n^p$ pour un certain $p\in \mathbb{N}$. L'application

$$\phi :E^{p+1}⟶E^p\times E,(x_1,\dots ,x_p,x_{p+1})⟼((x_1,\dots ,x_p),x_{p+1})$$

est bijective : sa réciproque est $((x_1,\dots ,x_p),y)⟼(x_1,\dots ,x_p,y)$, et les deux composées sont l'identité par lecture directe. Deux ensembles en bijection ont même cardinal, donc, par le principe multiplicatif appliqué au produit $E^p\times E$,

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left(E^{p+1}\right)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left(E^p\right)\times \mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=n^p\times n=n^{p+1}\mathrm{.}$$

La propriété est héréditaire, donc vraie pour tout $p\in \mathbb{N}$. $\mathrm{\square }$

Démonstration. L'ensemble $F$ étant fini de cardinal $p$, il existe une bijection de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ sur $F$ ; en notant $y_i$ l'image de $i$ par cette bijection, on dispose d'une énumération $F=\{y_1,y_2,\dots ,y_p\}$ dont les termes sont deux à deux distincts. Considérons alors

$$\mathrm{\Phi }:\mathcal{F}(F,E)⟶E^p,f⟼(f(y_1),f(y_2),\dots ,f(y_p))\mathrm{.}$$

Injectivité. Soient $f$ et $g$ deux applications de $F$ dans $E$ telles que $\mathrm{\Phi }(f)=\mathrm{\Phi }(g)$. Alors $f(y_i)=g(y_i)$ pour tout $i\in [\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$. Or tout élément de $F$ est l'un des $y_i$, donc $f$ et $g$ coïncident en tout point de $F$ : elles sont égales.

Surjectivité. Soit $(a_1,\dots ,a_p)\in E^p$. Comme les $y_i$ sont deux à deux distincts et épuisent $F$, la relation $f(y_i)=a_i$ définit sans ambiguïté une application $f$ de $F$ dans $E$ : tout élément de $F$ a une image, et une seule. Par construction, $\mathrm{\Phi }(f)=(a_1,\dots ,a_p)$.

Ainsi $\mathrm{\Phi }$ est bijective, et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{F}(F,E))=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E^p)=n^p$ d'après le théorème précédent. $\mathrm{\square }$

Nombre de parties d'un ensemble

Le passage des applications aux parties se fait par un objet minuscule qui traduit une partie en application, et réciproquement.

Première démonstration, par la fonction indicatrice. Considérons l'application

$$\mathrm{\Psi }:\mathcal{P}(E)⟶\mathcal{F}(E,\{0,1\}),A⟼{\mathbf{1}}_A,$$

et l'application dans l'autre sens

$$\mathrm{\Theta }:\mathcal{F}(E,\{0,1\})⟶\mathcal{P}(E),f⟼f^{-1}(\{1\})=\{x\in E:f(x)=1\}\mathrm{.}$$

Calcul de $\mathrm{\Theta }\circ \mathrm{\Psi }$. Soit $A\in \mathcal{P}(E)$. Par définition de ${\mathbf{1}}_A$, l'égalité ${\mathbf{1}}_A(x)=1$ équivaut à $x\in A$, donc $\mathrm{\Theta }(\mathrm{\Psi }(A))=\{x\in E:{\mathbf{1}}_A(x)=1\}=A$.

Calcul de $\mathrm{\Psi }\circ \mathrm{\Theta }$. Soit $f\in \mathcal{F}(E,\{0,1\})$ et posons $A=\mathrm{\Theta }(f)$. Soit $x\in E$. L'application $f$ ne prend que les valeurs $0$ et $1$, deux cas se présentent donc. Si $f(x)=1$, alors $x\in A$, donc ${\mathbf{1}}_A(x)=1=f(x)$. Si $f(x)=0$, alors $x\mathrm{\notin }A$, donc ${\mathbf{1}}_A(x)=0=f(x)$. Les deux applications coïncident en tout point : $\mathrm{\Psi }(\mathrm{\Theta }(f))={\mathbf{1}}_A=f$.

Les deux composées valent l'identité, donc $\mathrm{\Psi }$ est bijective et $\mathrm{\Theta }$ est sa réciproque. Par conséquent

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{P}(E))=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left(\mathcal{F}\right(E,\{0,1\}\left)\right)=2^n,$$

d'après le théorème du nombre d'applications, appliqué avec une source de cardinal $n$ et un but de cardinal $2$. $\mathrm{\square }$

Seconde démonstration, par récurrence sur $n$. Pour $n\in \mathbb{N}$, notons $H_n$ l'assertion : « tout ensemble de cardinal $n$ possède exactement $2^n$ parties ». L'énoncé porte sur tous les ensembles de cardinal $n$, et non sur un ensemble particulier : c'est indispensable pour que l'hérédité fonctionne.

Initialisation. Un ensemble de cardinal $0$ est vide, et $\mathcal{P}(\mathrm{\varnothing })=\{\mathrm{\varnothing }\}$ est de cardinal $1=2^0$. Donc $H_0$ est vraie.

Hérédité. Supposons $H_n$ vraie pour un certain $n\in \mathbb{N}$, et soit $E$ un ensemble de cardinal $n+1$. Comme $n+1⩾1$, l'ensemble $E$ est non vide : fixons $a\in E$ et posons $E^{\mathrm{\prime }}=E\setminus \{a\}$, de cardinal $n$ d'après la formule du complémentaire. Séparons les parties de $E$ selon qu'elles contiennent $a$ ou non :

$$\mathcal{A}=\{A\in \mathcal{P}(E):a\mathrm{\notin }A\},\mathcal{B}=\{A\in \mathcal{P}(E):a\in A\}\mathrm{.}$$

Ces deux ensembles sont disjoints et leur réunion est $\mathcal{P}(E)$ tout entier, puisque toute partie de $E$ contient $a$ ou ne le contient pas, et pas les deux.

Pour $\mathcal{A}$ : dire que $A\subset E$ et $a\mathrm{\notin }A$, c'est exactement dire que $A\subset E^{\mathrm{\prime }}$. Donc $\mathcal{A}=\mathcal{P}(E^{\mathrm{\prime }})$, et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{A})=2^n$ par hypothèse de récurrence.

Pour $\mathcal{B}$ : l'application $u:A⟼A\setminus \{a\}$ envoie $\mathcal{B}$ dans $\mathcal{P}(E^{\mathrm{\prime }})$, et l'application $v:B⟼B\cup \{a\}$ envoie $\mathcal{P}(E^{\mathrm{\prime }})$ dans $\mathcal{B}$. Si $A\in \mathcal{B}$, alors $a\in A$ et $(A\setminus \{a\})\cup \{a\}=A$ ; si $B\subset E^{\mathrm{\prime }}$, alors $a\mathrm{\notin }B$ et $(B\cup \{a\})\setminus \{a\}=B$. Les deux composées valent l'identité, donc $u$ est bijective et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{B})=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{P}(E^{\mathrm{\prime }}))=2^n$, toujours par hypothèse de récurrence.

Le principe d'addition, appliqué à la réunion disjointe de $\mathcal{A}$ et $\mathcal{B}$, donne

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{P}(E))=2^n+2^n=2^{n+1},$$

ce qui est $H_{n+1}$. La propriété est donc vraie pour tout $n\in \mathbb{N}$. $\mathrm{\square }$

Arrangements et injections

La factorielle, définie au paragraphe suivant par $n!=1\times 2\times \cdots \times n$, permet d'écrire ce produit sous forme condensée : pour $0⩽p⩽n$,

$$A_n^p=\frac{n!}{(n-p)!},$$

car ${\displaystyle \frac{n!}{(n-p)!}}={\displaystyle \frac{n(n-1)\cdots (n-p+1)\times (n-p)!}{(n-p)!}}$ après simplification des facteurs communs.

Démonstration. Point 1. Soit $(x_1,\dots ,x_p)$ un arrangement de $p$ éléments de $E$. L'application $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]\to E$, $i⟼x_i$, est injective, précisément parce que les $x_i$ sont deux à deux distincts. Une injection d'un ensemble fini dans un autre impose l'inégalité des cardinaux, donc $p⩽n$. Par contraposée, si $p>n$, il n'existe aucun arrangement de $p$ éléments de $E$, et $A_n^p=0$.

Point 2. Raisonnons par récurrence sur $p$, l'assertion $H_p$ étant : « pour tout ensemble fini $E$ de cardinal $n⩾p$, le nombre de $p$-listes d'éléments distincts de $E$ vaut $n(n-1)\cdots (n-p+1)$ ». Là encore, la quantification sur tous les $E$ et tous les $n⩾p$ est nécessaire.

Initialisation. Pour $p=0$, la seule $0$-liste est la liste vide, ses composantes sont trivialement distinctes deux à deux, et le produit vide vaut $1$. Donc $H_0$ est vraie.

Hérédité. Supposons $H_p$ vraie, et soient $n⩾p+1$ et $E$ de cardinal $n$. Notons ${\mathcal{A}}_{p+1}$ l'ensemble des $(p+1)$-listes d'éléments distincts de $E$ et ${\mathcal{A}}_p$ celui des $p$-listes d'éléments distincts de $E$. Considérons l'application de troncature

$$\tau :{\mathcal{A}}_{p+1}⟶{\mathcal{A}}_p,(x_1,\dots ,x_p,x_{p+1})⟼(x_1,\dots ,x_p)\mathrm{.}$$

Elle est bien définie : si les $p+1$ composantes sont deux à deux distinctes, les $p$ premières le sont aussi.

$\tau$ est surjective. Soit $(x_1,\dots ,x_p)\in {\mathcal{A}}_p$. L'ensemble $\{x_1,\dots ,x_p\}$ compte exactement $p$ éléments, donc son complémentaire $E\setminus \{x_1,\dots ,x_p\}$ est de cardinal $n-p⩾1$ : il est non vide. En y choisissant un élément $x_{p+1}$, on obtient un antécédent.

Toutes les fibres ont le même cardinal. Soit $(x_1,\dots ,x_p)\in {\mathcal{A}}_p$. Un antécédent par $\tau$ est une liste $(x_1,\dots ,x_p,y)$ dont les composantes sont deux à deux distinctes, c'est-à-dire un élément $y$ de $E$ différent de $x_1,\dots ,x_p$ : autrement dit $y\in E\setminus \{x_1,\dots ,x_p\}$. L'application $(x_1,\dots ,x_p,y)⟼y$ réalise donc une bijection de la fibre sur $E\setminus \{x_1,\dots ,x_p\}$, dont le cardinal vaut $n-p$. Ce nombre ne dépend pas de la fibre choisie.

Le lemme du berger s'applique : $\tau$ est surjective et toutes ses fibres ont pour cardinal $n-p$, donc

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left({\mathcal{A}}_{p+1}\right)=(n-p)\times \mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left({\mathcal{A}}_p\right)=(n-p)\times n(n-1)\cdots (n-p+1),$$

et le facteur ajouté est bien le suivant dans la suite décroissante, puisque $n-p=n-(p+1)+1$. L'assertion $H_{p+1}$ est établie, et la récurrence est terminée. $\mathrm{\square }$

Démonstration. Reprenons l'énumération $F=\{y_1,\dots ,y_p\}$ à termes deux à deux distincts et la bijection

$$\mathrm{\Phi }:\mathcal{F}(F,E)⟶E^p,f⟼(f(y_1),\dots ,f(y_p))$$

construite plus haut. Montrons que, pour $f\in \mathcal{F}(F,E)$,

$$f\text{ est injective}⟺\mathrm{\Phi }(f)\text{ est une }p\text{-liste d’}\acute{\text{e}}\text{l}\acute{\text{e}}\text{ments distincts.}$$

Sens direct. Si $f$ est injective et si $i\mathrm{\ne }j$, alors $y_i\mathrm{\ne }{y}_j$ (l'énumération est à termes distincts), donc $f(y_i)\mathrm{\ne }f(y_j)$ : les composantes de $\mathrm{\Phi }(f)$ sont deux à deux distinctes.

Sens réciproque. Supposons les composantes de $\mathrm{\Phi }(f)$ deux à deux distinctes, et soient $y,y^{\mathrm{\prime }}\in F$ tels que $f(y)=f(y^{\mathrm{\prime }})$. Écrivons $y=y_i$ et $y^{\mathrm{\prime }}=y_j$. Si l'on avait $i\mathrm{\ne }j$, les composantes d'indices $i$ et $j$ de $\mathrm{\Phi }(f)$ seraient égales, ce qui est exclu. Donc $i=j$, puis $y=y^{\mathrm{\prime }}$ : l'application $f$ est injective.

La restriction d'une bijection à une partie de son ensemble de départ est une bijection de cette partie sur son image. Ici, $\mathrm{\Phi }$ induit donc une bijection de l'ensemble des injections de $F$ dans $E$ sur l'ensemble des $p$-listes d'éléments distincts de $E$. Ces deux ensembles ont même cardinal, égal à $A_n^p$. $\mathrm{\square }$

Permutations et factorielle

La convention $0!=1$ n'est pas un caprice : c'est la valeur du produit vide, et c'est la seule qui rende la relation de récurrence valable dès $n=0$ et la formule $A_n^n=\frac{n!}{0!}=n!$ correcte. Toutes les formules du chapitre reposent dessus.

Démonstration. L'ensemble de départ et l'ensemble d'arrivée sont ici le même ensemble fini $E$, donc ils ont même cardinal. Le théorème d'équivalence établi plus haut s'applique : une application de $E$ dans $E$ est bijective si et seulement si elle est injective. Par conséquent, $\mathfrak{S}(E)$ est exactement l'ensemble des injections de $E$ dans $E$.

Le théorème du nombre d'injections, appliqué avec $p=n$, donne

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathfrak{S}(E))=A_n^n=\frac{n!}{(n-n)!}=\frac{n!}{0!}=n!\mathrm{.}\mathrm{\square }$$

Démonstration. Les ensembles $E$ et $F$ ayant même cardinal, le théorème d'équivalence montre qu'une application de $E$ dans $F$ est bijective si et seulement si elle est injective : les bijections de $E$ sur $F$ sont donc exactement les injections de $E$ dans $F$. Le théorème du nombre d'injections, appliqué avec $p=n$, en donne $A_n^n=n!$. $\mathrm{\square }$

Combinaisons et coefficients binomiaux

Toutes les situations traitées jusqu'ici étaient ordonnées. Or la majorité des questions concrètes ne le sont pas : choisir trois délégués parmi trente, distribuer une main de cartes, former une équipe, sélectionner un sous-ensemble. L'objet à compter est alors une partie, et non une liste. Le lemme du berger fait le pont entre les deux, et il produit les nombres les plus utilisés de toutes les mathématiques de première année.

Définition combinatoire et formule

Démonstration, par le lemme du berger. Soit $E$ un ensemble de cardinal $n$ et soit $p\in [\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$. Notons $\mathcal{A}$ l'ensemble des $p$-listes d'éléments distincts de $E$, de cardinal $A_n^p$, et considérons l'application

$$f:\mathcal{A}⟶{\mathcal{P}}_p(E),(x_1,\dots ,x_p)⟼\{x_1,\dots ,x_p\},$$

qui à une liste associe l'ensemble de ses composantes, autrement dit qui oublie l'ordre.

$f$ est bien définie. Les $x_i$ étant deux à deux distincts, l'ensemble $\{x_1,\dots ,x_p\}$ compte exactement $p$ éléments : c'est bien un élément de ${\mathcal{P}}_p(E)$.

$f$ est surjective. Soit $A\in {\mathcal{P}}_p(E)$. L'ensemble $A$ est fini de cardinal $p$, donc il existe une bijection de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ sur $A$ ; en notant $x_i$ l'image de $i$, la liste $(x_1,\dots ,x_p)$ a ses composantes deux à deux distinctes, appartient à $\mathcal{A}$, et $f$ l'envoie sur $A$.

Toutes les fibres ont pour cardinal $p!$. Soit $A\in {\mathcal{P}}_p(E)$. Un antécédent de $A$ est une $p$-liste d'éléments distincts dont l'ensemble des composantes est exactement $A$. À une telle liste $(x_1,\dots ,x_p)$ associons l'application $g:[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]\to A$, $i⟼x_i$ : elle est injective (composantes distinctes) et surjective sur $A$ (l'ensemble des composantes est $A$), donc bijective. Réciproquement, toute bijection $g$ de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ sur $A$ fournit la liste $(g(1),\dots ,g(p))$, qui est un antécédent de $A$. Ces deux constructions sont réciproques l'une de l'autre, donc la fibre $f^{-1}(\{A\})$ est en bijection avec l'ensemble des bijections de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ sur $A$. Ces deux ensembles étant de même cardinal $p$, ces bijections sont exactement les injections, au nombre de $A_p^p=p!$. La fibre a donc pour cardinal $p!$, indépendamment de $A$.

Le lemme du berger s'applique et donne $A_n^p=p!\times {\displaystyle \left(\genfrac{}{}{0px}{}{n}{p}\right)}$, c'est-à-dire, puisque $p!\mathrm{\ne }0$,

$${\displaystyle \left(\genfrac{}{}{0px}{}{n}{p}\right)}=\frac{A_n^p}{p!}=\frac{1}{p!}\times \frac{n!}{(n-p)!}=\frac{n!}{p!(n-p)!}\mathrm{.}\mathrm{\square }$$

Premières propriétés

Démonstration. Soit $E$ de cardinal $n$. La seule partie de $E$ de cardinal $0$ est $\mathrm{\varnothing }$, d'où ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{0}\right)}=1$. Une partie de $E$ de cardinal $n$ est, d'après le cas d'égalité pour le cardinal d'une partie, égale à $E$ tout entier ; il y en a donc exactement une, et ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{n}\right)}=1$. Les parties de cardinal $1$ sont les singletons $\{x\}$ avec $x\in E$, et $x⟼\{x\}$ est une bijection de $E$ sur ${\mathcal{P}}_1(E)$, de réciproque « unique élément de », d'où ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{1}\right)}=n$. La dernière égalité résultera de la symétrie ci-dessous, ou directement du fait que $A⟼\bar{A}$ échange parties à $1$ élément et parties à $n-1$ éléments. $\mathrm{\square }$

Première démonstration, combinatoire. Traitons d'abord le cas $0⩽p⩽n$. Soit $E$ de cardinal $n$, et considérons l'application de passage au complémentaire

$$c:{\mathcal{P}}_p(E)⟶{\mathcal{P}}_{n-p}(E),A⟼\bar{A}=E\setminus A\mathrm{.}$$

Elle est bien définie : la formule du cardinal du complémentaire donne $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\bar{A})=n-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=n-p$. Elle est involutive, c'est-à-dire que $\overline{\stackrel{‾}{A}}=A$ pour toute partie $A$ de $E$ ; l'application ${\mathcal{P}}_{n-p}(E)\to {\mathcal{P}}_p(E)$, $B⟼\bar{B}$, est donc sa réciproque, et $c$ est bijective. Les deux ensembles ont même cardinal, ce qui est l'égalité annoncée.

Si maintenant $p<0$, alors $n-p>n$, et les deux membres sont nuls ; si $p>n$, alors $n-p<0$, et les deux membres sont encore nuls. L'égalité vaut donc pour tout $p\in \mathbb{Z}$.

Seconde démonstration, par la formule. Pour $0⩽p⩽n$, l'entier $n-p$ appartient aussi à $[\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$ et

$${\displaystyle \left(\genfrac{}{}{0px}{}{n}{n-p}\right)}=\frac{n!}{(n-p)!(n-(n-p))!}=\frac{n!}{(n-p)!p!}={\displaystyle \left(\genfrac{}{}{0px}{}{n}{p}\right)},$$

la formule des combinaisons étant symétrique en $p$ et $n-p$ au dénominateur. $\mathrm{\square }$

Première démonstration, par double comptage. Soit $E$ de cardinal $n⩾1$. Comptons de deux manières l'ensemble

$$\mathcal{C}=\{(A,x):A\in {\mathcal{P}}_p(E)\text{ et }x\in A\},$$

c'est-à-dire l'ensemble des comités de $p$ personnes munis d'un président choisi dans le comité.

Le comité d'abord. Regroupons les couples selon leur première composante : pour $A\in {\mathcal{P}}_p(E)$ fixé, les couples de $\mathcal{C}$ de première composante $A$ sont les $(A,x)$ avec $x\in A$, et ils sont en bijection avec $A$, donc au nombre de $p$. Ces paquets sont deux à deux disjoints, leur réunion est $\mathcal{C}$, et il y en a ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{p}\right)}$. Le principe d'addition donne

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{C})=p{\displaystyle \left(\genfrac{}{}{0px}{}{n}{p}\right)}\mathrm{.}$$

Le président d'abord. Regroupons cette fois selon la seconde composante. Pour $x\in E$ fixé, notons ${\mathcal{C}}_x$ l'ensemble des couples de $\mathcal{C}$ de seconde composante $x$. Ces paquets sont deux à deux disjoints, leur réunion est $\mathcal{C}$, et il y en a $n$. Le cardinal de ${\mathcal{C}}_x$ est celui de l'ensemble des parties $A$ de cardinal $p$ contenant $x$. Or l'application

$$A⟼A\setminus \{x\}$$

réalise une bijection de cet ensemble sur ${\mathcal{P}}_{p-1}(E\setminus \{x\})$ : si $x\in A$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=p$, alors $A\setminus \{x\}$ est inclus dans $E\setminus \{x\}$ et de cardinal $p-1$ ; réciproquement, si $B\subset E\setminus \{x\}$ est de cardinal $p-1$, alors $B\cup \{x\}$ est de cardinal $p$ (réunion disjointe) et contient $x$ ; les deux applications sont réciproques l'une de l'autre. Comme $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E\setminus \{x\})=n-1$, on obtient $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{C}}_x)={\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)}$, valeur indépendante de $x$, et

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{C})=n{\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)}\mathrm{.}$$

Les deux comptages portant sur le même ensemble, les résultats sont égaux.

Seconde démonstration, par le calcul. Pour $1⩽p⩽n$,

$$\begin{array}{rl}{\displaystyle p{\displaystyle \left(\genfrac{}{}{0px}{}{n}{p}\right)}}& {\displaystyle =p\times \frac{n!}{p!(n-p)!}=\frac{n!}{(p-1)!(n-p)!}}\\ {\displaystyle }& {\displaystyle =n\times \frac{(n-1)!}{(p-1)!(n-p)!}=n\times \frac{(n-1)!}{(p-1)!((n-1)-(p-1))!}=n{\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)},}\end{array}$$

en utilisant $p!=p\times (p-1)!$, puis $n!=n\times (n-1)!$, et enfin $(n-1)-(p-1)=n-p$. $\mathrm{\square }$

Formule de Pascal et triangle

Première démonstration, combinatoire. Soit $E$ un ensemble de cardinal $n⩾1$. Comme $E$ est non vide, fixons $a\in E$ et posons $E^{\mathrm{\prime }}=E\setminus \{a\}$, de cardinal $n-1$. Séparons les parties de $E$ à $p$ éléments selon qu'elles contiennent $a$ ou non :

$$\mathcal{X}=\{A\in {\mathcal{P}}_p(E):a\mathrm{\notin }A\},\mathcal{Y}=\{A\in {\mathcal{P}}_p(E):a\in A\}\mathrm{.}$$

Ces deux ensembles sont disjoints et leur réunion est ${\mathcal{P}}_p(E)$, puisqu'une partie contient $a$ ou ne le contient pas, et pas les deux à la fois.

Cardinal de $\mathcal{X}$. Dire que $A\subset E$, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=p$ et $a\mathrm{\notin }A$, c'est dire que $A\subset E^{\mathrm{\prime }}$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=p$. Donc $\mathcal{X}={\mathcal{P}}_p(E^{\mathrm{\prime }})$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{X})={\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{p}\right)}$.

Cardinal de $\mathcal{Y}$. L'application $A⟼A\setminus \{a\}$ envoie $\mathcal{Y}$ dans ${\mathcal{P}}_{p-1}(E^{\mathrm{\prime }})$ : si $a\in A$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=p$, alors $A\setminus \{a\}$ est inclus dans $E^{\mathrm{\prime }}$ et de cardinal $p-1$. L'application $B⟼B\cup \{a\}$ envoie ${\mathcal{P}}_{p-1}(E^{\mathrm{\prime }})$ dans $\mathcal{Y}$ : si $B\subset E^{\mathrm{\prime }}$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)=p-1$, alors $a\mathrm{\notin }B$, donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B\cup \{a\})=p$ par réunion disjointe, et cette partie contient $a$. Les deux composées valent l'identité. Donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{Y})={\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)}$.

Le principe d'addition conclut. Le raisonnement n'a utilisé aucune hypothèse sur $p$ : lorsque $p$ sort de $[\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$, les ensembles en jeu sont vides et l'égalité se lit $0=0+0$, ce qui reste conforme.

Seconde démonstration, par le calcul. Les cas dégénérés se vérifient directement : pour $p⩽-1$ ou $p⩾n+1$, les trois coefficients sont nuls ; pour $p=0$, l'égalité s'écrit $0+1=1$ ; pour $p=n$, elle s'écrit $1+0=1$. Supposons donc $1⩽p⩽n-1$. Alors

$$\begin{array}{rl}{\displaystyle {\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)}+{\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{p}\right)}}& {\displaystyle =\frac{(n-1)!}{(p-1)!(n-p)!}+\frac{(n-1)!}{p!(n-1-p)!}}\\ {\displaystyle }& {\displaystyle =\frac{p\times (n-1)!}{p!(n-p)!}+\frac{(n-p)\times (n-1)!}{p!(n-p)!}}\\ {\displaystyle }& {\displaystyle =\frac{(n-1)!(p+n-p)}{p!(n-p)!}=\frac{n\times (n-1)!}{p!(n-p)!}=\frac{n!}{p!(n-p)!}={\displaystyle \left(\genfrac{}{}{0px}{}{n}{p}\right)},}\end{array}$$

la mise au même dénominateur utilisant $p!=p\times (p-1)!$ pour le premier terme et $(n-p)!=(n-p)\times (n-1-p)!$ pour le second. $\mathrm{\square }$

La formule de Pascal fournit une construction de proche en proche de tous les coefficients binomiaux : chaque coefficient de la ligne $n$ est la somme de deux coefficients voisins de la ligne $n-1$. En disposant les lignes les unes sous les autres, on obtient le triangle de Pascal, dont les bords ne contiennent que des $1$ puisque ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{0}\right)}={\displaystyle \left(\genfrac{}{}{0px}{}{n}{n}\right)}=1$.

Formule du binôme de Newton

L'écriture ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}{a}^k{b}^{n-k}$ désigne, dans un anneau quelconque, la somme de ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}$ termes tous égaux à $a^k{b}^{n-k}$ ; dans $\mathbb{R}$ ou dans $\mathbb{C}$, c'est le produit ordinaire.

Démonstration, combinatoire. Écrivons la puissance comme un produit de $n$ facteurs identiques :

$$(a+b{)}^n=\underset{n\text{ facteurs}}{\underbrace{(a+b)(a+b)\cdots (a+b)}}\mathrm{.}$$

Le développement par distributivité consiste à choisir, dans chaque facteur, l'un des deux termes $a$ ou $b$, à multiplier les $n$ termes choisis, puis à sommer sur tous les choix possibles. Un choix est entièrement décrit par l'ensemble

$$I=\{i\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]:\text{ on a pris }a\text{ dans le }i\text{-}\grave{\text{e}}\text{me facteur}\},$$

qui est une partie quelconque de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$, et réciproquement toute partie $I$ correspond à un choix et un seul. Le développement s'écrit donc

$$(a+b{)}^n=\sum _{I\in \mathcal{P}([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}])}\left(\prod _{i\in I}a\right)\left(\prod _{i\mathrm{\notin }I}b\right)\mathrm{.}$$

Comme $a$ et $b$ commutent, on peut réordonner les facteurs de chaque produit sans en changer la valeur, et le terme associé à $I$ vaut $a^{\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(I)}{b}^{n-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(I)}$, où l'exposant de $b$ est $n-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(I)$ d'après la formule du complémentaire. Ainsi

$$(a+b{)}^n=\sum _{I\in \mathcal{P}([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}])}{a}^{\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(I)}{b}^{n-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(I)}\mathrm{.}$$

Il reste à regrouper les termes égaux. Toute partie $I$ de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ a un cardinal, et un seul, appartenant à $[\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$ : les ensembles ${\mathcal{P}}_0([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]),\dots ,{\mathcal{P}}_n([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}])$ sont donc deux à deux disjoints et leur réunion est $\mathcal{P}([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}])$. En sommant par paquets,

$$(a+b{)}^n=\sum _{k=0}^n\sum _{I\in {\mathcal{P}}_k([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}])}{a}^k{b}^{n-k}=\sum _{k=0}^n\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{P}}_k([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]))a^k{b}^{n-k}=\sum _{k=0}^n{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}{a}^k{b}^{n-k},$$

puisque, à $k$ fixé, le terme $a^k{b}^{n-k}$ ne dépend plus de $I$ et se trouve répété autant de fois qu'il y a de parties à $k$ éléments. $\mathrm{\square }$

Cette démonstration explique ce que la démonstration par récurrence, menée au chapitre « Compléments de calcul algébrique et de trigonométrie » à partir de la formule de Pascal, se contentait de vérifier : le coefficient de $a^k{b}^{n-k}$ est le nombre de façons de choisir les $k$ facteurs qui fournissent un $a$.

Démonstration. Point 1. La formule du binôme avec $a=b=1$ donne

$$2^n=(1+1{)}^n=\sum _{k=0}^n{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}{1}^k{1}^{n-k}=\sum _{k=0}^n{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}\mathrm{.}$$

Point 2. La formule du binôme avec $a=-1$ et $b=1$ donne, pour $n⩾1$,

$$0=0^n=(-1+1{)}^n=\sum _{k=0}^n{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}(-1{)}^k{1}^{n-k}=\sum _{k=0}^n(-1{)}^k{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}\mathrm{.}$$

Point 3. Le terme d'indice $k=0$ est nul, et le pivot s'applique aux autres :

$$\sum _{k=0}^{n}k{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}=\sum _{k=1}^{n}k{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}=\sum _{k=1}^{n}n{\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)}=n\sum _{j=0}^{n-1}{\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{j}\right)}=n{2}^{n-1},$$

après le changement d'indice $j=k-1$ et l'application du point 1 au rang $n-1$. $\mathrm{\square }$

Formule de Vandermonde

Démonstration, combinatoire. Choisissons deux ensembles finis disjoints $M$ et $N$ de cardinaux respectifs $m$ et $n$ : par exemple $M=[\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$ et $N=[\text{\hspace{0.17em}⁣}[m+1,m+n]\text{\hspace{0.17em}⁣}]$. Posons $E=M\cup N$ ; la réunion étant disjointe, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=m+n$, et le nombre que l'on cherche à atteindre est

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{P}}_p(E))={\displaystyle \left(\genfrac{}{}{0px}{}{m+n}{p}\right)}\mathrm{.}$$

Partitionnons ${\mathcal{P}}_p(E)$ selon le nombre d'éléments pris dans $M$. Pour $k\in [\text{\hspace{0.17em}⁣}[0,p]\text{\hspace{0.17em}⁣}]$, posons

$${\mathcal{E}}_k=\{A\in {\mathcal{P}}_p(E):\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap M)=k\}\mathrm{.}$$

Toute partie $A$ de cardinal $p$ appartient à un ${\mathcal{E}}_k$ et à un seul, celui d'indice $k=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap M)$ ; cet indice est bien dans $[\text{\hspace{0.17em}⁣}[0,p]\text{\hspace{0.17em}⁣}]$ puisque $A\cap M\subset A$ entraîne $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap M)⩽p$. Les ${\mathcal{E}}_k$ sont donc deux à deux disjoints et leur réunion est ${\mathcal{P}}_p(E)$.

Calculons $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{E}}_k)$. Considérons

$$\theta :{\mathcal{E}}_k⟶{\mathcal{P}}_k(M)\times {\mathcal{P}}_{p-k}(N),A⟼(A\cap M,A\cap N)\mathrm{.}$$

Elle est bien définie : les ensembles $A\cap M$ et $A\cap N$ sont disjoints et leur réunion vaut $A\cap (M\cup N)=A$, donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap M)+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap N)=p$, d'où $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap N)=p-k$. L'application $(B,C)⟼B\cup C$ va dans l'autre sens, et les deux composées valent l'identité : pour $A\in {\mathcal{E}}_k$, $(A\cap M)\cup (A\cap N)=A$ comme on vient de le voir ; et pour $B\subset M$, $C\subset N$, on a $(B\cup C)\cap M=B$ et $(B\cup C)\cap N=C$, car $M$ et $N$ sont disjoints, donc $C\cap M=\mathrm{\varnothing }$ et $B\cap N=\mathrm{\varnothing }$. Ainsi $\theta$ est bijective, et le principe multiplicatif donne

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{E}}_k)={\displaystyle \left(\genfrac{}{}{0px}{}{m}{k}\right)}{\displaystyle \left(\genfrac{}{}{0px}{}{n}{p-k}\right)}\mathrm{.}$$

Le principe d'addition, appliqué à la famille $({\mathcal{E}}_k{)}_{0⩽k⩽p}$, dont les termes sont deux à deux disjoints et de réunion ${\mathcal{P}}_p(E)$, conclut :

$${\displaystyle \left(\genfrac{}{}{0px}{}{m+n}{p}\right)}=\sum _{k=0}^p{\displaystyle \left(\genfrac{}{}{0px}{}{m}{k}\right)}{\displaystyle \left(\genfrac{}{}{0px}{}{n}{p-k}\right)}\mathrm{.}\mathrm{\square }$$

Les termes pour lesquels $k>m$ ou $p-k>n$ sont nuls, conformément à la convention de nullité : ils correspondent à des ${\mathcal{E}}_k$ vides, aucune partie ne pouvant prendre plus de $m$ éléments dans $M$.

Démonstration. Appliquons la formule de Vandermonde avec $m=n$ et $p=n$ :

$$\sum _{k=0}^n{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}{\displaystyle \left(\genfrac{}{}{0px}{}{n}{n-k}\right)}={\displaystyle \left(\genfrac{}{}{0px}{}{2n}{n}\right)}\mathrm{.}$$

La symétrie donne ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{n-k}\right)}={\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}$ pour tout $k$, d'où le résultat. $\mathrm{\square }$

Méthodes

Les exercices de dénombrement se résolvent tous de la même manière : on nomme précisément l'ensemble que l'on compte, on choisit le modèle, on justifie ce choix par une bijection ou une partition, et seulement alors on calcule. Un résultat annoncé sans modèle explicité ne vaut aucun point, même s'il est juste. Les sept encadrés qui suivent recensent les gestes utiles.