Polynôme de Bell

En mathématiques, et plus précisément en combinatoire, les polynômes de Bell, nommés ainsi d'après le mathématicien Eric Temple Bell, sont des polynômes multivariés définis par :

$(n,k)\in \mathbb {N} ^{2},B_{n,k}(x_{1},x_{2},\dots )\;{\overset {\text{def}}{=}}\;n!\sum _{\begin{matrix}(m_{1},m_{2},\dots )\in \mathbb {N} ^{\mathbb {N} ^{*}}\\{\begin{cases}\sum _{i\in \mathbb {N} ^{*}}m_{i}=k\\\sum _{i\in \mathbb {N} ^{*}}i\cdot m_{i}=n\end{cases}}\end{matrix}}\prod _{i\in \mathbb {N} ^{*}}{\frac {x_{i}^{m_{i}}}{m_{i}!\,(i!)^{m_{i}}}}$

Sachant que m_i est forcément nul pour i > n − k + 1, on peut expliciter la borne supérieure des indices i :

$B_{n,k}(x_{1},\dots ,x_{n-k+1})\;=\;n!\sum _{\begin{matrix}(m_{1},\dots ,m_{n-k+1})\in \mathbb {N} ^{n-k+1}\\{\begin{cases}\sum _{i=1}^{n-k+1}m_{i}=k\\\sum _{i=1}^{n-k+1}i\cdot m_{i}=n\end{cases}}\end{matrix}}\prod _{i=1}^{n-k+1}{\frac {x_{i}^{m_{i}}}{m_{i}!\,(i!)^{m_{i}}}}$

Démonstration

Si m₁ = k − 1 et m_n−k+1 = 1, alors ∑ m_i = k et ∑ i·m_i = n, donc la borne supérieure des sommes doit valoir au minimum n − k + 1 pour couvrir correctement toutes les suites (m_i)_i≥1 valides.

Supposons qu'il existe un indice j > n − k + 1 tel que m_j ≠ 0, soit m_j ≥ 1. Les indices commençant à 1, on a également j ≥ 1, soit j − 1 ≥ 0, d'où (j − 1)·m_j ≥ j − 1 En outre, les inégalités i ≥ 1 et m_i ≥ 0 donnent i·m_i ≥ m_i. On obtient donc

${\begin{aligned}n&=\sum _{i\in \mathbb {N} ^{*}}i\cdot m_{i}\\&=j\cdot m_{j}+\sum _{i\in \mathbb {N} ^{*}\setminus \{j\}}i\cdot m_{i}\\&\geq j\cdot m_{j}+\sum _{i\in \mathbb {N} ^{*}\setminus \{j\}}m_{i}\quad {\text{ (par }}i\cdot m_{i}\geq m_{i}{\text{)}}\\&=(j-1)\cdot m_{j}+\sum _{i\in \mathbb {N} ^{*}}m_{i}\\&=(j-1)\cdot m_{j}+k\\&\geq j-1+k\quad {\text{ (par }}(j-1)\cdot m_{j}\geq (j-1){\text{)}}\\&>(n-k+1)-1+k\quad {\text{ (par }}j>n-k+1{\text{)}}\\&=n\end{aligned}}$

soit n > n, ce qui est contradictoire. Donc m_j = 0 pour tout j > n − k + 1, et la borne supérieure des sommes n'a pas besoin d'aller au-delà de n − k + 1 pour couvrir toutes les suites (m_i)_i≥1 valides.

Pour j > n − k + 1, on a m_j = 0, d'où x_j^m_j/m_j! (j!)^m_j = 1, donc la borne supérieure du produit n'a pas besoin d'aller au-delà de n − k + 1.

Interprétation combinatoire

Soit un ensemble de n éléments partitionné en k sous-ensembles non vides, dont m1 sous-ensembles de cardinalité 1, m2 sous-ensembles de cardinalité 2, etc. Le nombre de telles partitions est le coefficient du monôme unitaire xm1
1xm2
2… dans le polynôme de Bell Bn,k(x1, x2, …). On notera que :

