Dénombrement

Dénombrer, c'est répondre à une question d'apparence naïve : combien y a-t-il d'objets d'un type donné ? Combien de mots de cinq lettres, combien de comités de cinq personnes prises parmi douze, combien de chemins d'un coin à l'autre d'un quadrillage ? La question est naïve, la réponse ne l'est pas : la difficulté n'est presque jamais dans le calcul final, elle est dans la description exacte de ce que l'on compte. Une réponse fausse en dénombrement vient neuf fois sur dix d'un énoncé mal lu (l'ordre comptait-il ?), d'objets comptés deux fois, ou d'un modèle plaqué sans réflexion. C'est pourquoi ce chapitre insiste beaucoup sur la rédaction : identifier l'ensemble que l'on dénombre, dire à quel modèle il correspond, et seulement ensuite calculer.

Le programme est explicite sur un point : toute formalisation excessive est exclue. Nous ne construirons donc pas la notion d'entier naturel, et les propriétés les plus intuitives du cardinal seront admises, en le signalant à chaque fois. En revanche, tout ce qui relève du raisonnement de dénombrement proprement dit sera démontré : le théorème d'équivalence entre injectivité, surjectivité et bijectivité en cardinaux égaux, les opérations sur les cardinaux, le nombre d'applications, le nombre de parties, les arrangements, les combinaisons, la formule de Pascal et la formule du binôme. Ces deux dernières seront établies par voie combinatoire, comme le demande le programme : on compte le même ensemble de deux manières différentes, et l'identité tombe. C'est une façon de faire des mathématiques que vous ne connaissez sans doute pas encore, et qui est l'un des vrais apports de ce chapitre.

Les notations suivantes valent pour tout le chapitre. Les lettres $E$, $F$, $G$ désignent des ensembles, $A$, $B$, $C$ des parties d'un ensemble, $\mathcal{P}(E)$ l'ensemble des parties de $E$, $\bar{A}$ le complémentaire de $A$ dans un ensemble ambiant précisé par le contexte, $A\setminus B$ la différence, ${\mathbf{1}}_A$ la fonction indicatrice de $A$, $\mathcal{F}(E,F)$ ou $F^E$ l'ensemble des applications de $E$ dans $F$, ${\mathrm{i}\mathrm{d}}_E$ l'identité de $E$, et $[\text{\hspace{0.17em}⁣}[a,b]\text{\hspace{0.17em}⁣}]$ l'ensemble des entiers $k$ tels que $a⩽k⩽b$. Le cardinal s'écrit toujours $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$ : le programme mentionne aussi une notation avec des barres verticales, que nous n'emploierons jamais ici, pour éviter toute confusion avec la valeur absolue et le module. Enfin, le symbole $\mathrm{\square }$ marque la fin d'une démonstration.

Ensembles finis et cardinal

Définition d'un ensemble fini

Tout part de l'idée la plus simple qui soit : un ensemble est fini lorsqu'on peut en numéroter les éléments, de $1$ jusqu'à un certain entier, sans en oublier ni en compter deux fois. Numéroter, c'est exactement se donner une bijection depuis un intervalle d'entiers.

Pour $n=0$, l'intervalle $[\text{\hspace{0.17em}⁣}[1,0]\text{\hspace{0.17em}⁣}]$ est vide, et l'unique application de l'ensemble vide dans l'ensemble vide est une bijection : l'ensemble vide est donc fini, conformément à l'intuition.

Ce résultat est admis : le programme précise que tout fondement théorique des notions d'entier naturel et de cardinal est hors programme. Il n'est pas pour autant évident, et sa démonstration complète, par récurrence, relève de la théorie des ensembles. Retenez seulement qu'il légitime la définition suivante : l'entier obtenu en comptant les éléments de $E$ ne dépend pas de la manière dont on les a numérotés.

Démonstration. Les points 1 et 2 sont immédiats : l'application vide est une bijection de $[\text{\hspace{0.17em}⁣}[1,0]\text{\hspace{0.17em}⁣}]$ sur $\mathrm{\varnothing }$, donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathrm{\varnothing })=0$ ; réciproquement, si $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=0$, il existe une bijection de $[\text{\hspace{0.17em}⁣}[1,0]\text{\hspace{0.17em}⁣}]=\mathrm{\varnothing }$ sur $E$, et sa surjectivité impose que tout élément de $E$ ait un antécédent dans l'ensemble vide, ce qui n'est possible que si $E$ est vide. Ensuite, $1⟼a$ est une bijection de $[\text{\hspace{0.17em}⁣}[1,1]\text{\hspace{0.17em}⁣}]$ sur $\{a\}$. Si $a\mathrm{\ne }b$, l'application qui envoie $1$ sur $a$ et $2$ sur $b$ est une bijection de $[\text{\hspace{0.17em}⁣}[1,2]\text{\hspace{0.17em}⁣}]$ sur $\{a,b\}$. Pour le point 3, l'identité est une bijection de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur lui-même, et l'application $k⟼k+a-1$ est une bijection de $[\text{\hspace{0.17em}⁣}[1,b-a+1]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[a,b]\text{\hspace{0.17em}⁣}]$ : elle est bien à valeurs dans $[\text{\hspace{0.17em}⁣}[a,b]\text{\hspace{0.17em}⁣}]$, et $k⟼k-a+1$ en est la réciproque. Le point 4 est une simple reformulation de la définition. $\mathrm{\square }$

Parties d'un ensemble fini

Démonstration. Point 1. Comme $x\in E$, on a $n⩾1$. Soit $\phi :[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]\to E$ une bijection, et $i_0={\phi }^{-1}(x)$. Définissons $\psi :[\text{\hspace{0.17em}⁣}[1,n-1]\text{\hspace{0.17em}⁣}]\to E\setminus \{x\}$ par

