Exercice 15

On note $\mathrm{Surj}(E, F)$ l'ensemble des surjections de $E$ sur $F$. Si $\alpha : E' \to E$ et $\beta : F \to F'$ sont des bijections, l'application $f \mapsto \beta \circ f \circ \alpha$ est une bijection de $\mathrm{Surj}(E, F)$ sur $\mathrm{Surj}(E', F')$ (chapitre 2, proposition 6) : c'est pourquoi $S(n, p)$ ne dépend que des cardinaux, et l'on peut raisonner avec $E = \llbracket 1\,,n \rrbracket$ et $F = \llbracket 1\,,p \rrbracket$.

1. S'il existe une surjection d'un ensemble à $n$ éléments sur un ensemble à $p$ éléments, alors $n \geqslant p$ (chapitre 2, théorème 2). Pour $p = n$, les surjections sont les bijections (proposition 1 (iii)), au nombre de $n!$ (théorème 1). Pour $p = 1$, la seule application est constante, et elle est surjective. Pour $p = 2$, une application de $\llbracket 1\,,n \rrbracket$ dans $\{1, 2\}$ est surjective si et seulement si elle n'est pas constante. $$\boxed{S(n, p) = 0 \text{ si } p > n, \qquad S(n, n) = n!, \qquad S(n, 1) = 1, \qquad S(n, 2) = 2^{n} - 2}$$

2. Soit $f$ une surjection de $\llbracket 1\,,n + 1 \rrbracket$ sur $\llbracket 1\,,n \rrbracket$. Ses $n$ fibres $f^{-1}(\{y\})$ sont non vides, deux à deux disjointes, et recouvrent $\llbracket 1\,,n + 1 \rrbracket$ : leurs cardinaux, tous au moins égaux à $1$, ont pour somme $n + 1$, et exactement une fibre a deux éléments, les autres étant des singletons. On note $P(f)$ cette fibre à deux éléments. Fixons une paire $\{i, j\}$ : les surjections telles que $P(f) = \{i, j\}$ sont celles qui prennent la même valeur en $i$ et en $j$ et des valeurs deux à deux distinctes, différentes de celle-là, aux $n - 1$ autres points. Elles correspondent aux bijections de l'ensemble à $n$ éléments $\big\{\{i, j\}\big\} \cup \big\{\{k\} \mid k \neq i, j\big\}$ sur $\llbracket 1\,,n \rrbracket$ : il y en a $n!$. Le lemme des bergers, appliqué à $f \mapsto P(f)$, donne $$\boxed{S(n + 1, n) = \binom{n + 1}{2}\,n! = \frac{n\,(n + 1)!}{2}}$$ Pour $n = 2$, on trouve $6 = 2^{3} - 2$, en accord avec la question 1 ✓.

3. Soit $n \geqslant 2$, $p \geqslant 2$, et $f$ une surjection de $\llbracket 1\,,n \rrbracket$ sur $\llbracket 1\,,p \rrbracket$ ; on note $g$ sa restriction à $\llbracket 1\,,n - 1 \rrbracket$.

• Si $g$ est surjective sur $\llbracket 1\,,p \rrbracket$, la valeur $f(n)$ est quelconque. Réciproquement, toute surjection $g$ de $\llbracket 1\,,n - 1 \rrbracket$ sur $\llbracket 1\,,p \rrbracket$, prolongée par une valeur quelconque, donne une surjection $f$. Il y a $p\,S(n - 1, p)$ telles surjections $f$ (proposition 2 (iv)).

• Si $g$ n'est pas surjective, elle manque une valeur $y$ ; comme $f$ est surjective, $y$ est atteinte en $n$, donc $y = f(n)$, et $y$ est la seule valeur manquée. Ainsi $g$ est une surjection de $\llbracket 1\,,n - 1 \rrbracket$ sur $\llbracket 1\,,p \rrbracket \setminus \{f(n)\}$. Réciproquement, pour $y \in \llbracket 1\,,p \rrbracket$ et $g$ une surjection de $\llbracket 1\,,n - 1 \rrbracket$ sur cet ensemble à $p - 1$ éléments, le prolongement de $g$ par $f(n) = y$ est une surjection sur $\llbracket 1\,,p \rrbracket$ dont la restriction n'est pas surjective. Il y a $p\,S(n - 1, p - 1)$ telles surjections $f$.

