Exercice 16

1. Les $k$ parties d'une partition de $\llbracket 1\,,n \rrbracket$ en parties non vides sont deux à deux disjointes et ont chacune au moins un élément, donc $k \leqslant n$ par la proposition 2 (i). La seule partition en une partie est $\{\llbracket 1\,,n \rrbracket\}$, et la seule partition en $n$ parties est celle en singletons. $$\boxed{T(n, k) = 0 \text{ pour } k > n, \qquad T(n, 1) = T(n, n) = 1 \text{ pour } n \geqslant 1}$$

2. Soit $n, k \geqslant 1$. On sépare les partitions de $\llbracket 1\,,n \rrbracket$ en $k$ parties selon que $\{n\}$ en est une partie ou non.

• Si $\{n\}$ est une partie, les $k - 1$ autres forment une partition de $\llbracket 1\,,n - 1 \rrbracket$, et réciproquement toute partition de $\llbracket 1\,,n - 1 \rrbracket$ en $k - 1$ parties, complétée par $\{n\}$, convient. Il y a $T(n - 1, k - 1)$ telles partitions ; pour $n = 1$, la partition $\{\{1\}\}$ correspond à la partition vide de $\varnothing$, ce que traduit la convention $T(0, 0) = 1$.

• Sinon, $n$ appartient à une partie $P$ qui a d'autres éléments. En retirant $n$ de $P$, on obtient une partition de $\llbracket 1\,,n - 1 \rrbracket$ en $k$ parties non vides. Réciproquement, une partition de $\llbracket 1\,,n - 1 \rrbracket$ en $k$ parties est obtenue de cette façon à partir de exactement $k$ partitions, selon la partie à laquelle on ajoute $n$. Le lemme des bergers donne $k\,T(n - 1, k)$ partitions.

$$\boxed{T(n, k) = T(n - 1, k - 1) + k\,T(n - 1, k) \quad \text{pour } n, k \geqslant 1}$$ Les conventions rendent la formule valable au bord. Pour $n = k = 1$, par exemple, le second membre vaut $T(0, 0) + T(0, 1) = 1$, qui est bien $T(1, 1)$ ✓.

def T(n, k):
    if n == 0 and k == 0:
        return 1
    if n == 0 or k == 0:
        return 0
    return T(n - 1, k - 1) + k * T(n - 1, k)

print([T(4, k) for k in range(5)])   # affiche [0, 1, 7, 6, 1]

Chaque appel non terminal diminue $n$ de $1$, et les appels avec $n = 0$ s'arrêtent : la fonction se termine, comme à l'exercice 15.

3. À une surjection $f$ de $\llbracket 1\,,n \rrbracket$ sur $\llbracket 1\,,k \rrbracket$, on associe la partition $\pi(f)$ de $\llbracket 1\,,n \rrbracket$ formée de ses $k$ fibres $f^{-1}(\{y\})$, non vides puisque $f$ est surjective. Fixons une partition $\{P_{1}, \dots, P_{k}\}$ en $k$ parties : les surjections $f$ telles que $\pi(f)$ soit cette partition sont constantes sur chaque $P_{i}$, et la valeur prise sur les parties définit une bijection de $\{P_{1}, \dots, P_{k}\}$ sur $\llbracket 1\,,k \rrbracket$ ; réciproquement, chaque bijection fournit une telle surjection. Chaque fibre de $\pi$ a donc $k!$ éléments, et le lemme des bergers donne $$\boxed{S(n, k) = k!\,T(n, k) \quad \text{pour } n, k \geqslant 1}$$ Choisir une surjection, c'est choisir un partage en $k$ paquets, puis étiqueter les paquets. On en déduit $T(n, 2) = \frac{2^{n} - 2}{2} = 2^{n-1} - 1$, et $T(n + 1, n) = \binom{n + 1}{2}$ par l'exercice 15.

4. On a $B_{1} = 1$, puis $B_{2} = 2$, avec les partitions $\{\{1, 2\}\}$ et $\{\{1\}, \{2\}\}$, et $B_{3} = 5$, avec $\{\{1, 2, 3\}\}$, les trois partitions $\{\{i, j\}, \{k\}\}$ et la partition en singletons.

Soit $n \in \mathbb{N}$, et $\mathcal{P}$ une partition de $\llbracket 1\,,n + 1 \rrbracket$. Notons $P$ la partie qui contient $n + 1$, et $Q = P \setminus \{n + 1\}$, partie de $\llbracket 1\,,n \rrbracket$. Les autres parties de $\mathcal{P}$ forment une partition de $\llbracket 1\,,n \rrbracket \setminus Q$. Réciproquement, une partie $Q$ de $\llbracket 1\,,n \rrbracket$ et une partition de $\llbracket 1\,,n \rrbracket \setminus Q$ déterminent une unique partition de $\llbracket 1\,,n + 1 \rrbracket$, dont $Q \cup \{n + 1\}$ est la partie contenant $n + 1$. Si $\llbracket 1\,,n \rrbracket \setminus Q$ a $k$ éléments, il y a $B_{k}$ partitions de cet ensemble, avec $B_{0} = 1$ pour $Q = \llbracket 1\,,n \rrbracket$ ; et il y a $\binom{n}{k}$ parties $Q$ dont le complémentaire a $k$ éléments (proposition 4). En regroupant selon $k$ : $$\boxed{B_{n+1} = \sum_{k=0}^{n} \binom{n}{k}B_{k}}$$

$$\boxed{B_{1} = 1, \quad B_{2} = 2, \quad B_{3} = 5, \quad B_{4} = 15, \quad B_{5} = 52}$$ L'exercice 28 de la feuille du chapitre 2 a dénombré les partitions de $\{1, 2, 3, 4\}$, qui sont $15$, et en a déduit le nombre de relations d'équivalence sur un ensemble à quatre éléments : le chapitre 2 (proposition 8 et théorème 4) a établi une bijection entre relations d'équivalence et partitions. Le nombre $B_{n}$ est donc aussi le nombre de relations d'équivalence sur un ensemble à $n$ éléments. On a encore $B_{n} = \sum_{k=0}^{n} T(n, k)$, en regroupant les partitions selon leur nombre de parties : par exemple $B_{4} = 1 + 7 + 6 + 1$.

À retenir. Le corrigé de l'exercice 3 de la feuille du chapitre 20 avait trouvé les coefficients $1$, $1$, $2$, $5$, $15$ de $\mathrm{e}$ dans $\sum_{n=0}^{+\infty} \frac{n^{k}}{n!}$, pour $k = 0$, …, $4$, et annonçait qu'ils comptent les partitions d'un ensemble à $k$ éléments : on reconnaît $B_{0}$, …, $B_{4}$. Le calcul de sympy confirme $\sum_{n=0}^{+\infty} \frac{n^{k}}{n!} = B_{k}\,\mathrm{e}$ jusqu'à $k = 5$.