• par construction, on a ∑ m_i = k (nombre de sous-ensembles) et ∑ i·m_i = n (nombre total d'éléments), avec chaque m_i positif ou nul (nombre de sous-ensembles de cardinalité i) ;
• par conséquent, les cardinalités des sous-ensembles forment une partition de l'entier n en k parties, avec m_i la multiplicité de l'entier i dans cette partition.

Démonstration

Formons une liste avec les n éléments de l'ensemble de départ, et construisons les k sous-ensembles d'arrivée en prenant 1 par 1 les m₁ premiers éléments de la liste, puis 2 par 2 les 2·m₂ éléments suivants, etc. Il y a donc n! listes différentes à partir desquelles construire ces sous-ensembles d'arrivée.

Exemple :

Pour m₁ = 1, m₂ = 2 et m₃ = 1 (soit k = 4 et n = 8), et pour un ensemble de départ {A, B, …, H}, une des 8! = 40320 listes possibles est CHEFBADG, avec laquelle on construit les sous-ensembles {C}, {H, E}, {F, B} et {A, D, G}.

Cependant, l'ordre des éléments dans chaque sous-ensemble est non pertinent, donc, pour un sous-ensemble donné de cardinalité i, il y a i! listes différentes donnant le même résultat. Il faut donc diviser le nombre de listes m₁ fois par 1!, m₂ fois par 2!, etc., soit au final par ∏ (i!)^m_i.

Exemple :

En permutant le 2^e et le 3^e élément de la liste, soit CEHFBADG, le premier sous-ensemble de cardinalité 2 devient {E, H} lors de sa construction, identique à {H, E}. De même, en permutant le 4^e et le 5^e élément de la liste, soit CHEBFADG, le second sous-ensemble de cardinalité 2 devient {B, F} lors de sa construction, identique à {F, B}. Enfin, les 3! = 6 permutations des 6^e au 8^e éléments (par exemple, CHEFBGAD) donnent le même sous-ensemble {A, D, G} de cardinalité 3. Les trois zones de permutation (portant respectivement sur EH, FB et ADG) étant indépendantes, il y a donc 2!·2!·3! = 24 listes différentes permettant de construire les mêmes sous-ensembles {C}, {H, E}, {F, B} et {A, D, G} (attention : en tenant compte de l'ordre des sous-ensembles).

Enfin, les m_i sous-ensembles de cardinalité i étant indiscernables, il faut également diviser le résultat précédent par m₁!·m₂!·… = ∏ m_i!.

Exemple :

Les 2 sous-ensembles de cardinalité 2 sont indiscernables, donc la liste CFBHEADG (qui construit les sous-ensembles {C}, {F, B}, {H, E} et {A, D, G}) donne la même partition que CHEFBADG. Il y a donc au final 24·2! = 48 listes donnant toutes la même partition que CHEFBADG. De manière générale, chaque partition peut être construite par 48 listes différentes, il y a donc 40320/48 = 840 partitions différentes pour (m₁, m₂, m₃) = (1, 2, 1). En conclusion, l'un des monômes du polynôme de Bell B_8,4(x₁, x₂, …) est donc 840x₃x²
₂x₁ (note : les variables x_i sont notées par ordre décroissant de leur indice, afin de suivre la convention de notation utilisée pour les partitions d'un entier).

Le nombre total de partitions est donc n!/∏ (i!)mi · ∏ mi! = n!/∏ mi!·(i!)mi, coefficient associé au monôme unitaire xm1
1xm2
2… = ∏ xmi
i.

Exemples

On a :

$B_{6,2}(x_{1},x_{2},x_{3},x_{4},x_{5})=6x_{5}x_{1}+15x_{4}x_{2}+10x_{3}^{2}$

car il y a :

• 6 partitions d'un ensemble à 6 éléments de la forme 5 + 1 ;
• 15 partitions de la forme 4 + 2 ;
• 10 partitions de la forme 3 + 3.

De même :

$B_{6,3}(x_{1},x_{2},x_{3},x_{4})=15x_{4}x_{1}^{2}+60x_{3}x_{2}x_{1}+15x_{2}^{3}$

car il y a :

• 15 partitions d'un ensemble à 6 éléments de la forme 4 + 1 + 1 ;
• 60 partitions de la forme 3 + 2 + 1 ;
• 15 partitions de la forme 2 + 2 + 2.

Polynômes de Bell complets

La somme

$B_{n}(x_{1},\dots ,x_{n})=\sum _{k=0}^{n}B_{n,k}(x_{1},\dots ,x_{n-k+1})$

est parfois appelée n-ème polynôme de Bell complet, et alors les polynômes B_n, k définis ci-dessus sont appelés des polynômes de Bell « partiels ». Les polynômes de Bell complets B_n peuvent être exprimés par le déterminant d’une matrice :

$B_{n}(x_{1},\dots ,x_{n})={\begin{vmatrix}{0 \choose 0}x_{1}&{1 \choose 0}x_{2}&{2 \choose 0}x_{3}&{3 \choose 0}x_{4}&\cdots &{n-2 \choose 0}x_{n-1}&{n-1 \choose 0}x_{n}\\\\-1&{1 \choose 1}x_{1}&{2 \choose 1}x_{2}&{3 \choose 1}x_{3}&\cdots &{n-2 \choose 1}x_{n-2}&{n-1 \choose 1}x_{n-1}\\\\0&-1&{2 \choose 2}x_{1}&{3 \choose 2}x_{2}&\cdots &{n-2 \choose 2}x_{n-3}&{n-1 \choose 2}x_{n-2}\\\\0&0&-1&{3 \choose 3}x_{1}&\cdots &{n-2 \choose 3}x_{n-4}&{n-1 \choose 3}x_{n-3}\\\\\vdots &\vdots &\vdots &\ddots &\ddots &\vdots &\vdots \\\\0&0&0&0&\cdots &{n-2 \choose n-2}x_{1}&{n-1 \choose n-2}x_{2}\\\\0&0&0&0&\cdots &-1&{n-1 \choose n-1}x_{1}\end{vmatrix}}=\left|{j-1 \choose i-1}x_{j-i+1}-\delta _{j-i+1}\right|$

avec δ_k le symbole de Kronecker. La matrice dont B_n est le déterminant est une matrice de Hessenberg.

Table de valeurs

Le tableau suivant regroupe les premières valeurs de $B_{n,k}(x_{1},\dots ,x_{n-k+1})$ :

k n	0	1	2	3	4	5	6
0	$1$
1	$0$	$x_{1}$
2	$0$	$x_{2}$	$x_{1}^{2}$
3	$0$	$x_{3}$	$3x_{2}x_{1}$	$x_{1}^{3}$
4	$0$	$x_{4}$	$4x_{3}x_{1}+3x_{2}^{2}$	$6x_{2}x_{1}^{2}$	$x_{1}^{4}$
5	$0$	$x_{5}$	$5x_{4}x_{1}+10x_{3}x_{2}$	$10x_{3}x_{1}^{2}+15x_{2}^{2}x_{1}$	$10x_{2}x_{1}^{3}$	$x_{1}^{5}$
6	$0$	$x_{6}$	$6x_{5}x_{1}+15x_{4}x_{2}+10x_{3}^{2}$	$15x_{4}x_{1}^{2}+60x_{3}x_{2}x_{1}+15x_{2}^{3}$	$20x_{3}x_{1}^{3}+45x_{2}^{2}x_{1}^{2}$	$15x_{2}x_{1}^{4}$	$x_{1}^{6}$

Propriétés

Cas limites

• $B_{n,0}(x_{1},x_{2},\dots )=\delta _{n}$ avec δ_n le symbole delta de Kronecker
• $B_{n,1}(x_{1},x_{2},\dots )|_{n\geq 1}=x_{n}$
• $B_{n,n}(x_{1},x_{2},\dots )=x_{1}^{n}$
• $B_{n,k}(x_{1},x_{2},\dots )|_{k>n}=0$

Séries formelles exponentielles

Puissance

${\frac {1}{k!}}\left(\sum _{n=1}^{\infty }x_{n}{\frac {t^{n}}{n!}}\right)^{k}=\sum _{n=k}^{\infty }B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}$

Démonstration

Pour n et k deux entiers naturels, soient j ∈ ℕ^* vérifiant j ≥ n − k + 1 et (y₁, …, y_j) une suite de scalaires. La formule du multinôme de Newton établit que

$\left(\sum _{i=1}^{j}y_{i}\right)^{k}=\sum _{\begin{matrix}(m_{1},\dots ,m_{j})\in \mathbb {N} ^{j}\\\sum _{i=1}^{j}m_{i}=k\end{matrix}}{\binom {k}{m_{1},\dots ,m_{j}}}\prod _{i=1}^{j}y_{i}^{m_{i}}=k!\sum _{\begin{matrix}(m_{1},\dots ,m_{j})\in \mathbb {N} ^{j}\\\sum _{i=1}^{j}m_{i}=k\end{matrix}}\prod _{i=1}^{j}{\frac {y_{i}^{m_{i}}}{m_{i}!}}$

En posant y_i = x_i tⁱ/i!, on obtient

${\frac {1}{k!}}\left(\sum _{i=1}^{j}x_{i}{\frac {t^{i}}{i!}}\right)^{k}=\sum _{\begin{matrix}(m_{1},\dots ,m_{j})\in \mathbb {N} ^{j}\\\sum _{i=1}^{j}m_{i}=k\end{matrix}}\prod _{i=1}^{j}{\frac {x_{i}^{m_{i}}t^{i\cdot m_{i}}}{m_{i}!\,({i!})^{m_{i}}}}=\sum _{\begin{matrix}(m_{1},\dots ,m_{j})\in \mathbb {N} ^{j}\\\sum _{i=1}^{j}m_{i}=k\end{matrix}}\left(\prod _{i=1}^{j}{\frac {x_{i}^{m_{i}}}{m_{i}!\,({i!})^{m_{i}}}}\right)t^{\sum _{i=1}^{j}i\cdot m_{i}}$

Chaque membre est un polynôme en t, on peut donc en extraire le coefficient c_n associé à tⁿ, qui vaut

$c_{n}=\sum _{\begin{matrix}(m_{1},\dots ,m_{j})\in \mathbb {N} ^{j}\\{\begin{cases}\sum _{i=1}^{j}m_{i}=k\\\sum _{i=1}^{j}i\cdot m_{i}=n\end{cases}}\end{matrix}}\prod _{i=1}^{j}{\frac {x_{i}^{m_{i}}}{m_{i}!\,({i!})^{m_{i}}}}$

Comme démontré précédemment (voir en-tête de l'article), les conditions ∑ m_i = k et ∑ i·m_i = n font que m_i = 0 pour tout i > n − k + 1. Comme on a choisi j ≥ n − k + 1, la somme constituant c_n couvre bien toutes les suites (m_i)_i≥1 valides, d'où

$c_{n}=\sum _{\begin{matrix}(m_{1},\dots ,m_{n-k+1})\in \mathbb {N} ^{n-k+1}\\{\begin{cases}\sum _{i=1}^{n-k+1}m_{i}=k\\\sum _{i=1}^{n-k+1}i\cdot m_{i}=n\end{cases}}\end{matrix}}\prod _{i=1}^{n-k+1}{\frac {x_{i}^{m_{i}}}{m_{i}!\,({i!})^{m_{i}}}}={\frac {B_{n,k}(x_{1},\dots ,x_{n-k+1})}{n!}}$

On peut donc rendre j arbitrairement grand sans changer c_n, qui est donc également le coefficient associé à tⁿ de la série formelle obtenue en faisant tendre j vers l'infini, d'où

${\frac {1}{k!}}\left(\sum _{i=1}^{\infty }x_{i}{\frac {t^{i}}{i!}}\right)^{k}=\sum _{n=0}^{\infty }c_{n}t^{n}=\sum _{n=0}^{\infty }B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}$

Comme B_n,k|_n<k = 0, la somme peut commencer à k.

On notera que cette propriété ayant été démontrée en utilisant uniquement la définition des polynômes de Bell (et la formule du multinôme de Newton), elle pourra servir (directement ou indirectement) pour démontrer la plupart des autres propriétés ci-dessous sans causer de raisonnement circulaire.

Formule exponentielle

$\exp \left(\sum _{n=1}^{\infty }x_{n}{\frac {t^{n}}{n!}}\right)^{k}=\sum _{n=0}^{\infty }B_{n}(x_{1},\dots ,x_{n}){\frac {t^{n}}{n!}}$

Démonstration

${\begin{aligned}\exp \left(\sum _{n=1}^{\infty }x_{n}{\frac {t^{n}}{n!}}\right)^{k}&=\sum _{k=0}^{\infty }{\frac {1}{k!}}\left(\sum _{n=1}^{\infty }x_{n}{\frac {t^{n}}{n!}}\right)^{k}\\&=\sum _{k=0}^{\infty }\sum _{n=k}^{\infty }B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{0\leq k\leq n}B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=0}^{\infty }\sum _{k=0}^{n}B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=0}^{\infty }B_{n}(x_{1},\dots ,x_{n}){\frac {t^{n}}{n!}}\end{aligned}}$