Les deux cas sont disjoints, et la proposition 2 (i) donne $$\boxed{S(n, p) = p\big(S(n - 1, p) + S(n - 1, p - 1)\big) \quad \text{pour } n \geqslant 2 \text{ et } p \geqslant 2}$$

4. Le programme suit la question 3, avec pour cas de base ceux de la question 1.

def S(n, p):              # n >= 1 et p >= 1
    if p > n:
        return 0
    if p == 1:
        return 1
    return p * (S(n - 1, p) + S(n - 1, p - 1))

print(S(5, 3))            # affiche 150

Si un appel $S(n, p)$, avec $n \geqslant 1$ et $p \geqslant 1$, ne s'arrête pas dans l'un des deux tests, c'est que $2 \leqslant p \leqslant n$ : il provoque deux appels avec le premier argument $n - 1 \geqslant 1$ et des seconds arguments $p \geqslant 1$ et $p - 1 \geqslant 1$, de sorte que l'hypothèse $n, p \geqslant 1$ est préservée. Le premier argument diminue de $1$ à chaque appel et reste un entier au moins égal à $1$ : une chaîne d'appels emboîtés a donc au plus $n$ étages, et le programme se termine. Lorsque $n = 1$, on a soit $p > 1$, soit $p = 1$, et l'un des deux tests s'applique. La valeur $S(5, 3) = 150$ est celle que la remarque qui suit la proposition 6 a obtenue par la formule ✓.

5. Notons $R(n, p) = \sum_{k=0}^{p} (-1)^{p-k}\binom{p}{k}k^{n}$, et montrons par récurrence sur $n \geqslant 1$ la propriété : $S(n, p) = R(n, p)$ pour tout $p \geqslant 1$.

Initialisation : Pour $n = 1$, on utilise $k\binom{p}{k} = p\binom{p - 1}{k - 1}$ pour $k \geqslant 1$, puis la formule du binôme : $$R(1, p) = \sum_{k=1}^{p} (-1)^{p-k}\,p\binom{p - 1}{k - 1} = p\sum_{j=0}^{p-1} (-1)^{p-1-j}\binom{p - 1}{j} = p\,(1 - 1)^{p-1},$$ qui vaut $1$ si $p = 1$ et $0$ si $p \geqslant 2$ : c'est $S(1, p)$ par la question 1.

Hérédité : Supposons la propriété vraie au rang $n - 1$, pour un entier $n \geqslant 2$. Si $p = 1$, alors $R(n, 1) = 1^{n} - 0^{n} = 1 = S(n, 1)$. Pour $p \geqslant 2$, la question 3 et l'hypothèse de récurrence donnent $$S(n, p) = p\,R(n - 1, p) + p\,R(n - 1, p - 1), \qquad\text{soit}$$

$$S(n, p) = \sum_{k=0}^{p} (-1)^{p-k}\,p\binom{p}{k}k^{n-1} - \sum_{k=0}^{p-1} (-1)^{p-k}\,p\binom{p - 1}{k}k^{n-1} = \sum_{k=0}^{p} (-1)^{p-k}\,p\bigg(\binom{p}{k} - \binom{p - 1}{k}\bigg)k^{n-1},$$ avec la convention $\binom{p - 1}{p} = 0$. Par la formule de Pascal, $\binom{p}{k} - \binom{p - 1}{k} = \binom{p - 1}{k - 1}$ pour $k \geqslant 1$, et $p\binom{p - 1}{k - 1} = k\binom{p}{k}$ ; pour $k = 0$, le coefficient est nul. Ainsi $$S(n, p) = \sum_{k=0}^{p} (-1)^{p-k}\,k\binom{p}{k}k^{n-1} = R(n, p).$$

Conclusion : La formule est vraie pour tous $n, p \geqslant 1$. $$\boxed{S(n, p) = \sum_{k=0}^{p} (-1)^{p-k}\binom{p}{k}k^{n}}$$ La proposition 6 obtient la même formule en développant un produit, d'un seul coup ; la récurrence la retrouve sans la formule du crible, mais il faut connaître le résultat pour le démontrer. Les deux expressions ont été comparées à une énumération des surjections pour $n, p \leqslant 7$.