Quatre identités de plus, toutes comptées

La sortie de l’Atelier promettait « quelques identités de plus ». Les voici, au nombre de quatre, choisies pour ne recouper ni l’Atelier ni le DM : chacune est démontrée par dénombrement, c’est-à-dire en comptant deux fois la même chose, sans jamais invoquer de formule algébrique extérieure au chapitre. Toutes les valeurs numériques de cette page ont été vérifiées par script (énumération brute comprise).

1. Le crible à trois ensembles, une seconde preuve

La formule du crible à trois ensembles, son histoire et sa démonstration par associativité ont leur propre page sur ce compagnon (« Le crible à trois ensembles ») ; en voici une seconde démonstration, d’un tout autre style, qui compte les contributions élément par élément. Deux preuves d’un même théorème valent mieux qu’une : chacune éclaire ce que l’autre laisse dans l’ombre.

Théorème. Pour tous ensembles finis $A$, $B$, $C$ :

$$\operatorname{Card}(A \cup B \cup C) = \operatorname{Card}(A) + \operatorname{Card}(B) + \operatorname{Card}(C) - \operatorname{Card}(A \cap B) - \operatorname{Card}(A \cap C) - \operatorname{Card}(B \cap C) + \operatorname{Card}(A \cap B \cap C).$$

Démonstration (par comptage des contributions). Chaque cardinal du membre de droite est une somme de $1$, un par élément de l’ensemble concerné. Fixons un élément $x$ de $A \cup B \cup C$ et comptons sa contribution totale au membre de droite, selon le nombre $p$ d’ensembles parmi $A$, $B$, $C$ auxquels il appartient ($p$ vaut $1$, $2$ ou $3$).

• Si $p = 1$ : l’élément $x$ est compté une fois dans les trois premiers termes, jamais ailleurs. Contribution : $1$.
• Si $p = 2$ : il est compté deux fois dans les trois premiers termes, retiré une fois (il appartient à exactement une des trois intersections doubles), jamais dans la triple. Contribution : $2 - 1 = 1$.
• Si $p = 3$ : compté trois fois, retiré trois fois, rajouté une fois. Contribution : $3 - 3 + 1 = 1$.

Tout élément de $A \cup B \cup C$ contribue donc pour exactement $1$, et un élément qui n’est dans aucun des trois ensembles contribue pour $0$ : le membre de droite vaut $\operatorname{Card}(A \cup B \cup C)$. $\blacksquare$

Exemple. Combien d’entiers de $1$ à $1000$ sont divisibles par $2$, par $3$ ou par $5$ ? Avec $A$, $B$, $C$ les ensembles des multiples de $2$, de $3$ et de $5$ :

$$500 + 333 + 200 - 166 - 100 - 66 + 33 = 734,$$

les six derniers cardinaux étant ceux des multiples de $6$, $10$, $15$ et $30$. Il reste donc $266$ entiers divisibles par aucun des trois.

Quant au mur sur lequel la question Q15.c) du DM butait exprès (compter les surjections par le complémentaire), c’est précisément ce que le crible débloque : le calcul complet vous attend sur la page « Les surjections passées au crible ».

2. Le comité et son président

Lemme d’absorption. Pour tout entier $n \geqslant 1$ et tout $k \in \{1, \ldots, n\}$ :

$$k \binom{n}{k} = n \binom{n-1}{k-1}.$$

Démonstration. Comptons, dans un groupe de $n$ personnes, les couples (comité à $k$ membres, président membre de ce comité). Premier comptage : choisir le comité ($\binom{n}{k}$ façons), puis son président parmi ses $k$ membres ; total $\binom{n}{k} \times k$. Second comptage : choisir d’abord le président ($n$ façons), puis les $k - 1$ autres membres parmi les $n - 1$ personnes restantes ; total $n \times \binom{n-1}{k-1}$. Les deux procédés énumèrent exactement les mêmes couples, chacun une seule fois. $\blacksquare$

Théorème. Pour tout entier $n \geqslant 1$ :

$$\sum_{k=1}^{n} k \binom{n}{k} = n \, 2^{\,n-1}.$$

Démonstration. Comptons cette fois tous les couples (comité non vide, son président), sans fixer la taille. Premier comptage : classer par taille $k$ du comité ; la classe de taille $k$ contient $k \binom{n}{k}$ couples (lemme ci-dessus, ou premier comptage du lemme), et le principe additif donne la somme du membre de gauche. Second comptage : choisir d’abord le président ($n$ façons), puis décider librement, pour chacune des $n - 1$ autres personnes, si elle entre au comité ; d’après le cours, un ensemble à $n - 1$ éléments possède $2^{\,n-1}$ parties. Total : $n \times 2^{\,n-1}$. $\blacksquare$