Composition

Si

$f(t)=\sum _{n=0}^{\infty }f_{n}{\frac {t^{n}}{n!}}$ (avec $f_{0}=f(0)$ quelconque)

et

$g(t)=\sum _{n=1}^{\infty }g_{n}{\frac {t^{n}}{n!}}$ (avec donc $g_{0}=g(0)=0$)

alors

$(f\circ g)(t)=\sum _{n=0}^{\infty }\left[\sum _{k=0}^{n}f_{k}B_{n,k}(g_{1},\dots ,g_{n-k+1})\right]{\frac {t^{n}}{n!}}$

Démonstration

${\begin{aligned}(f\circ g)(t)&=\sum _{k=0}^{\infty }f_{k}{\frac {g(t)^{k}}{k!}}\\&=\sum _{k=0}^{\infty }f_{k}{\frac {1}{k!}}\left(\sum _{n=1}^{\infty }g_{n}{\frac {t^{n}}{n!}}\right)^{k}\\&=\sum _{k=0}^{\infty }f_{k}\sum _{n=k}^{\infty }B_{n,k}(g_{1},\dots ,g_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{0\leq k\leq n}f_{k}B_{n,k}(g_{1},\dots ,g_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=0}^{\infty }\left[\sum _{k=0}^{n}f_{k}B_{n,k}(g_{1},\dots ,g_{n-k+1})\right]{\frac {t^{n}}{n!}}\end{aligned}}$

Formules de récurrence

${\begin{aligned}B_{n+1,k+1}(x_{1},\dots ,x_{n-k+1})&=\sum _{i=0}^{n-k}{\binom {n}{i}}x_{i+1}B_{n-i,k}(x_{1},\dots ,x_{n-i-k+1})\\&=\sum _{i=k}^{n}{\binom {n}{i}}x_{n-i+1}B_{i,k}(x_{1},\dots ,x_{i-k+1})\end{aligned}}$

avec B_n,0 = δ_n.

Démonstration

D'après la formule de puissance des séries formelles exponentielles (voir plus haut), on a

${\frac {1}{k!}}\left(\sum _{n=1}^{\infty }x_{n}{\frac {t^{n}}{n!}}\right)^{k}=\sum _{n=k}^{\infty }B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}$

