Les surjections passées au crible

La question Q15.c) du DM1 s’achevait sur un constat d’échec assumé : pour dénombrer $\operatorname{Surj}(4, 3)$, retirer de $3^4$ les applications qui évitent $a$, puis celles qui évitent $b$, puis celles qui évitent $c$, retire certaines applications plusieurs fois, et l’énoncé promettait l’outil manquant au compagnon numérique. L’outil est arrivé : c’est le crible, dont l’extra « Le crible à trois ensembles » donne le principe, la démonstration et l’exemple. Cette page reprend le fil exactement où le devoir l’a laissé, et le déroule jusqu’à deux formules que le DM ne pouvait pas atteindre.

Les acquis du devoir

Trois résultats du DM servent de socle ; ils y sont démontrés, nous les citons sans les refaire.

• Le dictionnaire (Q14). Pour tous entiers $n \geqslant k \geqslant 1$, $\operatorname{Surj}(n, k) = k! \times S(n, k)$ : une surjection, c’est une partition en $k$ blocs suivie d’un baptême des blocs.
• Le classement par l’image (Q16). Pour tous entiers $n, k \geqslant 1$, $k^n = \sum_{j=1}^{k} \binom{k}{j} \operatorname{Surj}(n, j)$.
• La table (Q15.a). $\operatorname{Surj}(4, 1) = 1$, $\operatorname{Surj}(4, 2) = 14$, $\operatorname{Surj}(4, 3) = 36$, $\operatorname{Surj}(4, 4) = 24$ : nos valeurs témoins pour tout ce qui suit.

Le crible compte les ratés

Soient $n \geqslant 1$ et $k \geqslant 1$, un ensemble $E$ à $n$ éléments et $F = \{y_1, y_2, \ldots, y_k\}$. Parmi les $k^n$ applications de $E$ vers $F$ (résultat R2 du chapitre), les surjections sont celles qui n’évitent aucun élément de $F$. Comptons donc les ratées. Pour chaque $i \in \llbracket 1\,; k \rrbracket$, notons

$$A_i = \{\, f : E \to F \mid y_i \text{ n'est l'image d'aucun élément de } E \,\}.$$

Une application non surjective est une application qui évite au moins un $y_i$ : l’ensemble des non-surjections est exactement $A_1 \cup A_2 \cup \cdots \cup A_k$. Or ces ensembles se dénombrent sans effort, intersections comprises : une application qui évite $y_{i_1}, \ldots, y_{i_j}$ (avec $i_1 < \cdots < i_j$) n’est rien d’autre qu’une application de $E$ vers l’ensemble $F \setminus \{y_{i_1}, \ldots, y_{i_j}\}$, qui possède $k - j$ éléments. Par R2 :

$$\operatorname{Card}\bigl(A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_j}\bigr) = (k - j)^n.$$

Toutes les intersections de $j$ ensembles ont donc le même cardinal, et il y a $\binom{k}{j}$ façons de choisir les $j$ éléments évités : la situation rêvée pour le crible.

Le cas du DM, réglé sous vos yeux. Reprenons Q15.c) : $n = 4$, $k = 3$, $F = \{a, b, c\}$. Les trois ensembles $A_a$, $A_b$, $A_c$ ont chacun $2^4 = 16$ éléments ; les trois intersections deux à deux en ont $1^4 = 1$ (la seule application évitant $a$ et $b$ est la constante égale à $c$, et ainsi de suite) ; la triple intersection est vide, car une application de $E$ non vide doit bien envoyer ses éléments quelque part : $0^4 = 0$. Le crible à trois ensembles, démontré dans l’extra voisin, donne :

$$\operatorname{Card}(A_a \cup A_b \cup A_c) = 3 \times 16 - 3 \times 1 + 0 = 45,$$

d’où $\operatorname{Surj}(4, 3) = 3^4 - 45 = 81 - 45 = 36$. La valeur de la table est retrouvée, par la méthode même qui échouait sans correctifs : les trois retraits de $16$ comptaient deux fois chacune des trois constantes.

Le cas général. La forme générale du crible (énoncée en vitrine dans l’extra voisin, admise ici) donne, pour tous $n \geqslant 1$ et $k \geqslant 1$ :

$$\operatorname{Card}(A_1 \cup \cdots \cup A_k) = \sum_{j=1}^{k} (-1)^{j+1} \binom{k}{j} (k - j)^n,$$

et par passage au complémentaire dans l’ensemble des $k^n$ applications :

$$\forall n \geqslant 1, \ \forall k \geqslant 1, \qquad \operatorname{Surj}(n, k) = \sum_{j=0}^{k} (-1)^{j} \binom{k}{j} (k - j)^n,$$

le terme $j = 0$ de la somme restituant le $k^n$ initial. Contrôles sur la table du DM : pour $n = 4$ et $k = 2$, la somme vaut $2^4 - 2 \times 1^4 + 0 = 14$ ; pour $n = 4$ et $k = 3$, elle vaut $81 - 48 + 3 - 0 = 36$ ; pour $n = 4$ et $k = 4$, elle vaut $4^4 - 4 \times 3^4 + 6 \times 2^4 - 4 \times 1^4 + 0 = 256 - 324 + 96 - 4 = 24$, soit $4!$, comme il se doit puisqu’une surjection entre deux ensembles de même taille est une bijection. Et lorsque $k > n$, la somme s’annule : aucune surjection d’un petit ensemble sur un plus grand, la formule le sait.

