5.4 Les nombres de Stirling de deuxième espèce et les nombres de Bell (4 cas)

Pour pouvoir résoudre les quatre problèmes suivants, nous allons procéder de manière un peu différente. Nous allons commencer par définir les nombres de Stirling de deuxième espèce et les nombres de Bell comme étant la solution de deux de ces problèmes. Ensuite, nous les étudierons plus en détail et, en particulier, nous verrons comment les calculer.

Définition 5.4.1.

On définit les deux familles de nombres suivantes :

1.

On définit les nombres de Stirling de deuxième espèce $\displaystyle\left\{k\atop n\right\}$ comme étant le nombre de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes identiques si les urnes ne peuvent pas être vides et l’ordre des boules dans les urnes n’est pas important. ¹¹ 1 Notez que certains auteurs préfèrent la notation $\displaystyle S(n,k)$ , avec un $\displaystyle S$ majuscule pour les différencier des nombres de Stirling de première espèce qui utilisent plutôt un $\displaystyle s$ minuscule.
2.

On définit les nombres de Bell comme étant le nombre de façons de placer $\displaystyle k$ boules différentes dans des urnes identiques si les urnes ne peuvent pas être vides et l’ordre des boules dans les urnes n’est pas important.

Bien que ces définitions ne nous donnent pas d’information à priori sur comment les calculer, il s’agit tout de même de la solution de deux de nos problèmes. Puis, à partir des nombres de Stirling de deuxième espèce, on obtient immédiatement la solution des deux autres, ce que nous allons faire tout de suite. Puis, nous verrons comment les évaluer à l’aide d’une récurrence et d’une formule explicite.

Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes identiques, si les urnes ne peuvent pas être vide et que l’ordre des boules dans les urnes n’est pas importante ?

Ce problème est maintenant particulièrement facile, car il s’agit exactement de la définition des nombres de Stirling de deuxième espèce. On peut donc directement affirmer que la réponse est $\displaystyle\left\{k\atop n\right\}$ .

Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans des urnes identiques, si les urnes ne peuvent pas être vide et que l’ordre des boules dans les urnes n’est pas importante ?

Comme pour le problème précédent, la solution de ce problème est maintenant particulièrement facile. Par définition, il s’agit tout simplement du nombre de Bell $\displaystyle B_{k}$ .

Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes différentes, si les urnes ne peuvent pas être vide et que l’ordre des boules dans les urnes n’est pas importante ?

Pour résoudre ce problème, remarquons premièrement que la seule différence entre ce problème et la définition des nombres de Stirling de deuxième espèce est que les urnes sont maintenant distinctes. On peut donc résoudre le problème en plaçant les $\displaystyle k$ boules dans les urnes sans tenir compte de quelle urne il s’agit (donc comme si elles étaient identiques), ce qui peut être fait de $\displaystyle\left\{k\atop n\right\}$ façons. Puis, on ordonne les urnes pour tenir compte du fait qu’elles sont toutes différentes, ce qui peut être fait de $\displaystyle n!$ façons. La solution du problème est donc:

\displaystyle n!\left\{k\atop n\right\}

Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes identiques, si l’ordre des boules dans les urnes n’est pas importante ?

À nouveau, ce problème est très semblable à la définition des nombres de Stirling de deuxième espèce, sauf que cette fois ci, les urnes peuvent être laissées vides. Ce problème revient donc à se demander combien il y a de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle 1$ urnes, puis le nombre de façons de les placer dans $\displaystyle 2$ urnes, puis le nombre de façons de les placer dans $\displaystyle 3$ urnes, etc…. jusqu’à un maximum de $\displaystyle n$ urnes. Ce qui nous donne, par le principe de la somme, la formule suivante:

\displaystyle\sum_{i=1}^{n}\left\{k\atop i\right\}

Une formule de récurrence pour les nombres de Stirling de deuxième espèce