d'où par changement de variable k → k + 1

$\sum _{n=k+1}^{\infty }B_{n,k+1}(x_{1},\dots ,x_{n-k}){\frac {t^{n}}{n!}}={\frac {1}{(k+1)!}}\left(\sum _{n=1}^{\infty }x_{n}{\frac {t^{n}}{n!}}\right)^{k+1}$

En dérivant chaque membre par rapport à t, on a d'une part

${\begin{aligned}\left[\sum _{n=k+1}^{\infty }B_{n,k+1}(x_{1},\dots ,x_{n-k}){\frac {t^{n}}{n!}}\right]'&=\sum _{n=k+1}^{\infty }B_{n,k+1}(x_{1},\dots ,x_{n-k}){\frac {t^{n-1}}{(n-1)!}}\\&=\sum _{n=k}^{\infty }B_{n+1,k+1}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}\end{aligned}}$

et d'autre part

${\begin{aligned}\left[{\frac {1}{(k+1)!}}\left(\sum _{n=1}^{\infty }x_{n}{\frac {t^{n}}{n!}}\right)^{k+1}\right]'&=\left(\sum _{i=1}^{\infty }x_{i}{\frac {t^{i}}{i!}}\right)'\cdot {\frac {1}{k!}}\left(\sum _{n=1}^{\infty }x_{n}{\frac {t^{n}}{n!}}\right)^{k}\\&=\sum _{i=0}^{\infty }x_{i+1}{\frac {t^{i}}{i!}}\cdot \sum _{j=k}^{\infty }B_{j,k}(x_{1},\dots ,x_{j-k+1}){\frac {t^{j}}{j!}}\\&=\sum _{\begin{cases}i\geq 0\\j\geq k\end{cases}}x_{i+1}B_{j,k}(x_{1},\dots ,x_{j-k+1}){\frac {t^{i+j}}{i!j!}}\\&{\underset {n=i+j}{=}}\sum _{\begin{cases}i\geq 0\\n-i\geq k\end{cases}}x_{i+1}B_{n-i,k}(x_{1},\dots ,x_{n-i-k+1}){\frac {t^{n}}{i!(n-i)!}}\\&=\sum _{\begin{cases}n-k\geq i\geq 0\\n\geq k+i\geq k\end{cases}}x_{i+1}B_{n-i,k}(x_{1},\dots ,x_{n-i-k+1}){\frac {t^{n}}{i!(n-i)!}}\\&=\sum _{n=k}^{\infty }\sum _{i=0}^{n-k}{\binom {n}{i}}x_{i+1}B_{n-i,k}(x_{1},\dots ,x_{n-i-k+1}){\frac {t^{n}}{n!}}\end{aligned}}$

d'où

$\sum _{n=k}^{\infty }B_{n+1,k+1}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}=\sum _{n=k}^{\infty }\sum _{i=0}^{n-k}{\binom {n}{i}}x_{i+1}B_{n-i,k}(x_{1},\dots ,x_{n-i-k+1}){\frac {t^{n}}{n!}}$

Enfin, par unicité de la décomposition des séries formelles exponentielles sur la base ${\begin{pmatrix}{\frac {t^{n}}{n!}}\end{pmatrix}}_{n\in \mathbf {N} }$, on obtient

$B_{n+1,k+1}(x_{1},\dots ,x_{n-k+1})=\sum _{i=0}^{n-k}{\binom {n}{i}}x_{i+1}B_{n-i,k}(x_{1},\dots ,x_{n-i-k+1})$

La seconde forme s'obtient immédiatement par le changement de variable i → n − i.