$$\psi (i)=\{\begin{array}{ll}\phi (i)& \text{si }1⩽i⩽i_0-1,\\ \phi (i+1)& \text{si }{i}_0⩽i⩽n-1.\end{array}$$

Cette application est bien à valeurs dans $E\setminus \{x\}$, car les indices utilisés sont tous différents de $i_0$ et $\phi$ est injective. Elle est injective : si $\psi (i)=\psi (j)$, l'injectivité de $\phi$ donne, selon les cas, $i=j$, ou $i=j+1$ avec $i⩽i_0-1$ et $j⩾i_0$, ce qui est impossible. Elle est surjective : si $y\in E\setminus \{x\}$, alors $y=\phi (k)$ avec $k\mathrm{\ne }{i}_0$ ; si $k<i_0$ alors $y=\psi (k)$, et si $k>i_0$ alors $y=\psi (k-1)$. Ainsi $\psi$ est une bijection et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E\setminus \{x\})=n-1$.

Point 2. Ce point est admis, conformément au préambule du programme, qui indique que les propriétés les plus intuitives du cardinal sont admises sans démonstration. Voici néanmoins l'idée, non exigible : on raisonne par récurrence sur $n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$. Pour $n=0$, la seule partie de $\mathrm{\varnothing }$ est $\mathrm{\varnothing }$. Pour l'hérédité, on fixe $x\in E$ et l'on distingue selon que $x$ appartient ou non à $A$ ; dans les deux cas on se ramène à une partie de $E\setminus \{x\}$, qui est de cardinal $n-1$ d'après le point 1.

Point 3. Supposons $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=n$ et raisonnons par contraposée : supposons $A\mathrm{\ne }E$. Comme $A\subset E$, il existe alors $x\in E$ avec $x\mathrm{\notin }A$. On a donc $A\subset E\setminus \{x\}$, et le point 2 appliqué à la partie $A$ de l'ensemble fini $E\setminus \{x\}$ donne

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)⩽\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E\setminus \{x\})=n-1<n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)\mathrm{.}$$

Ainsi $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)\mathrm{\ne }\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$, ce qui achève la contraposée. $\mathrm{\square }$

Premiers exemples de dénombrement

Applications entre ensembles finis

Injections, surjections et comparaison des cardinaux

Les trois propriétés qui suivent traduisent une idée simple : une injection « range sans écraser », donc l'ensemble de départ ne peut pas être plus gros que celui d'arrivée ; une surjection « couvre tout », donc l'ensemble d'arrivée ne peut pas être plus gros que celui de départ.

Démonstration. Établissons d'abord un fait utilisé partout dans la suite : si deux ensembles sont en bijection et si l'un est fini, alors l'autre l'est aussi et ils ont même cardinal. En effet, soit $g:X\to Y$ une bijection avec $X$ fini de cardinal $n$, et soit $\phi :[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]\to X$ une bijection. Alors $g\circ \phi$ est une bijection de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $Y$, comme composée de deux bijections. Donc $Y$ est fini de cardinal $n$.

Point 1. Supposons $f$ injective et notons $f(E)=\{f(x);x\in E\}$ son image. L'application $\tilde{f}:E\to f(E)$ définie par $\tilde{f}(x)=f(x)$ est surjective par construction, et injective puisque $f$ l'est : c'est donc une bijection. Par le fait préliminaire, $\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. Pour chaque $y\in F$, l'ensemble $f^{-1}(\{y\})$ est non vide ; choisissons-en un élément, que nous notons $s(y)$. On définit ainsi une application $s:F\to E$ vérifiant $f(s(y))=y$ pour tout $y\in F$. Cette application $s$ est injective : si $s(y)=s(y^{\mathrm{\prime }})$, alors en appliquant $f$ on obtient $y=f(s(y))=f(s(y^{\mathrm{\prime }}))=y^{\mathrm{\prime }}$. Le point 1 appliqué à $s$ donne $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)⩽\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$.

Point 3. Une bijection est à la fois injective et surjective : les points 1 et 2 donnent les deux inégalités, donc l'égalité. $\mathrm{\square }$

Le théorème fondamental

Voici le résultat central de cette section, explicitement au programme. Il affirme qu'entre deux ensembles finis de même cardinal, il suffit de vérifier la moitié du travail : l'injectivité entraîne gratuitement la surjectivité, et réciproquement.

Démonstration. Notons $n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$. Nous montrons $1⟹2$, puis $2⟹1$, ce qui suffira à conclure.

Preuve de $1⟹2$. Supposons $f$ injective. Comme dans la démonstration précédente, $f$ induit une bijection de $E$ sur $f(E)$, donc

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f(E))=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)\mathrm{.}$$

Ainsi $f(E)$ est une partie de l'ensemble fini $F$ ayant le même cardinal que $F$ : le point 3 de la propriété sur les parties donne $f(E)=F$, c'est-à-dire que $f$ est surjective.

Preuve de $2⟹1$. Supposons $f$ surjective et raisonnons par l'absurde en supposant $f$ non injective. Il existe alors $a,b\in E$ avec $a\mathrm{\ne }b$ et $f(a)=f(b)$. Posons $E^{\mathrm{\prime }}=E\setminus \{a\}$, de cardinal $n-1$, et considérons la restriction $g:E^{\mathrm{\prime }}\to F$ de $f$ à $E^{\mathrm{\prime }}$. Montrons que $g$ est surjective. Soit $y\in F$ ; par surjectivité de $f$, il existe $x\in E$ tel que $f(x)=y$. Si $x\mathrm{\ne }a$, alors $x\in E^{\mathrm{\prime }}$ et $g(x)=y$. Si $x=a$, alors, comme $b\mathrm{\ne }a$, on a $b\in E^{\mathrm{\prime }}$ et $g(b)=f(b)=f(a)=y$. Dans les deux cas, $y$ a un antécédent par $g$ : $g$ est bien surjective. Le point 2 de la propriété précédente donne alors

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)⩽\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E^{\mathrm{\prime }})=n-1<n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F),$$

ce qui est absurde. Donc $f$ est injective.