Nous allons maintenant regarder comment calculer les nombres de Stirling de deuxième espèce, en commençant par chercher une récurrence. Pour ce faire, nous allons utiliser la méthode de l’élément distingué. Comme les urnes sont toutes identiques, notre élément distingué doit nécessairement être une boule. Cette boule peut soit être seule dans une urne, soit en compagnie d’une autre boule.

Si notre élément distingué est seul, il nous faut alors placer les $\displaystyle k-1$ boules restantes dans les $\displaystyle n-1$ urnes restantes, ce qui, par définition des nombres de Stirling de deuxième espèce, peut être accompli de $\displaystyle\left\{k-1\atop n-1\right\}$ façons. D’un autre côté, si notre élément distingué n’est pas seul, alors on commence par placer les $\displaystyle k-1$ boules qui ne sont pas notre élément distingué dans les $\displaystyle n$ urnes, ce qui peut être fait de $\displaystyle\left\{k-1\atop n\right\}$ façons, puis on choisit l’urne dans laquelle placer notre élément distingué. Bien que les urnes soient originellement toutes identiques, le fait d’avoir déjà placé les $\displaystyle k-1$ boules (toutes différentes) dans les urnes nous permet maintenant de distinguer les urnes. En d’autres mots, une fois qu’elles contiennent quelque chose, elles sont maintenant toutes différentes. On a donc $\displaystyle n$ endroits ou nous pouvons placer notre élément distingué. On obtient donc la récurrence suivante:

\displaystyle\left\{k\atop n\right\}=\left\{k-1\atop n-1\right\}+n\left\{k-1% \atop n\right\},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak% \ \leavevmode\nobreak\ \leavevmode\nobreak\ \textrm{ si }\leavevmode\nobreak\ % \leavevmode\nobreak\ 1<n<k

Il nous reste maintenant à trouver des valeurs initiales appropriées. Il est facile de voir qu’il n’y a qu’une seule façon de placer $\displaystyle k$ boules dans une urne, car toutes les boules doivent alors se retrouver dans cette urne. On a donc:

\displaystyle\left\{k\atop 1\right\}=1

De plus, il n’y a qu’une seule façon de placer $\displaystyle k$ boules dans $\displaystyle k$ urnes, car chaque urne devra contenir exactement une boule. Comme toutes les urnes sont identiques, cela ne fait aucune différence dans quelle urne se retrouve chaque boule. On a donc:

\displaystyle\left\{k\atop k\right\}=1

Il est aussi important de remarquer que si nous avons un nombre insuffisant de boules pour qu’il puisse y avoir au moins une boule dans chaque urne, alors le problème n’a aucune solution. On doit donc aussi ajouter la condition suivante:

\displaystyle\left\{k\atop n\right\}=0,\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \textrm{ si }\leavevmode\nobreak\ \leavevmode\nobreak\ k<n

À partir de la récurrence et des valeurs initiales que nous venons de trouver, il nous est maintenant facile d’utiliser Python pour trouver les valeurs des nombres de Stirling de deuxième espèce.

Listing 26: Nombres de Stirling de deuxième espèce

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              def Stirling2(k,n):


                6
                
                
                
                  if n == 1:


                7
                
                
                
                      return 1


                8
                
                
                
                  if k == n:


                9
                
                
                
                      return 1


                10
                
                
                
                  if 1 < n < k:


                11
                
                
                
                      return Stirling2(k-1,n-1) + n * Stirling2(k-1,n)


                12
                
                
                
                  else:


                13
                
                
                
                      return 0


                14
                
                
                
              


                15
                
                
                
              A = []


                16
                
                
                
              for k in range(1,11):


                17
                
                
                
                  ligne = [Stirling2(k,n) for n in range(1,11)]


                18
                
                
                
                  A.append(ligne)


                19
                
                
                
              tableau = DataFrame(A)


                20
                
                
                
              tableau.columns = [i for i in range(1,11)]


                21
                
                
                
              tableau.index = [i for i in range(1,11)]


                22
                
                
                
              tableau