${\begin{aligned}B_{n+1}(x_{1},\dots ,x_{n+1})&=\sum _{i=0}^{n}{\binom {n}{i}}x_{i+1}B_{n-i}(x_{1},\dots ,x_{n-i})\\&=\sum _{i=0}^{n}{\binom {n}{i}}x_{n-i+1}B_{i}(x_{1},\dots ,x_{i})\end{aligned}}$

avec B₀ = B_0,0 = 1.

Démonstration

Pour n ≥ 0 on a n + 1 > 0, d'où B_n+1,0 = 0, donc

${\begin{aligned}B_{n+1}(x_{1},\dots ,x_{n+1})&=\sum _{i=0}^{n+1}B_{n+1,i}(x_{1},\dots ,x_{n-i+2})\\&=0+\sum _{i=1}^{n+1}B_{n+1,i}(x_{1},\dots ,x_{n-i+2})\\&{\underset {k=i-1}{=}}\sum _{k=0}^{n}B_{n+1,k+1}(x_{1},\dots ,x_{n-k+1})\\&=\sum _{k=0}^{n}\sum _{i=0}^{n-k}{\binom {n}{i}}x_{i+1}B_{n-i,k}(x_{1},\dots ,x_{n-i-k+1})\\&=\sum _{i=0}^{n}\sum _{k=0}^{n-i}{\binom {n}{i}}x_{i+1}B_{n-i,k}(x_{1},\dots ,x_{n-i-k+1})\\&=\sum _{i=0}^{n}{\binom {n}{i}}x_{i+1}B_{n-i}(x_{1},\dots ,x_{n-i})\end{aligned}}$

La seconde forme s'obtient immédiatement par le changement de variable i → n − i.

Démonstration

La matrice ${\begin{pmatrix}{j-1 \choose i-1}x_{j-i+1}-\delta _{j-i+1}\end{pmatrix}}$ étant une matrice de Hessenberg, on peut développer son déterminant selon la dernière colonne, donnant la formule de récurrence.

Valeurs particulières

• $B_{n,k}(1,1,\dots ,1)={\begin{Bmatrix}n\\k\end{Bmatrix}}$ (nombre de Stirling de seconde espèce non signé)
• $B_{n,k}(1,-1,1,-1,\dots ,(-1)^{n-k})=(-1)^{n-k}{\begin{Bmatrix}n\\k\end{Bmatrix}}$ (nombre de Stirling de seconde espèce signé)
• $B_{n}(1,1,\dots ,1)=B_{n}$ (nombre de Bell)
• $B_{n,k}(0!,1!,\dots ,(n-k)!)={\begin{bmatrix}n\\k\end{bmatrix}}$ (nombre de Stirling de première espèce non signé)
• $B_{n,k}(0!,-1!,2!,-3!,\dots ,(-1)^{n-k}(n-k)!)=(-1)^{n-k}{\begin{bmatrix}n\\k\end{bmatrix}}$ (nombre de Stirling de première espèce signé)
• $B_{n}(0!,1!,\dots ,(n-1)!)=n!$
• $B_{n}(0!,-1!,2!,-3!,\dots ,(-1)^{n-1}(n-1)!)=\delta _{n,0}+\delta _{n,1}$
• $B_{n}(-0!,-1!,\dots ,-(n-1)!)=\delta _{n,0}-\delta _{n,1}$
• $B_{n,k}(1!,2!,\dots ,(n-k+1)!)=\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor$ (nombre de Lah non signé)
• $B_{n,k}(-1!,2!,-3!,4!,\dots ,(-1)^{n-k+1}(n-k+1)!)=(-1)^{n}\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor$ (nombre de Lah signé)

Type binomial

$B_{n}(x_{1}+y_{1},\dots ,x_{n}+y_{n})=\sum _{k=0}^{n}{\binom {n}{k}}B_{n-k}(x_{1},\dots ,x_{n-k})B_{k}(y_{1},\dots ,y_{k})$

avec B₀ = 1.

Réciproque

Soit f une fonction infiniment dérivable en un point a et de réciproque f ^-1, alors :

$y_{n}=\sum _{k=1}^{n}f^{(k)}(a)B_{n,k}(x_{1},\dots ,x_{n-k+1})\Leftrightarrow x_{n}=\sum _{k=1}^{n}[f^{-1}]^{(k)}(f(a))B_{n,k}(y_{1},\dots ,y_{n-k+1})$

Démonstration

Posons

$x(t)=\sum _{n=1}^{\infty }x_{n}{\frac {t^{n}}{n!}}$ (on vérifie que $x_{0}=x(0)=0$)

ainsi que

$g(t)=f(t+a)-f(a)$

d'où

$g(0)=0{\text{ et }}\forall n\geq 1,g^{(n)}(0)=f^{(n)}(a)$

soit

$g(t)=\sum _{n=1}^{\infty }f^{(n)}(a){\frac {t^{n}}{n!}}$

En appliquant la formule de composition des séries formelles exponentielles (voir plus haut) à $y=g\circ x$, on obtient

${\begin{aligned}y(t)&=\sum _{n=0}^{\infty }\sum _{k=0}^{n}g_{k}B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}\\&=g_{0}+\sum _{n=1}^{\infty }\sum _{k=1}^{n}f^{(k)}(a)B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=1}^{\infty }y_{n}{\frac {t^{n}}{n!}}\end{aligned}}$

avec

$y_{n}=\sum _{k=1}^{n}f^{(k)}(a)B_{n,k}(x_{1},\dots ,x_{n-k+1})$

Calculons maintenant la réciproque de g :

$t=g(g^{-1}(t))=f(g^{-1}(t)+a)-f(a)$

donne

$g^{-1}(t)=f^{-1}(t+f(a))-a$

d'où

$g^{-1}(0)=0{\text{ et }}\forall n\geq 1,[g^{-1}]^{(n)}(0)=[f^{-1}]^{(n)}(f(a))$

soit