Conclusion. Nous avons $1⟹2$ et $2⟹1$, donc les assertions 1 et 2 sont équivalentes. Si l'une des deux est vraie, l'autre l'est aussi, et $f$, à la fois injective et surjective, est bijective : d'où $1⟹3$. Enfin $3⟹1$ est immédiat. Les trois assertions sont donc équivalentes. $\mathrm{\square }$

Le principe des tiroirs

Démonstration. Raisonnons par contraposée. Supposons $f$ injective. Le point 1 de la propriété de comparaison donne alors $\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 $f$ n'est pas injective, et la définition de la non-injectivité fournit exactement deux éléments distincts de même image. $\mathrm{\square }$

L'image mentale qui donne son nom au principe est la suivante : si l'on range $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$ chaussettes dans $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$ tiroirs et qu'il y a plus de chaussettes que de tiroirs, alors un tiroir au moins en contient deux. L'énoncé ne dit pas lequel, et c'est là toute sa force : il donne une existence sans aucune construction.

Démonstration. Les ensembles $f^{-1}(\{y\})$, pour $y$ parcourant $F$, sont deux à deux disjoints : un élément $x$ de $E$ appartient à $f^{-1}(\{y\})$ pour la seule valeur $y=f(x)$. Leur réunion est $E$ tout entier, puisque tout $x\in E$ appartient à $f^{-1}(\{f(x)\})$. La formule de dénombrement d'une réunion de parties deux à deux disjointes, établie à la section suivante, donne donc

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=\sum _{y\in F}\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f^{-1}(\{y\}))\mathrm{.}$$

Raisonnons par l'absurde : si l'on avait $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f^{-1}(\{y\}))⩽k$ pour tout $y\in F$, la somme ci-dessus, qui comporte $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$ termes, serait majorée par $k\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$, d'où $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)⩽k\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$, en contradiction avec l'hypothèse. Il existe donc $y\in F$ tel que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(f^{-1}(\{y\}))⩾k+1$. $\mathrm{\square }$

Un mot sur l'usage des bijections

Opérations sur les cardinaux

Réunion de parties disjointes

Démonstration. Posons $p=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)$ et $q=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)$, et donnons-nous deux bijections $\phi :[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]\to A$ et $\psi :[\text{\hspace{0.17em}⁣}[1,q]\text{\hspace{0.17em}⁣}]\to B$. Définissons $\chi :[\text{\hspace{0.17em}⁣}[1,p+q]\text{\hspace{0.17em}⁣}]\to A\cup B$ par

$$\chi (i)=\{\begin{array}{ll}\phi (i)& \text{si }1⩽i⩽p,\\ \psi (i-p)& \text{si }p+1⩽i⩽p+q\mathrm{.}\end{array}$$

L'application est bien définie : pour $p+1⩽i⩽p+q$, on a $1⩽i-p⩽q$, donc $\psi (i-p)$ a un sens.

Surjectivité. Soit $z\in A\cup B$. Si $z\in A$, il existe $i\in [\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ avec $z=\phi (i)=\chi (i)$. Si $z\in B$, il existe $j\in [\text{\hspace{0.17em}⁣}[1,q]\text{\hspace{0.17em}⁣}]$ avec $z=\psi (j)=\chi (j+p)$, et $j+p\in [\text{\hspace{0.17em}⁣}[p+1,p+q]\text{\hspace{0.17em}⁣}]$. Dans les deux cas, $z$ est atteint.

Injectivité. Soient $i$ et $i^{\mathrm{\prime }}$ dans $[\text{\hspace{0.17em}⁣}[1,p+q]\text{\hspace{0.17em}⁣}]$ tels que $\chi (i)=\chi (i^{\mathrm{\prime }})$. Si $i$ et $i^{\mathrm{\prime }}$ sont tous deux dans $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$, alors $\phi (i)=\phi (i^{\mathrm{\prime }})$ et l'injectivité de $\phi$ donne $i=i^{\mathrm{\prime }}$. S'ils sont tous deux dans $[\text{\hspace{0.17em}⁣}[p+1,p+q]\text{\hspace{0.17em}⁣}]$, l'injectivité de $\psi$ donne $i-p=i^{\mathrm{\prime }}-p$, donc $i=i^{\mathrm{\prime }}$. Reste le cas mixte : si $i⩽p<i^{\mathrm{\prime }}$, alors $\chi (i)\in A$ et $\chi (i^{\mathrm{\prime }})\in B$, or $A\cap B=\mathrm{\varnothing }$, donc $\chi (i)\mathrm{\ne }\chi (i^{\mathrm{\prime }})$, ce qui contredit l'hypothèse. Ce cas ne se produit donc pas.

Ainsi $\chi$ est une bijection de $[\text{\hspace{0.17em}⁣}[1,p+q]\text{\hspace{0.17em}⁣}]$ sur $A\cup B$, qui est donc fini de cardinal $p+q$. $\mathrm{\square }$

Démonstration. Par récurrence sur $m⩾1$. Pour $m=1$, l'égalité est immédiate. Supposons-la vraie au rang $m$ et donnons-nous $A_1,\dots ,A_{m+1}$ deux à deux disjoints. Posons $U=A_1\cup \cdots \cup A_m$. Les ensembles $U$ et $A_{m+1}$ sont disjoints : si $z\in U\cap A_{m+1}$, alors $z$ appartient à un certain $A_i$ avec $i⩽m$, et à $A_{m+1}$, donc $z\in A_i\cap A_{m+1}=\mathrm{\varnothing }$, ce qui est absurde. La propriété précédente puis l'hypothèse de récurrence donnent

$$\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 }$

En pratique, on applique la formule précédente à des parties deux à deux disjointes recouvrant $E$, sans se soucier de savoir si l'une d'elles est vide : une partie vide contribue pour $0$ à la somme et ne fausse donc rien. C'est la raison pour laquelle on parle souvent, par abus commode, de « partitionner selon un critère », même quand certains cas ne se produisent pas.

Démonstration. Point 1. Les parties $A$ et $\bar{A}$ sont disjointes, car un élément de $\bar{A}$ n'appartient pas à $A$, et leur réunion vaut $E$ : tout élément de $E$ appartient à $A$ ou n'y appartient pas. La formule de la réunion disjointe 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}(\bar{A})$, d'où le résultat en soustrayant.