La formule explicite des $S(n, k)$

Il ne reste qu’à traverser le dictionnaire. En divisant par $k!$ l’égalité précédente, le résultat Q14 du DM transforme le décompte de surjections en décompte de partitions :

$$\forall n \geqslant k \geqslant 1, \qquad S(n, k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{j} \binom{k}{j} (k - j)^n.$$

C’est la formule explicite promise par la sortie du DM : plus besoin du triangle, ni de la récurrence, pour atteindre un $S(n, k)$ isolé. Vérifions sur les valeurs que le devoir a fait construire à la main :

$$S(4, 2) = \frac{1}{2}\bigl(2^4 - 2 \times 1^4 + 0\bigr) = \frac{16 - 2}{2} = 7, \qquad S(4, 3) = \frac{1}{6}\bigl(3^4 - 3 \times 2^4 + 3 \times 1^4 - 0\bigr) = \frac{81 - 48 + 3}{6} = \frac{36}{6} = 6.$$

Ce sont bien les valeurs de la ligne $n = 4$ du triangle (question Q6). Notez le petit miracle arithmétique : rien n’annonce que cette somme alternée de grandes puissances soit divisible par $k!$, et pourtant elle l’est toujours, puisqu’elle compte des surjections que le dictionnaire range en paquets de $k!$ exemplaires. Quant à la boucle historique, elle se referme sur l’encadré « Londres, 1730 » du DM : les coefficients de conversion que Stirling tabulait sans compter la moindre partition possèdent donc aussi une formule close, que lui-même n’a jamais écrite.

La fenêtre de Dobiński

Pour finir, une échappée vers le supérieur. Le DM a défini les nombres de Bell par $B_n = \sum_{k=1}^{n} S(n, k)$ ; en 1877, dans une note parue dans l’Archiv der Mathematik und Physik, G. Dobiński établit les premiers cas d’une formule stupéfiante, qui porte depuis son nom :

$$\forall n \geqslant 1, \qquad B_n = \frac{1}{\mathrm{e}} \sum_{k = 0}^{+\infty} \frac{k^n}{k!},$$

où $\mathrm{e} = 2{,}718\ldots$ est la constante que vous fréquenterez toute l’année en analyse. Lisez-la deux fois : une somme infinie de fractions, divisée par un nombre irrationnel, tombe exactement sur un entier, et cet entier compte les partitions. Soyons honnêtes sur son statut : la série infinie et le nombre $\mathrm{e}$ relèvent de l’analyse, pas du dénombrement, et cette formule est hors du chapitre ; nous l’énonçons sans la démontrer. Sa preuve s’obtient en combinant la formule explicite ci-dessus avec le développement en série de $\mathrm{e}$, un outil que la terminale n’aborde pas.

Ce qui est à notre portée, en revanche, c’est de la mettre à l’épreuve numériquement. Pour $n = 5$, en tronquant la somme à ses premiers termes puis en divisant par $\mathrm{e}$ :

Somme arrêtée à	Valeur de $\dfrac{1}{\mathrm{e}} \displaystyle\sum_{k=0}^{K} \dfrac{k^5}{k!}$
$K = 5$	$\approx 46{,}4295$
$K = 10$	$\approx 51{,}9983$
$K = 15$	$52{,}000000$ (à six décimales près)

La série fonce vers $52$, qui est précisément $B_5$, le nombre des cinquante-deux genji-mon. Même épreuve pour $n = 6$ : la somme arrêtée à $K = 25$ donne $203{,}000000$ à six décimales près, et le DM a établi $B_6 = 203$ à la question Q11. Les factorielles du dénominateur écrasent si vite les puissances du numérateur que quelques dizaines de termes suffisent.

Le chapitre s’achève ainsi sur une perspective en enfilade : un jeu d’encens du Japon d’Edo, un triangle, un dictionnaire de surjections, un crible venu de la théorie des nombres, et au bout du couloir une série infinie qui connaît les partitions mieux que quiconque. Le dénombrement s’arrête où commence l’analyse ; la porte, elle, reste ouverte.

Sources

• DM1 du chapitre A2, parties II et IV : dictionnaire $\operatorname{Surj}(n, k) = k! \times S(n, k)$ (Q14), classement par l’image (Q16), table des $\operatorname{Surj}(4, k)$ (Q15.a), échec du décompte naïf (Q15.c), valeurs $B_5 = 52$ (Q7) et $B_6 = 203$ (Q11), encadré « Londres, 1730 » sur la Methodus Differentialis de Stirling.
• Extra « Le crible à trois ensembles » (même chapitre) : démonstration du cas à trois ensembles, énoncé de la forme générale.
• G. Dobiński, note sur la sommation des séries $\sum k^n / k!$, Archiv der Mathematik und Physik (Grunert), 1877.
• Vérifications numériques de cette page (surjections par énumération brute contre formule du crible, valeurs de $S(4, 2)$ et $S(4, 3)$, sommes partielles de Dobiński) : recalculées par machine.