$g^{-1}(t)=\sum _{n=1}^{\infty }[f^{-1}]^{(n)}(f(a)){\frac {t^{n}}{n!}}$

En appliquant la formule de composition des séries formelles exponentielles à $x=g^{-1}\circ y$, on obtient

${\begin{aligned}x(t)&=\sum _{n=0}^{\infty }\sum _{k=0}^{n}(g^{-1})_{k}B_{n,k}(y_{1},\dots ,y_{n-k+1}){\frac {t^{n}}{n!}}\\&=(g^{-1})_{0}+\sum _{n=1}^{\infty }\sum _{k=1}^{n}[f^{-1}]^{(k)}(f(a))B_{n,k}(y_{1},\dots ,y_{n-k+1}){\frac {t^{n}}{n!}}\end{aligned}}$

d'où

$x_{n}=[f^{-1}]^{(k)}(f(a))B_{n,k}(y_{1},\dots ,y_{n-k+1})$

Cas particuliers

En prenant f (x) = e^x (soit f ^–1(x) = ln(x)) infiniment dérivable en 0, on a :

• $f^{(k)}(0)=1$
• $[f^{-1}]^{(k)}(f(0))=(-1)^{k-1}(k-1)!$

d’où :

$y_{n}=\sum _{k=1}^{n}B_{n,k}(x_{1},\dots ,x_{n-k+1})\Leftrightarrow x_{n}=\sum _{k=1}^{n}(-1)^{k-1}(k-1)!B_{n,k}(y_{1},\dots ,y_{n-k+1})$

soit :

$x_{n}=\sum _{k=1}^{n}(-1)^{k-1}(k-1)!B_{n,k}[B_{1}(x_{1}),\dots ,B_{n-k+1}(x_{1},\dots ,x_{n-k+1})]$

En prenant f (x) = x^α avec α ≠ 0 (soit f ^–1(x) = x^1/α) infiniment dérivable en 1, on a :

• $f^{(k)}(1)=\alpha ^{\underline {k}}$
• $[f^{-1}]^{(k)}(f(1))=\left({\frac {1}{\alpha }}\right)^{\underline {k}}$

avec .^k la factorielle décroissante, d’où :

$y_{n}=\sum _{k=1}^{n}\alpha ^{\underline {k}}B_{n,k}(x_{1},\dots ,x_{n-k+1})\Leftrightarrow x_{n}=\sum _{k=1}^{n}\left({\frac {1}{\alpha }}\right)^{\underline {k}}B_{n,k}(y_{1},\dots ,y_{n-k+1})$

Composition

Soient :

$f(t)=\sum _{n=0}^{\infty }f_{n}{\frac {t^{n}}{n!}}$

$g(t)=\sum _{n=1}^{\infty }g_{n}{\frac {t^{n}}{n!}}$ (on note que $g_{0}=g(0)=0$)

$(f\circ g)(t)=h(t)=\sum _{n=0}^{\infty }h_{n}{\frac {t^{n}}{n!}}$

Alors :

$B_{n,k}(h_{1},\dots ,h_{n-k+1})=\sum _{i=k}^{n}B_{i,k}(f_{1},\dots ,f_{i-k+1})B_{n,i}(g_{1},\dots ,g_{n-i+1})$

En posant les matrices $F={\begin{pmatrix}B_{j-1,i-1}(f_{1},\dots ,f_{j-i+1})\end{pmatrix}}$ (triangulaire supérieure) ainsi que $G$ et $H$ de manière similaire, on a alors :

$H=FG$

Démonstration

Posons

$f_{+}(t)=f(t)-f_{0}=\sum _{n=1}^{\infty }f_{n}{\frac {t^{n}}{n!}}$, avec donc $f_{+}(0)=0$

On a

$h_{0}=h(0)=f(g(0))=f(0)=f_{0}$

d'où

$h_{+}(t)=(f_{+}\circ g)(t)=f(g(t))-f_{0}=h(t)-h_{0}=\sum _{n=1}^{\infty }h_{n}{\frac {t^{n}}{n!}}$, avec donc $h_{+}(0)=0$

Posons

$e_{k}(t)={\frac {t^{k}}{k!}}=\sum _{n=0}^{\infty }\delta _{n,k}{\frac {t^{n}}{n!}}$

(Note : la notation $e_{k}$ pour cette fonction vient de la théorie des espèces combinatoires (en).) Par associativité de la composition de fonctions, on a $e_{k}\circ h_{+}=(e_{k}\circ f_{+})\circ g$, dont on évaluera chaque membre. En appliquant la formule de composition des séries formelles exponentielles (voir plus haut), on obtient