Point 2. Les parties $A\cap B$ et $A\setminus B$ sont disjointes : un élément de $A\setminus B$ n'est pas dans $B$, donc pas dans $A\cap B$. Leur réunion vaut $A$ : un élément de $A$ est dans $B$ ou n'y est pas. Donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B)+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\setminus B)$, d'où la formule. Si $B\subset A$, alors $A\cap B=B$ et l'on obtient le cas particulier. $\mathrm{\square }$

Réunion de deux ensembles quelconques

Démonstration. Écrivons $A\cup B$ comme une réunion disjointe : $A\cup B=A\cup (B\setminus A)$. Ces deux parties sont bien disjointes, car un élément de $B\setminus A$ n'appartient pas à $A$, et leur réunion est bien $A\cup B$, car tout élément de $B$ est soit dans $A$, soit dans $B\setminus A$. La formule de la réunion disjointe donne

$$\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)\mathrm{.}$$

Or, d'après le point 2 de la propriété précédente appliqué à $B$ et $A$, on a $\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}(B\cap A)$. En reportant, et puisque $B\cap A=A\cap B$,

$$\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 }$$

L'interprétation est limpide : en ajoutant $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)$, on compte deux fois les éléments communs, il faut donc en retrancher une fois le nombre.

Produit cartésien

Démonstration. Si $A$ est vide, $A\times B$ est vide et les deux membres valent $0$. Supposons donc $A$ non vide et écrivons $A=\{a_1,\dots ,a_p\}$ avec $p=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)$ et les $a_i$ deux à deux distincts. Pour $i\in [\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$, posons

$$P_i=\{a_i\}\times B=\{(a_i,b);b\in B\}\mathrm{.}$$

Ces parties sont deux à deux disjointes : un couple appartenant à $P_i$ et à $P_j$ aurait pour première composante à la fois $a_i$ et $a_j$, ce qui impose $i=j$. Leur réunion est $A\times B$ : tout couple $(a,b)$ de $A\times B$ a sa première composante égale à un certain $a_i$, donc appartient à $P_i$. Enfin, pour $i$ fixé, l'application $b⟼(a_i,b)$ est une bijection de $B$ sur $P_i$ : elle est surjective par définition de $P_i$, et injective car deux couples de même première composante sont égaux si et seulement si leurs secondes composantes le sont. Donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(P_i)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)$. La formule de la réunion disjointe donne alors

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\times B)=\sum _{i=1}^p\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(P_i)=\sum _{i=1}^p\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)=p\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)\mathrm{.}\mathrm{\square }$$

Démonstration. Récurrence sur $p⩾1$. Le cas $p=1$ est trivial. Supposons le résultat acquis au rang $p$. En identifiant un $(p+1)$-uplet $(x_1,\dots ,x_{p+1})$ avec le couple $((x_1,\dots ,x_p),x_{p+1})$, ce qui est une simple réécriture, on obtient

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A_1\times \cdots \times A_{p+1})=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}((A_1\times \cdots \times A_p)\times A_{p+1})=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A_1\times \cdots \times A_p)\times \mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A_{p+1}),$$

en appliquant le cas de deux ensembles. L'hypothèse de récurrence conclut. Pour le cas particulier, on prend $A_i=E$ pour tout $i$, et le produit vaut $n^p$. Pour $p=0$, la convention selon laquelle $E^0$ est réduit à un unique élément (le $0$-uplet vide) est cohérente avec $n^0=1$. $\mathrm{\square }$

Le principe multiplicatif

Le produit cartésien fournit le principe le plus utilisé de tout le chapitre. Il mérite d'être énoncé sous la forme où on l'emploie réellement, celle des choix successifs.

Disjonction de cas et passage au complémentaire

Nombre d'applications, nombre de parties

Applications d'un ensemble fini dans un autre

Démonstration. Première rédaction, par choix successifs. Supposons $E$ non vide et écrivons $E=\{x_1,\dots ,x_p\}$, les $x_i$ étant deux à deux distincts. Se donner une application $f:E\to F$, c'est se donner l'image de chacun des $p$ éléments de $E$, et rien d'autre : deux applications qui coïncident en chaque $x_i$ sont égales, et tout choix d'images définit bien une application. On effectue donc $p$ choix successifs : $f(x_1)$ dans $F$, soit $q$ possibilités, puis $f(x_2)$ dans $F$, soit encore $q$ possibilités quel que soit le choix précédent, et ainsi de suite jusqu'à $f(x_p)$. Le principe multiplicatif donne $q\times q\times \cdots \times q=q^p$.

Deuxième rédaction, par récurrence sur $p$. Pour $p=0$, c'est-à-dire $E=\mathrm{\varnothing }$, il existe exactement une application de $\mathrm{\varnothing }$ dans $F$, l'application vide, et $q^0=1$ : la formule est vraie. Supposons-la vraie pour tout ensemble de cardinal $p$, et soit $E$ de cardinal $p+1$. Fixons $a\in E$ et posons $E^{\mathrm{\prime }}=E\setminus \{a\}$, de cardinal $p$. L'application

$$\mathrm{\Phi }:\mathcal{F}(E,F)⟶\mathcal{F}(E^{\mathrm{\prime }},F)\times F,f⟼(f_{\mathrm{\mid }{E}^{\mathrm{\prime }}},f(a))$$

est une bijection : à partir d'un couple $(g,y)$, on reconstruit une unique application $f$ de $E$ dans $F$ en posant $f(x)=g(x)$ pour $x\in E^{\mathrm{\prime }}$ et $f(a)=y$. Donc, par l'hypothèse de récurrence et le cardinal d'un produit,

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{F}(E,F))=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{F}(E^{\mathrm{\prime }},F))\times \mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)=q^p\times q=q^{p+1},$$

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