Ce qui nous permet d’obtenir le tableau suivant:

Nombre de Stirling de deuxième espèce

$\displaystyle k\backslash n$	1	2	3	4	5	6	7	8	9	10
1	1	0	0	0	0	0	0	0	0	0
2	1	1	0	0	0	0	0	0	0	0
3	1	3	1	0	0	0	0	0	0	0
4	1	7	6	1	0	0	0	0	0	0
5	1	15	25	10	1	0	0	0	0	0
6	1	31	90	65	15	1	0	0	0	0
7	1	63	301	350	140	21	1	0	0	0
8	1	127	966	1701	1050	266	28	1	0	0
9	1	255	3025	7770	6951	2646	462	36	1	0
10	1	511	9330	34105	42525	22827	5880	750	45	1

Une formule explicite pour les nombres de Stirling de deuxième espèce

Bien que la récurrence soit, en théorie, suffisante pour calculer la valeur des nombres de Stirling de deuxième espèce, en pratique, il est souvent plus utile d’avoir à notre disposition une formule explicite. C’est ce que nous allons chercher immédiatement. Pour ce faire, plutôt que de travailler directement avec la définition, nous allons chercher le nombre de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes différentes si les urnes ne peuvent pas être vides et que l’ordre des boules n’est pas important. Une fois que nous aurons résolu ce problème, il nous suffira alors de diviser par $\displaystyle n!$ pour retrouver la valeur des nombres de Stirling de deuxième espèce.

Pour ce faire, commençons par remarquer qu’il y a $\displaystyle n^{k}$ façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes différentes, s’il n’y a aucune autre condition. Le problème étant que cela inclut le cas ou au moins une urne est vide. Comme il y a $\displaystyle\binom{n}{1}$ façons de choisir une urne pour quelle soit vide, et $\displaystyle(n-1)^{k}$ façons de placer les $\displaystyle k$ boules dans les $\displaystyle n-1$ urnes restantes. On a donc:

\displaystyle n^{k}-\binom{n}{1}(n-1)^{k}

Le problème est maintenant que nous avons retiré deux fois les cas ou au moins deux urnes sont vides. Il faut donc les ajouter à nouveau. Pour ce faire, on choisit les deux urnes qui sont vides en calculant $\displaystyle\binom{n}{2}$ , puis on place les $\displaystyle k$ boules dans les $\displaystyle n-2$ urnes restantes. On a donc:

\displaystyle n^{k}-\binom{n}{1}(n-1)^{k}+\binom{n}{2}(n-2)^{k}

Cette fois, ce sont les cas où au moins trois urnes vides qui nous créent des maux de tête. Nous les avons ajoutées deux fois, ce qui signifie que nous devons à nouveau les retirer. En continuant de la même façon, on obtient finalement la formule suivante pour le nombre de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes différentes si les urnes peuvent être vides et que l’ordre n’est pas important :

\displaystyle n!\left\{k\atop n\right\}=\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}(n-i% )^{k}

À partir de cette dernière expression, on peut donc affirmer que la formule explicite pour les nombres de Stirling de deuxième espèce est:

\displaystyle\left\{k\atop n\right\}=\frac{1}{n!}\sum_{i=0}^{n}(-1)^{i}\binom{% n}{i}(n-i)^{k}

Exemple de calcul des nombres de Stirling de deuxième espèce

Nous allons maintenant regarder comment utiliser la récurrence et la formule explicite pour évaluer les nombres de Stirling de deuxième espèce. Nous allons illustrer chacune de ces deux méthodes en calculant la valeur de $\displaystyle\left\{5\atop 3\right\}$ .

À partir de la récurrence, nous avons:

$\displaystyle\displaystyle\left\{5\atop 3\right\}$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\left\{4\atop 2\right\}+3\left\{4\atop 3\right\}$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\left(\left\{3\atop 1\right\}+2\left\{3\atop 2\right% \}\right)+3\left(\left\{3\atop 2\right\}+3\left\{3\atop 3\right\}\right)$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 1+2\left(\left\{2\atop 1\right\}+2\left\{2\atop 2% \right\}\right)+3\left(\left\{2\atop 1\right\}+2\left\{2\atop 2\right\}+3\right)$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 1+2(1+2)+3(1+2+3)=1+6+18$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 25$

Pour ce qui est de la formule explicite, nous obtenons:

$\displaystyle\displaystyle\left\{5\atop 3\right\}$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\frac{1}{3!}\left(\binom{3}{0}\cdot 3^{5}-\binom{3}{% 1}\cdot 2^{5}+\binom{3}{2}\cdot 1^{5}-0\right)$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\frac{1}{6}\left(1\cdot 3^{5}-3\cdot 2^{5}+3\cdot 1^% {5}\right)$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\frac{1}{6}\left(243-96+3\right)=\frac{1}{6}(150)$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 25$

Tel qu’attendu, les deux méthodes nous donnent la même réponse.

Les nombres de Bell

Nous avons défini les nombres de Bell (du nom de Eric Temple Bell) au début de la section comme étant le nombre de façons de placer $\displaystyle k$ boules différentes dans des urnes identiques, si les urnes ne peuvent pas être vides et que l’ordre des boules dans les urnes n’est pas important. Ceci est équivalent à se demander combien il y a de relations d’équivalence sur un ensemble de $\displaystyle k$ éléments, ou bien le nombre de façons de partitionner un ensemble de $\displaystyle k$ éléments.

Nous allons commencer par chercher une formule explicite pour les nombres de Bell. Pour trouver le nombre de façons de placer $\displaystyle k$ boules différentes dans des urnes identiques, si les urnes ne peuvent pas être vides et que l’ordre des boules dans les urnes n’est pas important, nous pouvons compter le nombre de façons de les placer dans une urne, puis dans $\displaystyle 2$ urnes, puis dans $\displaystyle 3$ urnes, etc… En additionnant le tout, nous obtenons une formule pour $\displaystyle B_{k}$ . Par définition des nombres de Stirling de deuxième espèce, nous avons donc la formule explicite suivante:

\displaystyle B_{k}=\sum_{i=1}^{k}\left\{k\atop i\right\}=\sum_{i=1}^{k}\left(% \frac{1}{i!}\sum_{j=0}^{i}(-1)^{j}\binom{i}{j}(i-j)^{k}\right)

Remarquez que la formule de droite peut sembler particulièrement compliquée, mais si nous avons accès à une table des nombres de Stirling de deuxième espèce, la formule du milieu est particulièrement simple à utiliser.

Nous allons maintenant chercher une formule de récurrence permettant d’évaluer les nombres de Bell. Pour obtenir cette formule de récurrence, remarquons premièrement qu’il n’existe qu’une seule façon de placer $\displaystyle 0$ boules dans des urnes. On a donc $\displaystyle B_{0}=1$ . Bien qu’il puisse sembler complètement inutile de vouloir placer $\displaystyle 0$ boules dans des urnes, cette valeur nous sera particulièrement utile comme valeur initiale pour notre récurrence. Ensuite, nous utilisons la méthode de l’élément distingué. Fixons l’une des boules comme étant notre élément distingué. Cette boule peut soit être seule dans une urne, soit en compagnie d’autres boules. Nous allons donc choisir les $\displaystyle j$ boules qui ne sont pas dans la même urne que notre élément distingué, où $\displaystyle j$ est un nombre entre $\displaystyle 0$ et $\displaystyle k-1$ , puis on place ces $\displaystyle j$ boules dans des urnes. Ceci nous donne la récurrence suivante:

\displaystyle B_{k}=\sum_{j=0}^{k-1}\binom{k-1}{j}B_{j}\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \Longleftrightarrow\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ B_{k+1}=\sum_{j=0}^{k}% \binom{k}{j}B_{j}