Exemple ($n = 4$) : $1 \times 4 + 2 \times 6 + 3 \times 4 + 4 \times 1 = 4 + 12 + 12 + 4 = 32 = 4 \times 2^3$.

3. La classe coupée en deux

Théorème. Pour tout entier $n \geqslant 1$ :

$$\binom{2n}{2} = 2 \binom{n}{2} + n^2.$$

Démonstration. Soit un ensemble de $2n$ élèves, coupé en deux demi-groupes de $n$ élèves chacun. Comptons les paires d’élèves. D’un côté, une paire est une partie à deux éléments d’un ensemble à $2n$ éléments : il y en a $\binom{2n}{2}$. De l’autre, une paire est d’exactement un des trois types suivants : interne au premier demi-groupe ($\binom{n}{2}$ paires), interne au second ($\binom{n}{2}$ paires), ou mixte, auquel cas elle est déterminée par le choix d’un élève dans chaque demi-groupe ($n \times n$ paires, par le principe multiplicatif). Le principe additif conclut. $\blacksquare$

Exemple ($n = 15$) : dans une classe de $30$ élèves coupée en deux demi-groupes de $15$, on compte $\binom{30}{2} = 435$ paires, dont $2 \times 105 = 210$ paires internes et $15^2 = 225$ paires mixtes. Le même geste démontre, pour tous entiers $m \geqslant 1$ et $n \geqslant 1$, la version asymétrique $\binom{m+n}{2} = \binom{m}{2} + \binom{n}{2} + mn$.

4. Le sous-comité

Théorème. Pour tous entiers $n$, $k$, $m$ tels que $0 \leqslant m \leqslant k \leqslant n$ :

$$\binom{n}{k} \binom{k}{m} = \binom{n}{m} \binom{n-m}{k-m}.$$

Démonstration. Dans un groupe de $n$ personnes, comptons les couples $(K, M)$ où $K$ est un comité à $k$ membres et $M$ un sous-comité (un bureau, par exemple) de $m$ membres pris dans $K$. Premier comptage : choisir $K$ ($\binom{n}{k}$ façons), puis $M$ dans $K$ ($\binom{k}{m}$ façons). Second comptage : choisir d’abord le bureau $M$ parmi tout le monde ($\binom{n}{m}$ façons), puis compléter le comité en choisissant les $k - m$ membres restants parmi les $n - m$ personnes hors bureau ($\binom{n-m}{k-m}$ façons). Mêmes couples, comptés une fois chacun des deux côtés. $\blacksquare$

Exemple ($n = 5$, $k = 3$, $m = 2$) : $\binom{5}{3} \binom{3}{2} = 10 \times 3 = 30 = 10 \times 3 = \binom{5}{2} \binom{3}{1}$.

Corollaire. Pour tout entier naturel $n$ et tout $m \in \{0, \ldots, n\}$ :

$$\sum_{k=m}^{n} \binom{n}{k} \binom{k}{m} = \binom{n}{m} \, 2^{\,n-m}.$$

Démonstration. Comptons les couples $(K, M)$ où $M$ est un bureau à $m$ membres et $K$ un comité quelconque le contenant (de taille libre). À gauche : classer par taille $k$ de $K$ ; la classe de taille $k$ contient $\binom{n}{k} \binom{k}{m}$ couples (choisir $K$, puis $M$ dans $K$), et le principe additif somme les classes. À droite : choisir $M$ ($\binom{n}{m}$ façons), puis décider librement de l’appartenance à $K$ de chacune des $n - m$ personnes restantes : $2^{\,n-m}$ possibilités d’après le cours. $\blacksquare$

Exemple ($n = 4$, $m = 2$) : $6 \times 1 + 4 \times 3 + 1 \times 6 = 6 + 12 + 6 = 24 = \binom{4}{2} \times 2^2$.

Dernière élégance : dans ce corollaire, le cas $m = 1$ s’écrit $\sum_{k=1}^{n} \binom{n}{k} \binom{k}{1} = \binom{n}{1} 2^{\,n-1}$, c’est-à-dire exactement l’identité du comité et de son président. Les quatre résultats de cette page reposent sur un unique geste, celui que le chapitre vous a appris : quand une égalité résiste au calcul, cherchez ce qu’elle compte.

Vérifications

• Les quatre identités ont été testées par script (hub_identites_verif.py) : formules confrontées à l’énumération brute (tous les triplets de parties pour le crible, tous les couples comité-président et comité-sous-comité jusqu’à $n = 7$, toutes les paires par demi-groupes jusqu’à $n = 9$), puis aux formules closes jusqu’à $n = 14$ et au-delà.
• Exercice 5 de l’Atelier A2 : le crible à deux ensembles, point de départ de la section 1.
• DM1 du chapitre A2, questions Q15 et Q16 : la valeur $36$ retrouvée ici par le crible y est obtenue par le triangle des $S(n, k)$ puis par le classement selon l’image.