Le nombre de parties d'un ensemble fini

Première démonstration, par les fonctions indicatrices. Rappelons que pour $A\subset E$, la fonction indicatrice ${\mathbf{1}}_A:E\to \{0,1\}$ est définie par ${\mathbf{1}}_A(x)=1$ si $x\in A$ et ${\mathbf{1}}_A(x)=0$ sinon. Considérons l'application

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

Montrons que $\mathrm{\Theta }$ est bijective en exhibant sa réciproque. À une application $f:E\to \{0,1\}$, associons la partie $\mathrm{\Lambda }(f)=f^{-1}(\{1\})=\{x\in E;f(x)=1\}$.

D'une part, pour toute partie $A$, on a $\mathrm{\Lambda }(\mathrm{\Theta }(A))=\{x\in E;{\mathbf{1}}_A(x)=1\}=A$, par définition même de l'indicatrice. D'autre part, pour toute application $f:E\to \{0,1\}$ et tout $x\in E$, on a ${\mathbf{1}}_{\mathrm{\Lambda }(f)}(x)=1$ si et seulement si $x\in \mathrm{\Lambda }(f)$, c'est-à-dire si et seulement si $f(x)=1$ ; comme $f$ ne prend que les valeurs $0$ et $1$, cela signifie exactement ${\mathbf{1}}_{\mathrm{\Lambda }(f)}(x)=f(x)$. Donc $\mathrm{\Theta }(\mathrm{\Lambda }(f))=f$. Les deux composées valent l'identité, donc $\mathrm{\Theta }$ est bijective, et

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

d'après la propriété précédente. $\mathrm{\square }$

Seconde démonstration, par récurrence sur $n$. Montrons par récurrence sur $n\in \mathbb{N}$ l'assertion : « tout ensemble de cardinal $n$ possède exactement $2^n$ parties ».

Initialisation. Si $n=0$, alors $E=\mathrm{\varnothing }$ et $\mathcal{P}(\mathrm{\varnothing })=\{\mathrm{\varnothing }\}$ : il y a une seule partie, et $2^0=1$.

Hérédité. Supposons l'assertion vraie au rang $n$ et soit $E$ de cardinal $n+1$. Fixons $a\in E$ et posons $E^{\mathrm{\prime }}=E\setminus \{a\}$, de cardinal $n$. Découpons $\mathcal{P}(E)$ selon que la partie contient ou non l'élément $a$ :

$$\mathcal{U}=\{A\in \mathcal{P}(E);a\mathrm{\notin }A\},\mathcal{V}=\{A\in \mathcal{P}(E);a\in A\}\mathrm{.}$$

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

Les éléments de $\mathcal{U}$ sont exactement les parties de $E^{\mathrm{\prime }}$, donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{U})=2^n$ par hypothèse de récurrence. Quant à $\mathcal{V}$, l'application $A⟼A\setminus \{a\}$ envoie $\mathcal{V}$ dans $\mathcal{P}(E^{\mathrm{\prime }})$, et l'application $B⟼B\cup \{a\}$ envoie $\mathcal{P}(E^{\mathrm{\prime }})$ dans $\mathcal{V}$ ; ces deux applications sont réciproques l'une de l'autre, car pour $A\in \mathcal{V}$ on a $(A\setminus \{a\})\cup \{a\}=A$ puisque $a\in A$, et pour $B\subset E^{\mathrm{\prime }}$ on a $(B\cup \{a\})\setminus \{a\}=B$ puisque $a\mathrm{\notin }B$. Donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{V})=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{P}(E^{\mathrm{\prime }}))=2^n$.

Finalement $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{P}(E))=2^n+2^n=2^{n+1}$, ce qui achève la récurrence. $\mathrm{\square }$

Listes, arrangements, permutations

Les $p$-listes

Une $p$-liste s'identifie à une application de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ dans $E$ : à la liste $(x_1,\dots ,x_p)$ correspond l'application $i⟼x_i$, et réciproquement. Deux listes sont égales si et seulement si elles ont les mêmes composantes dans le même ordre : $(1,2)\mathrm{\ne }(2,1)$, alors que $\{1,2\}=\{2,1\}$. C'est là toute la différence entre une liste et une partie.

Démonstration. C'est le cardinal de $E^p$, calculé à la section précédente ; c'est aussi, via l'identification ci-dessus, le cardinal de $\mathcal{F}([\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}],E)$, qui vaut $n^p$. $\mathrm{\square }$

$p$-listes d'éléments distincts et injections

Démonstration. Cas $p>n$. Une $p$-liste d'éléments distincts de $E$ définit une application injective de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ dans $E$. S'il en existait une, la comparaison des cardinaux donnerait $p⩽n$, ce qui contredit $p>n$. Il n'y en a donc aucune : $A_n^p=0$.

Cas $p⩽n$, par choix successifs. Construisons une telle liste. On choisit $x_1$ dans $E$ : il y a $n$ possibilités. Puis $x_2$ dans $E\setminus \{x_1\}$ : il y a $n-1$ possibilités, et ce nombre ne dépend pas de la valeur choisie pour $x_1$, seul l'ensemble dans lequel on puise change. Puis $x_3$ dans $E\setminus \{x_1,x_2\}$ : il y a $n-2$ possibilités, à nouveau indépendamment des choix antérieurs, car $x_1$ et $x_2$ sont distincts et l'on retire donc exactement deux éléments. En poursuivant, au $k$-ième choix on dispose de $n-(k-1)$ possibilités, et le dernier choix, celui de $x_p$, en offre $n-p+1$. La description est fidèle : toute suite de choix licites fournit une $p$-liste d'éléments distincts, toute telle liste s'obtient ainsi, et deux suites de choix distinctes donnent deux listes distinctes puisque les listes sont ordonnées. Le principe multiplicatif donne

$$A_n^p=n(n-1)\cdots (n-p+1)\mathrm{.}$$