Il existe une façon simple et efficace de calculer les différentes valeurs des nombres de Bell $\displaystyle B_{k}$ . L’idée est de construire un triangle semblable au triangle de Pascal, que l’on appelle le triangle de Bell. On commence par écrire $\displaystyle 1$ sur la première ligne ; puis chaque ligne subséquente est obtenue en commençant par le dernier nombre de la ligne précédente et, pour chaque nombre suivant, on additionne le nombre précédent avec celui qui se trouve immédiatement au dessus du nombre précédent. Chaque ligne aura ainsi un nombre de plus que la ligne précédente. Une fois le triangle construit, on remarque que les nombres de Bell sont en fait le dernier nombre de chacune des lignes. La première ligne correspondante à $\displaystyle B_{1}$ .

Triangle de Bell

1
1	2
2	3	5
5	7	10	15
15	20	27	37	52
52	67	87	114	151	203
203	255	322	409	523	674	877

En utilisant le triangle ci-dessus, on peut donc obtenir par exemple que $\displaystyle B_{5}=52$ .

Commentaires additionnels sur les nombres de Stirling de deuxième espèce

Nous avons défini les nombres de Stirling de deuxième espèce $\displaystyle\left\{k\atop n\right\}$ comme étant le nombre de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes identiques sans qu’aucune urne ne soit vide et si l’ordre des boules dans les urnes n’est pas important. L’origine des nombres de Stirling vient en fait d’un problème complètement différent. Nous avons vu que les factorielles tombantes correspondent à la solution du problème de choisir $\displaystyle k$ objets parmi $\displaystyle n$ avec ordre et sans remise. À partir de cette définition, il est relativement facile de trouver la fonction génératrice exponentielle de cette suite de nombres. On a donc:

\displaystyle\sum_{k=0}^{\infty}n^{\underline{k}}\frac{x^{k}}{k!}=(1+x)^{n}

Cette fonction génératrice peut en fait être interprétée en considérant que chaque objet peut être choisi ou non. Pour chaque objet, on a donc la fonction génératrice $\displaystyle(1+x)$ . En considérant que nous avons $\displaystyle n$ objets, on obtient alors immédiatement la fonction génératrice exponentielle ci-dessus. Il est cependant important de remarquer que cette approche ne fonctionne qu’avec les fonctions génératrices exponentielles, car l’ordre est implicite dans le problème.

Une question différente, mais tout aussi intéressante d’un point de vue théorique de la combinatoire est de se demander si les factorielles tombantes ne seraient pas la fonction génératrice d’une autre suite intéressante. On cherche donc une famille de nombres $\displaystyle s(k,n)$ telle que:

\displaystyle\sum_{k=0}^{\infty}s(k,n)x^{k}=x^{\underline{n}}

Les nombres $\displaystyle s(k,n)$ portent le nom de nombres de Stirling signés de première espèce. Le terme signé fait ici référence au fait qu’ils peuvent être positifs ou négatifs. D’un point de vue combinatoire, c’est cependant la valeur absolue de ces nombres qui est la plus intéressante. On définit donc les nombres de Stirling de première espèce comme étant:

\displaystyle\left[k\atop n\right]=\left|s(k,n)\right|

La question suivante est maintenant de se demander ce qui se passe si l’on échange le rôle du $\displaystyle x^{n}$ et celui du $\displaystyle x^{\underline{k}}$ . Pour que le problème ait du sens, il faut alors prendre la somme sur les $\displaystyle n$ plutôt que sur les $\displaystyle k$ . C’est à dire, peut-on trouver une famille de nombres $\displaystyle S(k,n)$ qui satisfait l’égalité suivante:

\displaystyle\sum_{n=0}^{\infty}S(k,n)x^{\underline{n}}=x^{k}