${\begin{aligned}(e_{k}\circ h_{+})(t)&=\sum _{n=0}^{\infty }\sum _{i=0}^{n}(e_{k})_{i}B_{n,i}(h_{1},\dots ,h_{n-i+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=0}^{\infty }\sum _{i=0}^{n}\delta _{i,k}B_{n,i}(h_{1},\dots ,h_{n-i+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=0}^{\infty }B_{n,k}(h_{1},\dots ,h_{n-k+1}){\frac {t^{n}}{n!}}\end{aligned}}$

De même, en posant $\ell _{k}=e_{k}\circ f_{+}$, on a

${\begin{aligned}\ell _{k}(t)&=\sum _{n=0}^{\infty }B_{n,k}(f_{1},\dots ,f_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=0}^{\infty }(\ell _{k})_{n}{\frac {t^{n}}{n!}}\end{aligned}}$

En appliquant une dernière fois la formule de composition, on obtient

${\begin{aligned}(\ell _{k}\circ g)(t)&=\sum _{n=0}^{\infty }\sum _{i=0}^{n}(\ell _{k})_{i}B_{n,i}(g_{1},\dots ,g_{n-i+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=0}^{\infty }\sum _{i=0}^{n}B_{i,k}(f_{1},\dots ,f_{i-k+1})B_{n,i}(g_{1},\dots ,g_{n-i+1}){\frac {t^{n}}{n!}}\end{aligned}}$

L'égalité $e_{k}\circ h_{+}=\ell _{k}\circ g$ donne

$\sum _{n=0}^{\infty }B_{n,k}(h_{1},\dots ,h_{n-k+1}){\frac {t^{n}}{n!}}=\sum _{n=0}^{\infty }\sum _{i=0}^{n}B_{i,k}(f_{1},\dots ,f_{i-k+1})B_{n,i}(g_{1},\dots ,g_{n-i+1}){\frac {t^{n}}{n!}}$

Ensuite, par unicité de la décomposition des séries formelles exponentielles sur la base ${\begin{pmatrix}{\frac {t^{n}}{n!}}\end{pmatrix}}_{n\in \mathbf {N} }$, on obtient

$B_{n,k}(h_{1},\dots ,h_{n-k+1})=\sum _{i=0}^{n}B_{i,k}(f_{1},\dots ,f_{i-k+1})B_{n,i}(g_{1},\dots ,g_{n-i+1})$

Enfin, comme $i<k\Rightarrow B_{i,k}=0$, on peut changer la borne inférieure de la somme pour obtenir

$B_{n,k}(h_{1},\dots ,h_{n-k+1})=\sum _{i=k}^{n}B_{i,k}(f_{1},\dots ,f_{i-k+1})B_{n,i}(g_{1},\dots ,g_{n-i+1})$

Cas particuliers

En prenant $f(t)=\exp(t)$ et $g(t)=\ln(1+t)$, on obtient :

$\sum _{i=k}^{n}(-1)^{n-i}{\begin{Bmatrix}i\\k\end{Bmatrix}}{\begin{bmatrix}n\\i\end{bmatrix}}=\delta _{n,k}$

En prenant $f(t)=\ln(1+t)$ et $g(t)=\exp(t)-1$, on obtient :

$\sum _{i=k}^{n}(-1)^{i-k}{\begin{bmatrix}i\\k\end{bmatrix}}{\begin{Bmatrix}n\\i\end{Bmatrix}}=\delta _{n,k}$

En prenant $f(t)=\exp(t)$ et $g(t)=-\ln(1-t)$, on obtient :

$\sum _{i=k}^{n}{\begin{Bmatrix}i\\k\end{Bmatrix}}{\begin{bmatrix}n\\i\end{bmatrix}}=\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor$

En prenant $f(t)={\frac {1}{1-t}}$ et $g(t)={\frac {t}{1+t}}$, on obtient :

$\sum _{i=k}^{n}(-1)^{n-i}\left\lfloor {\begin{matrix}i\\k\end{matrix}}\right\rfloor \left\lfloor {\begin{matrix}n\\i\end{matrix}}\right\rfloor =\delta _{n,k}$

Factorielle décroissante

$\forall (a,b)\in \mathbb {N} ^{2},\sum _{k=1}^{n}a^{\underline {k}}B_{n,k}(b^{\underline {1}},\dots ,b^{\underline {n}})=(ab)^{\underline {k}}$

avec .^k la factorielle décroissante.

Comportement d’échelle

Polynômes de Bell partiels

Cas général

$B_{n,k}(\alpha \beta x_{1},\dots ,\alpha \beta ^{n-k+1}x_{n-k+1})=\alpha ^{k}\beta ^{n}B_{n,k}(x_{1},\dots ,x_{n-k+1})$

Cas particuliers

$B_{n,k}(\alpha x_{1},\dots ,\alpha x_{n-k+1})=\alpha ^{k}B_{n,k}(x_{1},\dots ,x_{n-k+1})$

$B_{n,k}(\alpha x_{1},\dots ,\alpha ^{n-k+1}x_{n-k+1})=\alpha ^{n}B_{n,k}(x_{1},\dots ,x_{n-k+1})$

Polynômes de Bell complets

Cas général

$B_{n}(\alpha \beta x_{1},\dots ,\alpha \beta ^{n}x_{n})=\beta ^{n}\sum _{k=0}^{n}\alpha ^{k}B_{n,k}(x_{1},\dots ,x_{n-k+1})$

Cas particuliers

$B_{n}(\alpha x_{1},\dots ,\alpha x_{n})=\sum _{k=0}^{n}\alpha ^{k}B_{n,k}(x_{1},\dots ,x_{n-k+1})$

$B_{n}(\alpha x_{1},\dots ,\alpha ^{n}x_{n})=\alpha ^{n}B_{n}(x_{1},\dots ,x_{n})$

Autre expression

$B_{n}(\alpha x_{1},\dots ,\alpha x_{n})=\sum _{k=0}^{n}\alpha ^{\underline {k}}B_{n,k}[B_{1}(x_{1}),\dots ,B_{n-k+1}(x_{1},x_{2},\dots ,x_{n-k+1})]$

avec .^k la factorielle décroissante.

Démonstration

Posons

$f(t)=(1+t)^{\alpha }=\sum _{n=0}^{\infty }\alpha ^{\underline {n}}{\frac {t^{n}}{n!}}$

$g(t)=\exp(t)-1=\sum _{n=1}^{\infty }1{\frac {t^{n}}{n!}}$ (on vérifie que $g_{0}=g(0)=0$)

$x(t)=\sum _{n=1}^{\infty }x_{n}{\frac {t^{n}}{n!}}$ (on vérifie que $x_{0}=x(0)=0$)

Par associativité de la composition de fonctions, on a $(f\circ g)\circ x=f\circ (g\circ x)$, dont on évaluera chaque membre.

Membre de gauche : $(f\circ g)\circ x$

Posons $h=f\circ g$, d'où

$h(t)=\exp(t)^{\alpha }=\exp(\alpha t)=\sum _{n=0}^{\infty }\alpha ^{n}{\frac {t^{n}}{n!}}$

En appliquant la formule de composition des séries formelles exponentielles (voir plus haut), on obtient

${\begin{aligned}(h\circ x)(t)&=\sum _{n=0}^{\infty }\sum _{k=0}^{n}h_{k}B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=0}^{\infty }\sum _{k=0}^{n}\alpha ^{k}B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=0}^{\infty }\sum _{k=0}^{n}B_{n,k}(\alpha x_{1},\dots ,\alpha x_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=0}^{\infty }B_{n}(\alpha x_{1},\dots ,\alpha x_{n}){\frac {t^{n}}{n!}}\end{aligned}}$

Membre de droite : $f\circ (g\circ x)$

Posons $y=g\circ x$, d'où, par application de la formule de composition

${\begin{aligned}y(t)&=\sum _{n=0}^{\infty }\sum _{k=0}^{n}g_{k}B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}\\&=g_{0}B_{0,0}(x_{1})+\sum _{n=1}^{\infty }\sum _{k=0}^{n}B_{n,k}(x_{1},\dots ,x_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=1}^{\infty }B_{n}(x_{1},\dots ,x_{n}){\frac {t^{n}}{n!}}\end{aligned}}$