En multipliant et divisant par $(n-p)!$, on reconnaît

$$A_n^p=\frac{n(n-1)\cdots (n-p+1)\times (n-p)(n-p-1)\cdots 1}{(n-p)!}=\frac{n!}{(n-p)!}\mathrm{.}$$

Le cas des injections. Soit $X$ un ensemble de cardinal $p$, que l'on énumère $X=\{u_1,\dots ,u_p\}$. Une application $f:X\to E$ est déterminée par la liste $(f(u_1),\dots ,f(u_p))$ de ses valeurs, et elle est injective si et seulement si cette liste est formée d'éléments deux à deux distincts. Les applications injectives de $X$ dans $E$ correspondent donc exactement aux $p$-listes d'éléments distincts de $E$, et il y en a $A_n^p$. $\mathrm{\square }$

Permutations et factorielle

La convention $0!=1$ n'est pas une coquetterie : c'est elle qui rend la relation $(n+1)!=(n+1)n!$ valable dès $n=0$, et qui permet d'écrire $A_n^n=\frac{n!}{0!}=n!$ sans cas particulier. Voici les premières valeurs, à connaître au moins jusqu'à $6!$.

La croissance est spectaculaire : $8!=40320$, $10!=3628800$ et $12!=479001600$. Une factorielle écrase toute puissance : c'est pourquoi un dénombrement qui aboutit à $n!$ produit très vite des nombres gigantesques.

Démonstration. Une permutation de $E$ est une bijection de $E$ sur $E$ ; en particulier, c'est une application injective de $E$ dans $E$. Réciproquement, comme $E$ et $E$ ont évidemment même cardinal, le théorème fondamental de la section 2 affirme que toute application injective de $E$ dans $E$ est bijective. Les permutations de $E$ sont donc exactement les applications injectives de $E$ dans $E$, et il y en a, d'après la propriété précédente appliquée avec $p=n$,

$$A_n^n=\frac{n!}{(n-n)!}=\frac{n!}{0!}=n!\mathrm{.}\mathrm{\square }$$

Les quatre modèles

Combinaisons et coefficients binomiaux

Définition et premières valeurs

Cette définition demande deux justifications. D'abord, le nombre en question est bien fini : les parties à $p$ éléments de $E$ forment une partie de $\mathcal{P}(E)$, qui est fini de cardinal $2^n$. Ensuite, ce nombre ne dépend que de $n$, et non de l'ensemble $E$ choisi : si $E$ et $E^{\mathrm{\prime }}$ ont même cardinal, une bijection de $E$ sur $E^{\mathrm{\prime }}$ transforme les parties à $p$ éléments de l'un en les parties à $p$ éléments de l'autre, sans en oublier ni en confondre. La notation $\left(\genfrac{}{}{0px}{}{n}{p}\right)$, qui ne mentionne pas $E$, est donc légitime. Dans toute la suite, on note ${\mathcal{P}}_p(E)$ l'ensemble des parties à $p$ éléments de $E$, de sorte que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{P}}_p(E))=\left(\genfrac{}{}{0px}{}{n}{p}\right)$.

Démonstration. Les points 1, 2 et 4 sont des reformulations directes de résultats déjà établis : l'unique partie de cardinal $0$ est $\mathrm{\varnothing }$ car un ensemble fini de cardinal nul est vide ; une partie $A$ de $E$ telle que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)$ vaut $E$ d'après le point 3 de la propriété sur les parties ; enfin toute partie de $E$ vérifie $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)⩽n$, ce qui interdit $p>n$, et un cardinal est un entier naturel, ce qui interdit $p<0$. Pour le point 3, l'application $x⟼\{x\}$ de $E$ dans ${\mathcal{P}}_1(E)$ est surjective, car toute partie à un élément s'écrit ainsi, et injective, car $\{x\}=\{y\}$ entraîne $x=y$. Donc $\left(\genfrac{}{}{0px}{}{n}{1}\right)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=n$. $\mathrm{\square }$

Dans toute la suite, sauf mention contraire, on considère $0⩽p⩽n$. La convention $\left(\genfrac{}{}{0px}{}{n}{p}\right)=0$ en dehors de cet intervalle a l'avantage de rendre les formules valables sans restriction, ce qui évite de multiplier les cas particuliers.

La formule explicite, par double comptage

Démonstration, par double comptage. Soit $E$ un ensemble de cardinal $n$ et soit $L$ l'ensemble des $p$-listes d'éléments deux à deux distincts de $E$. Nous allons calculer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(L)$ de deux manières.

Premier comptage. D'après la section précédente, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(L)=A_n^p$.

Second comptage. À toute liste $\mathrm{\ell }=(x_1,\dots ,x_p)\in L$, associons l'ensemble de ses composantes

$$S(\mathrm{\ell })=\{x_1,x_2,\dots ,x_p\}\mathrm{.}$$

Comme les $x_i$ sont deux à deux distincts, $S(\mathrm{\ell })$ est une partie de $E$ à exactement $p$ éléments, c'est-à-dire un élément de ${\mathcal{P}}_p(E)$. Pour $A\in {\mathcal{P}}_p(E)$, posons

$$L_A=\{\mathrm{\ell }\in L;S(\mathrm{\ell })=A\}\mathrm{.}$$

Les ensembles $L_A$, pour $A$ parcourant ${\mathcal{P}}_p(E)$, sont deux à deux disjoints (une liste $\mathrm{\ell }$ n'appartient qu'au seul $L_A$ avec $A=S(\mathrm{\ell })$) et leur réunion est $L$ tout entier (toute liste $\mathrm{\ell }$ appartient à $L_{S(\mathrm{\ell })}$). Le dénombrement d'une réunion de parties deux à deux disjointes donne donc

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(L)=\sum _{A\in {\mathcal{P}}_p(E)}\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(L_A)\mathrm{.}$$