Les nombres $\displaystyle S(k,n)$ ainsi définis ont été appelés les nombres de Stirling de deuxième espèce et correspondent directement au problème de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes identiques sans que les urnes ne soient vides, et si l’ordre des boules dans les urnes n’est pas important. On a donc:

\displaystyle\left\{k\atop n\right\}=S(k,n)

Comme nous l’avons déjà mentionné, cette approche pour définir les nombres de Stirling est surtout intéressante d’un point de vue théorique, mais aussi du point de vue de l’algèbre linéaire où ces derniers peuvent être vus comme des matrices de passage entre différentes bases sur un espace vectoriel de polynômes. L’approche en termes des problèmes d’occupation est cependant beaucoup plus concrète et sera préférée dans le cours. Il est cependant intéressant de démontrer que ces deux approches sont absolument équivalentes, ce que nous pouvons faire à l’aide de l’induction. Pour ce faire, il nous faut cependant commencer par ajouter les valeurs initiales correspondant à $\displaystyle k=0$ et à $\displaystyle n=0$ . On dira donc que:

\displaystyle\left\{k\atop 0\right\}=\left\{\begin{array}[]{l}1\textrm{ si }k=% 0\\ 0\textrm{ si }k>0\end{array}\right.\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \textrm{ et }\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \left\{0\atop n\right\}=\left\{% \begin{array}[]{l}1\textrm{ si }n=0\\ 0\textrm{ si }n>0\end{array}\right.

À partir de la définition des nombres de Stirling de deuxième espèce ainsi que de la valeur initiale ci-dessus, on peut maintenant démontrer la formule suivante:

\displaystyle\sum_{n=0}^{\infty}\left\{k\atop n\right\}x^{\underline{n}}=x^{k}

1.

Si $\displaystyle k=0$ on a:

$\displaystyle\sum_{n=0}^{\infty}\left\{0\atop n\right\}x^{\underline{n}}=\left% \{0\atop 0\right\}x^{\underline{0}}=1\cdot 1=1$

Ce qui correspond à la valeur de $\displaystyle x^{0}$ . L’égalité est donc vraie si $\displaystyle k=0$ .
2.

Supposons que l’égalité est vraie pour $\displaystyle k=j$ . C’est à dire que l’on suppose que:

$\displaystyle\sum_{n=0}^{\infty}\left\{j\atop n\right\}x^{\underline{n}}=x^{j}$

Vérifions que l’égalité est encore vraie si $\displaystyle k=j+1$ . On a donc:

$\displaystyle\displaystyle\sum_{n=0}^{\infty}\left\{j+1\atop n\right\}x^{% \underline{n}}$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\left\{j+1\atop 0\right\}x^{\underline{0}}+\sum_{n=1% }^{\infty}\left\{j+1\atop n\right\}x^{\underline{n}}=\sum_{n=1}^{\infty}\left[% \left\{j\atop n-1\right\}+n\left\{j\atop n\right\}\right]x^{\underline{n}}$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\sum_{n=1}^{\infty}\left\{j\atop n-1\right\}x^{% \underline{n}}+\sum_{n=1}^{\infty}n\left\{j\atop n\right\}x^{\underline{n}}=% \sum_{n=0}^{\infty}\left\{j\atop n\right\}x^{\underline{n+1}}+\sum_{n=0}^{% \infty}n\left\{j\atop n\right\}x^{\underline{n}}$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\sum_{n=0}^{\infty}(x-n)\left\{j\atop n\right\}x^{% \underline{n}}+\sum_{n=0}^{\infty}n\left\{j\atop n\right\}x^{\underline{n}}=x% \sum_{n=0}^{\infty}\left\{j\atop n\right\}x^{\underline{n}}=x\cdot x^{k}=x^{k+1}$

L’équation est donc encore vraie dans le cas où $\displaystyle k=j+1$ .

Par le principe d’induction, on peut donc affirmer que l’égalité est vraie pour tous les $\displaystyle k\geq 0$ .