Puis, en appliquant une dernière fois la formule de composition, on obtient

${\begin{aligned}(f\circ y)(t)&=\sum _{n=0}^{\infty }\sum _{k=0}^{n}f_{k}B_{n,k}(y_{1},\dots ,y_{n-k+1}){\frac {t^{n}}{n!}}\\&=\sum _{n=0}^{\infty }\sum _{k=0}^{n}\alpha ^{\underline {k}}B_{n,k}(B_{1}(x_{1}),\dots ,B_{n-k+1}(x_{1},\dots ,x_{n-k+1})){\frac {t^{n}}{n!}}\end{aligned}}$

Résultat

L'égalité $h\circ x=f\circ y$ donne

$\sum _{n=0}^{\infty }B_{n}(\alpha x_{1},\dots ,\alpha x_{n}){\frac {t^{n}}{n!}}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}\alpha ^{\underline {k}}B_{n,k}(B_{1}(x_{1}),\dots ,B_{n-k+1}(x_{1},\dots ,x_{n-k+1})){\frac {t^{n}}{n!}}$

Enfin, par unicité de la décomposition des séries formelles exponentielles sur la base ${\begin{pmatrix}{\frac {t^{n}}{n!}}\end{pmatrix}}_{n\in \mathbf {N} }$, on obtient

$B_{n}(\alpha x_{1},\dots ,\alpha x_{n})=\sum _{k=0}^{n}\alpha ^{\underline {k}}B_{n,k}(B_{1}(x_{1}),\dots ,B_{n-k+1}(x_{1},\dots ,x_{n-k+1}))$

Identité de convolution

Pour des suites x_n, y_n, n = 1, 2, …, on peut définir un produit de convolution par :

$(x\diamondsuit y)_{n}=\sum _{j=1}^{n-1}{n \choose j}x_{j}y_{n-j}$

(les bornes de sommation étant 1 et n − 1, et non 0 et n).

Soit $x_{n}^{k\diamondsuit }$ le n-ème terme de la suite $\displaystyle \underbrace {x\diamondsuit \cdots \diamondsuit x} _{k\ \mathrm {facteurs} }$

Alors :

$B_{n,k}(x_{1},\dots ,x_{n-k+1})={\frac {x_{n}^{k\diamondsuit }}{k!}}$

Applications

Formule de Faà di Bruno

La formule de Faà di Bruno peut être énoncée à l'aide des polynômes de Bell de la manière suivante :

$(f\circ g)^{(n)}(x)=\sum _{k=0}^{n}(f^{(k)}\circ g)(x)\,B_{n,k}\left(g'(x),\dots ,g^{(n-k+1)}(x)\right)$

Moments et cumulants

Pour une variable aléatoire réelle dont le moment ordinaire m_r d’ordre r existe, on a :

$m_{r}=B_{r}(\kappa _{1},\dots ,\kappa _{r})$

avec κ_i les cumulants.

Représentations de suites polynomiales

Pour toute suite a₁, a₂, … de scalaires, soit :

$p_{n}(x)=\sum _{k=1}^{n}B_{n,k}(a_{1},\dots ,a_{n-k+1})x^{k}$

Cette suite de polynômes est de type binomial, c'est-à-dire qu'elle satisfait l'identité binomiale suivante :

$p_{n}(x+y)=\sum _{k=0}^{n}{n \choose k}p_{k}(x)p_{n-k}(y)$

pour n ≥ 0.

En fait, on a également la réciproque :

Théorème — Toutes les suites de polynômes de type binomial peuvent s’exprimer sous la forme faisant intervenir les polynômes de Bell.

Si nous posons

$h(x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{n!}}$

en considérant cette série comme une série formelle, alors pour tout n :

$h^{-1}\left({\frac {\mathrm {d} }{\mathrm {d} x}}\right)p_{n}(x)=np_{n-1}(x)$

Notes et références

• (en) Eric Temple Bell, « Partition Polynomials », Ann. Math., vol. 29, n^os 1/4,‎ 1927-1928, p. 38-46 (DOI 10.2307/1967979)
• (en) Eric Temple Bell, « Exponential Polynomials », Ann. Math., vol. 35, n^o 2,‎ 1934, p. 258-277 (DOI 10.2307/1968431)
• (en) Louis Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Reidel Publishing Company, Dordrecht-Holland/Boston-U.S., 1974
• (en) Steven Roman (en), The Umbral Calculus, Dover Publications

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bell polynomials » (voir la liste des auteurs).

Articles connexes

• Calcul ombral
• Indicateur de cycles du groupe symétrique