Calcul de $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(L_A)$. Fixons $A\in {\mathcal{P}}_p(E)$. Une liste $\mathrm{\ell }$ appartient à $L_A$ si et seulement si ses composantes sont deux à deux distinctes et si l'ensemble de ses composantes est exactement $A$. Or une $p$-liste d'éléments deux à deux distincts de $A$ a nécessairement pour ensemble de composantes une partie de $A$ à $p$ éléments, donc $A$ tout entier puisque $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=p$. Ainsi $L_A$ est exactement l'ensemble des $p$-listes d'éléments distincts de $A$, et

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(L_A)=A_p^p=p!\mathrm{.}$$

Ce nombre ne dépend pas de $A$ : la somme comporte $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{P}}_p(E))=\left(\genfrac{}{}{0px}{}{n}{p}\right)$ termes tous égaux à $p!$, d'où

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

Conclusion. En égalant les deux comptages, $A_n^p=\left(\genfrac{}{}{0px}{}{n}{p}\right)p!$, et comme $p!\mathrm{\ne }0$,

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

Symétrie

Démonstration combinatoire, par passage au complémentaire. Soit $E$ un ensemble de cardinal $n$. Choisir une partie $A$ à $p$ éléments de $E$, c'est exactement choisir les $n-p$ éléments que l'on laisse de côté, c'est-à-dire la partie $\bar{A}$, qui a $n-p$ éléments d'après la formule du complémentaire. Formellement, l'application $A⟼\bar{A}$ envoie ${\mathcal{P}}_p(E)$ dans ${\mathcal{P}}_{n-p}(E)$, et elle est sa propre réciproque puisque $\overline{\stackrel{‾}{A}}=A$. C'est donc une bijection, et les deux ensembles ont même cardinal, ce qui est l'égalité annoncée.

Vérification par le calcul. En appliquant la formule explicite avec $n-p$ à la place de $p$, et en notant que $n-(n-p)=p$,

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

La formule de Pascal et le triangle

Démonstration combinatoire. Soit $E$ un ensemble de cardinal $n⩾1$ et fixons un élément $a\in E$. Posons $E^{\mathrm{\prime }}=E\setminus \{a\}$, de cardinal $n-1$. Découpons l'ensemble ${\mathcal{P}}_p(E)$ des parties à $p$ éléments de $E$ selon que la partie contient ou non l'élément $a$ :

$$\mathcal{U}=\{A\in {\mathcal{P}}_p(E);a\mathrm{\notin }A\},\mathcal{V}=\{A\in {\mathcal{P}}_p(E);a\in A\}\mathrm{.}$$

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

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

Les parties qui ne contiennent pas $a$. Une partie $A$ de $E$ à $p$ éléments ne contenant pas $a$ est exactement une partie de $E^{\mathrm{\prime }}$ à $p$ éléments. Donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{U})=\left(\genfrac{}{}{0px}{}{n-1}{p}\right)$.

Les parties qui contiennent $a$. Une partie $A$ de $E$ à $p$ éléments contenant $a$ s'obtient en adjoignant $a$ à la partie $A\setminus \{a\}$, qui est une partie de $E^{\mathrm{\prime }}$ à $p-1$ éléments. Réciproquement, si $B$ est une partie de $E^{\mathrm{\prime }}$ à $p-1$ éléments, alors $B\cup \{a\}$ est une partie de $E$ à $p$ éléments contenant $a$, car $a\mathrm{\notin }B$. Ces deux correspondances sont réciproques l'une de l'autre, donc $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{V})=\left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)$.

En additionnant, on obtient exactement la formule annoncée.

Vérification par le calcul. Pour $1⩽p⩽n-1$, réduisons au même dénominateur :

$$\begin{array}{rl}{\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)+\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{(n-1)!p}{p!(n-p)!}+\frac{(n-1)!(n-p)}{p!(n-p)!}}\\ {\displaystyle }& {\displaystyle =\frac{(n-1)!(p+n-p)}{p!(n-p)!}}\\ {\displaystyle }& {\displaystyle =\frac{n!}{p!(n-p)!}=\left(\genfrac{}{}{0px}{}{n}{p}\right),}\end{array}$$

où l'on a multiplié le premier terme par $\frac{p}{p}$ et le second par $\frac{n-p}{n-p}$ pour obtenir le dénominateur commun $p!(n-p)!$. $\mathrm{\square }$

La formule de Pascal permet de calculer tous les coefficients binomiaux de proche en proche, sans aucune factorielle : chaque coefficient est la somme des deux coefficients situés juste au-dessus de lui, à gauche et à droite. C'est le triangle de Pascal, présenté ici en deux tableaux pour tenir dans la largeur.

La formule du pivot

Démonstration combinatoire, par double comptage. Soit $E$ un ensemble de cardinal $n$. Comptons de deux façons les éléments de l'ensemble

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

c'est-à-dire les couples formés d'une partie à $p$ éléments et d'un élément distingué à l'intérieur de cette partie. On peut penser à un comité de $p$ personnes choisi parmi $n$, dans lequel on désigne un président.

Premier comptage, en choisissant d'abord la partie. Découpons $\mathcal{C}$ selon la première composante $A$. Pour $A\in {\mathcal{P}}_p(E)$ fixée, les couples de $\mathcal{C}$ de première composante $A$ sont les $(A,x)$ avec $x\in A$ : il y en a $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=p$. Ces morceaux sont deux à deux disjoints et recouvrent $\mathcal{C}$, donc

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{C})=\sum _{A\in {\mathcal{P}}_p(E)}p=\left(\genfrac{}{}{0px}{}{n}{p}\right)\times p\mathrm{.}$$

Second comptage, en choisissant d'abord l'élément distingué. Découpons maintenant $\mathcal{C}$ selon la seconde composante $x$. Pour $x\in E$ fixé, les couples de $\mathcal{C}$ de seconde composante $x$ sont les $(A,x)$ où $A$ est une partie à $p$ éléments contenant $x$. Comme dans la démonstration de la formule de Pascal, une telle partie s'écrit de manière unique $A=B\cup \{x\}$ avec $B$ partie à $p-1$ éléments de $E\setminus \{x\}$, ensemble de cardinal $n-1$ : il y en a donc $\left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)$. Ces morceaux sont deux à deux disjoints et recouvrent $\mathcal{C}$, donc

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{C})=\sum _{x\in E}\left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)=n\times \left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)\mathrm{.}$$

