Exercice corrigé : Nombres de Bell

Voici un exercice corrigé détaillé démontrant la formule des nombres de Bell

3 janvier 2023

320 vues

2 minutes de lecture

Voici l’énoncé d’un exercice qui va s’intéresser aux nombres de Bell. C’est un exercice de dénombrement, qui va utiliser des séries entières. On va donc mettre cet exercice en deuxième année dans le supérieur.

Retrouvez tous nos énoncés sur le dénombrement

Et voici l’énoncé :

Enoncé

Corrigé

Question 1 : Calcul des premiers termes

On a :

$B_1= 1$ , cela semble évident, on a qu’une seule manière de partitionner $\{a\}$
Pour partitionner $\{1,2\}$ , on a 2 possibilités : $\{\{a,b\}\}$ et $\{\{a\},\{b\}\}$ . Ainsi, $B_2= 2$
Pour $B_3$ , cela se complique un peu plus. Soit c’est l’ensemble tout entier : $\{\{a,b,c\}\}$ , soit le plus grand ensemble a 2 éléments et nécessairement le second n’en a qu’un : $\{\{a,b\},\{c\}\},\{\{a,c\},\{b\}\},\{\{b,c\},\{a\}\}$ , soit c’est découpé en 3 éléments : $\{\{a\},\{b\},\{c\}\}$ . Ainsi, $B_3=5$

Question 2 : Une formule de récurrence

On rentre ici dans la partie dénombrement. Posons $E_n = \{1,\ldots,n\}$ . On va donc s’intéresser à $E_{n+1}$

Lorsqu’on fait une partition, on va maintenant chercher l’ensemble qui contient n + 1. Celui contient k éléments distincts de n+1, avec $0 \ldots k \ldots n$ . Puisque c’est un ensemble à k éléments, on a $\displaystyle \binom{n}{k}$ façons de le choisir.

Il reste ensuite n-k éléments. On peut les partionner de $B_{n-k}$ façons différentes. Donc, pour k fixé, on a $\displaystyle \binom{n}{k}B_{n-k}$ . Maintenant, on peut faire varier k entre 0 et n, c’est-à-dire toutes les valeurs qu’il peut prendre.

Notons aussi que $\binom{n}{k}= \binom{n}{n-k}$

Ainsi,

B_{n+1} = \sum_{k=0}^n \binom{n}{n-k}B_{n-k}=\sum_{k=0}^n \binom{n}{k}B_{k}

On a ainsi établi la relation d’Aitken qui concerne les nombres de Bell

Question 3 : Expression des nombres de Bell

Faisons comme indiqué une récurrence forte.

Initialisation : On a d’une part, par définition $B_0 = 1$ . D’autre part,

\begin{array}{ll} & \displaystyle \sum_{i=0}^{+\infty}e^{-1} \dfrac{i^0}{i!}\\ =& e^{-1}\displaystyle \sum_{i=0}^{+\infty} \dfrac{1}{i!}\\ =& e^{-1}e^1 \\ =& 1 \end{array}

On a donc bien $B_0 = \displaystyle \sum_{i=0}^{+\infty}e^{-1} \dfrac{i^0}{i!}$

Hérédité : Soit $n \in \mathbb{N}$ fixé. On suppose que $\forall k \leq n, B_k = \displaystyle \sum_{i=0}^{+\infty}e^{-1} \dfrac{i^k}{i!}$ .

On sait que $B_{n+1} =\displaystyle \sum_{k=0}^n \binom{n}{k}B_{k}$ . Et donc :

\begin{array}{ll} B_{n+1} & =\displaystyle \sum_{k=0}^n \binom{n}{k}\sum_{i=0}^{+\infty}e^{-1} \dfrac{i^k}{i!}\\ & =\displaystyle e^{-1} \sum_{i=0}^{+\infty}\sum_{k=0}^n \binom{n}{k} \dfrac{i^k}{i!}\\ & =\displaystyle e^{-1} \sum_{i=0}^{+\infty}\dfrac{1}{i!}\sum_{k=0}^n \binom{n}{k} i^k\\ & =\displaystyle e^{-1} \sum_{i=0}^{+\infty}\dfrac{1}{i!}\sum_{k=0}^n \binom{n}{k} i^k1^{n-k}\\ & =\displaystyle e^{-1} \sum_{i=0}^{+\infty}\dfrac{1}{i!}(1+i)^n\\ & =\displaystyle e^{-1} \sum_{i=0}^{+\infty}\dfrac{1}{i!(i+1)}(1+i)^{n+1}\\ & =\displaystyle \sum_{i=0}^{+\infty}e^{-1} \dfrac{(1+i)^{n+1}}{(i+1)!}\\ & =\displaystyle \sum_{i=1}^{+\infty}e^{-1} \dfrac{i^{n+1}}{i!}\\ & =\displaystyle \sum_{i=0}^{+\infty}e^{-1} \dfrac{i^{n+1}}{i!}\\ \end{array}

On peut bien inverser les signes sommes car l’un des sommes est finie et chacune des séries est bien convergente (la preuve est laissée au lecteur, et si jamais, vous avez la preuve dans la vidéo ci-dessous). En faisant cela, on a bien obtenu le résultat recherché. Ainsi,