En égalant les deux comptages, $p\left(\genfrac{}{}{0px}{}{n}{p}\right)=n\left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)$.

Vérification par le calcul. Pour $1⩽p⩽n$,

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

puisque $p!=p\times (p-1)!$, et par ailleurs

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

Les deux expressions coïncident. $\mathrm{\square }$

La formule du binôme, par voie combinatoire

Démonstration combinatoire. Le cas $n=0$ est immédiat : les deux membres valent $1$. Supposons $n⩾1$ et écrivons le produit en numérotant ses facteurs :

$$(a+b{)}^n=\underset{\text{facteur }1}{\underbrace{(a+b)}}\times \underset{\text{facteur }2}{\underbrace{(a+b)}}\times \cdots \times \underset{\text{facteur }n}{\underbrace{(a+b)}}\mathrm{.}$$

Développer ce produit par distributivité consiste à choisir, dans chacun des $n$ facteurs, l'un des deux termes $a$ ou $b$, à multiplier les $n$ termes choisis, puis à sommer sur toutes les manières de choisir. C'est exactement la règle de développement d'un produit de sommes, appliquée $n$ fois.

Une manière de choisir est entièrement décrite par l'ensemble

$$K=\{i\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}];\text{on a choisi }a\text{ dans le facteur }i\},$$

qui est une partie quelconque de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ ; les facteurs d'indice hors de $K$ fournissent alors $b$. Réciproquement, toute partie $K$ de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ décrit une et une seule manière de choisir. Le produit correspondant comporte $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(K)$ facteurs égaux à $a$ et $n-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(K)$ facteurs égaux à $b$ ; comme la multiplication des nombres est commutative, ce produit vaut $a^{\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(K)}{b}^{n-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(K)}$. Ainsi

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

Regroupons maintenant les termes de cette somme selon le cardinal de $K$, c'est-à-dire découpons $\mathcal{P}([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}])$ en les ${\mathcal{P}}_k([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}])$ pour $k\in [\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$ : ces parties sont deux à deux disjointes (une partie a un seul cardinal) et leur réunion est $\mathcal{P}([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}])$ tout entier. Tous les termes correspondant à un même $k$ sont égaux à $a^k{b}^{n-k}$, et il y en a $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{P}}_k([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]))=\left(\genfrac{}{}{0px}{}{n}{k}\right)$. D'où

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

Conséquences du binôme

Démonstration. La première identité s'obtient en appliquant la formule du binôme avec $a=b=1$ : le membre de gauche devient $(1+1{)}^n=2^n$, et le membre de droite ${\sum }_k\left(\genfrac{}{}{0px}{}{n}{k}\right)1^k{1}^{n-k}={\sum }_k\left(\genfrac{}{}{0px}{}{n}{k}\right)$.

La seconde s'obtient avec $a=-1$ et $b=1$ : le membre de gauche devient $(-1+1{)}^n=0^n=0$, puisque $n⩾1$, et le membre de droite ${\sum }_k\left(\genfrac{}{}{0px}{}{n}{k}\right)(-1{)}^k{1}^{n-k}={\sum }_k(-1{)}^k\left(\genfrac{}{}{0px}{}{n}{k}\right)$. $\mathrm{\square }$

Démonstration. Découpons $\mathcal{P}(E)$ selon le cardinal des parties : les ensembles ${\mathcal{P}}_0(E),{\mathcal{P}}_1(E),\dots ,{\mathcal{P}}_n(E)$ sont deux à deux disjoints, puisqu'une partie a un cardinal et un seul, et leur réunion est $\mathcal{P}(E)$, puisque toute partie de $E$ a un cardinal compris entre $0$ et $n$. D'où

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{P}(E))=\sum _{k=0}^n\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{P}}_k(E))=\sum _{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)=2^n,$$

la dernière égalité étant la conséquence du binôme établie à l'instant. $\mathrm{\square }$

Démonstration. Notons $P$ le nombre de parties de $E$ de cardinal pair et $I$ celui des parties de cardinal impair. En découpant $\mathcal{P}(E)$ selon le cardinal comme ci-dessus, puis en séparant les indices pairs des indices impairs,

$$P=\sum _{\begin{array}{c}0⩽k⩽n\\ k\text{ pair}\end{array}}\left(\genfrac{}{}{0px}{}{n}{k}\right),I=\sum _{\begin{array}{c}0⩽k⩽n\\ k\text{ impair}\end{array}}\left(\genfrac{}{}{0px}{}{n}{k}\right)\mathrm{.}$$

La première conséquence du binôme donne $P+I=2^n$. La seconde s'écrit

$$0=\sum _{k=0}^n(-1{)}^k\left(\genfrac{}{}{0px}{}{n}{k}\right)=\sum _{k\text{ pair}}\left(\genfrac{}{}{0px}{}{n}{k}\right)-\sum _{k\text{ impair}}\left(\genfrac{}{}{0px}{}{n}{k}\right)=P-I,$$

car $(-1{)}^k$ vaut $1$ si $k$ est pair et $-1$ sinon. Le système formé de $P+I=2^n$ et $P-I=0$ donne $P=I=2^{n-1}$. $\mathrm{\square }$

Méthodes de dénombrement

Choisir le modèle : quatre questions

Dénombrer par choix successifs, contrainte d'abord

Disjonction de cas et complémentaire, en pratique

Le double comptage

Anagrammes

Chemins dans un quadrillage

Le tableau des réflexes

Pour finir cette section méthodologique, voici les réflexes du chapitre, à faire défiler mentalement devant tout énoncé de dénombrement.

Exemples traités et erreurs classiques