Polynôme de Bell

En mathématiques, et plus précisément en combinatoire, un polynôme de Bell, nommé ainsi d'après le mathématicien Eric Temple Bell, est défini par:

B n , k ( x 1 , x 2 , … , x n − k + 1 ) = ∑ n ! j 1 ! j 2 ! ⋯ j n − k + 1 ! ( x 1 1 ! ) j 1 ( x 2 2 ! ) j 2 ⋯ ( x n − k + 1 ( n − k + 1 ) ! ) j n − k + 1 {\displaystyle B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})=\sum {n! \over j_{1}!j_{2}!\cdots j_{n-k+1}!}\left({x_{1} \over 1!}\right)^{j_{1}}\left({x_{2} \over 2!}\right)^{j_{2}}\cdots \left({x_{n-k+1} \over (n-k+1)!}\right)^{j_{n-k+1}}}

où la somme porte sur toutes les suites j1, j2, j3, …, jn−k+1 d'entiers naturels telles que :

j 1 + j 2 + ⋯ + j n − k + 1 = k {\displaystyle j_{1}+j_{2}+\cdots +j_{n-k+1}=k} et j 1 + 2 j 2 + 3 j 3 + ⋯ + ( n − k + 1 ) j n − k + 1 = n {\displaystyle j_{1}+2j_{2}+3j_{3}+\cdots +(n-k+1)j_{n-k+1}=n}

Polynômes de Bell complets

La somme

B n ( x 1 , x 2 , … , x n ) = ∑ k = 1 n B n , k ( x 1 , x 2 , … , x n − k + 1 ) {\displaystyle B_{n}(x_{1},x_{2},\dots ,x_{n})=\sum _{k=1}^{n}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})}

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

B n ( x 1 , x 2 , … , x n ) = | ( 0 0 ) x 1 ( 1 0 ) x 2 ( 2 0 ) x 3 ( 3 0 ) x 4 ⋯ ( n − 2 0 ) x n − 1 ( n − 1 0 ) x n − 1 ( 1 1 ) x 1 ( 2 1 ) x 2 ( 3 1 ) x 3 ⋯ ( n − 2 1 ) x n − 2 ( n − 1 1 ) x n − 1 0 − 1 ( 2 2 ) x 1 ( 3 2 ) x 2 ⋯ ( n − 2 2 ) x n − 3 ( n − 1 2 ) x n − 2 0 0 − 1 ( 3 3 ) x 1 ⋯ ( n − 2 3 ) x n − 4 ( n − 1 3 ) x n − 3 ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ 0 0 0 0 ⋯ ( n − 2 n − 2 ) x 1 ( n − 1 n − 2 ) x 2 0 0 0 0 ⋯ − 1 ( n − 1 n − 1 ) x 1 | = | ( j − 1 i − 1 ) x j − i + 1 − δ j − i + 1 | {\displaystyle B_{n}(x_{1},x_{2},\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 Bn est le déterminant est une matrice de Hessenberg.

Interprétation combinatoire

Si l'entier n est partitionné en une somme dans laquelle "1" apparait j1 fois, "2" apparait j2 fois, et ainsi de suite, alors le nombre de partitions d'un ensemble à n éléments qui correspondent à cette partition de l'entier n quand on ne distingue plus les éléments de l'ensemble est le coefficient correspondant du polynôme.

Exemples

Par exemple, nous avons :

B 6 , 2 ( x 1 , x 2 , x 3 , x 4 , x 5 ) = 6 x 5 x 1 + 15 x 4 x 2 + 10 x 3 2 {\displaystyle 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 ) = 15 x 4 x 1 2 + 60 x 3 x 2 x 1 + 15 x 2 3 {\displaystyle 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.

Propriétés

Formule de récurrence

B n + 1 ( x 1 , x 2 , … , x n + 1 ) = ∑ k = 0 n ( n k ) B n − k ( x 1 , x 2 , … , x n − k ) x k + 1 = ∑ k = 0 n ( n k ) B k ( x 1 , x 2 , … , x k ) x n − k + 1 {\displaystyle B_{n+1}(x_{1},x_{2},\dots ,x_{n+1})=\sum _{k=0}^{n}{\binom {n}{k}}B_{n-k}(x_{1},x_{2},\dots ,x_{n-k})\,x_{k+1}=\sum _{k=0}^{n}{\binom {n}{k}}B_{k}(x_{1},x_{2},\dots ,x_{k})\,x_{n-k+1}}
avec B0 = 1.
Démonstration

La matrice ( ( j − 1 i − 1 ) x j − i + 1 − δ j − i + 1 ) {\displaystyle {\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.

Nombre de Stirling de seconde espèce

B n , k ( 1 , 1 , … , 1 ) = { n k } {\displaystyle B_{n,k}(1,1,\dots ,1)={\begin{Bmatrix}n\\k\end{Bmatrix}}}

Nombre de Bell

B n ( 1 , 1 , … , 1 ) = B n {\displaystyle B_{n}(1,1,\dots ,1)=B_{n}}
Démonstration
B n ( 1 , 1 , … , 1 ) = ∑ k = 1 n B n , k ( 1 , 1 , … , 1 ) = ∑ k = 1 n { n k } = B n {\displaystyle B_{n}(1,1,\dots ,1)=\sum _{k=1}^{n}B_{n,k}(1,1,\dots ,1)=\sum _{k=1}^{n}{\begin{Bmatrix}n\\k\end{Bmatrix}}=B_{n}}

Nombre de Stirling de première espèce (non signés)

B n , k ( 0 ! , 1 ! , … , ( n − k ) ! ) = [ n k ] {\displaystyle B_{n,k}(0!,1!,\dots ,(n-k)!)={\begin{bmatrix}n\\k\end{bmatrix}}}

Nombre de Lah

B n , k ( 1 ! , 2 ! , … , ( n − k + 1 ) ! ) = ⌊ n k ⌋ {\displaystyle B_{n,k}(1!,2!,\dots ,(n-k+1)!)=\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor }

Factorielle

B n ( 0 , 1 , … , n − 1 ) = ( n − 1 ) ! {\displaystyle B_{n}(0,1,\dots ,n-1)=(n-1)!} pour n ≥ 1.
B n ( 0 ! , 1 ! , … , ( n − 1 ) ! ) = n ! {\displaystyle B_{n}(0!,1!,\dots ,(n-1)!)=n!}
B n ( − 0 ! , − 1 ! , … , − ( n − 1 ) ! ) = 0 {\displaystyle B_{n}(-0!,-1!,\dots ,-(n-1)!)=0}

Dernier argument

  • B n , 1 ( x 1 , x 2 , … , x n ) = x n {\displaystyle B_{n,1}(x_{1},x_{2},\dots ,x_{n})=x_{n}}
  • ∀ k > 1 , B n , k ( x 1 , x 2 , … , x n − k + 1 , x n − k + 2 , … , x n ) = B n , k ( x 1 , x 2 , … , x n − k + 1 ) = B n , k ( x 1 , x 2 , … , x n − k + 1 , 0 , … , 0 ) {\displaystyle \forall k>1,B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1},x_{n-k+2},\dots ,x_{n})=B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})=B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1},0,\dots ,0)}
  • B n ( x 1 , x 2 , … , x n − 1 , x n ) = B n ( x 1 , x 2 , … , x n − 1 , 0 ) + x n {\displaystyle B_{n}(x_{1},x_{2},\dots ,x_{n-1},x_{n})=B_{n}(x_{1},x_{2},\dots ,x_{n-1},0)+x_{n}}

Type binomial

Article détaillé : Type binomial.
B n ( x 1 + y 1 , x 2 + y 2 , … , x n + y n ) = ∑ k = 0 n ( n k ) B n − k ( x 1 , x 2 , … , x n − k ) B k ( y 1 , y 2 , … , y k ) {\displaystyle B_{n}(x_{1}+y_{1},x_{2}+y_{2},\dots ,x_{n}+y_{n})=\sum _{k=0}^{n}{\binom {n}{k}}B_{n-k}(x_{1},x_{2},\dots ,x_{n-k})B_{k}(y_{1},y_{2},\dots ,y_{k})}

avec B0 = 1.

Réciproque

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

y n = ∑ k = 1 n [ f ] x = a ( k ) B n , k ( x 1 , x 2 , … , x n − k + 1 ) ⇔ x n = ∑ k = 1 n [ f − 1 ] x = f ( a ) ( k ) B n , k ( y 1 , y 2 , … , y n − k + 1 ) {\displaystyle y_{n}=\sum _{k=1}^{n}[f]_{x=a}^{(k)}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})\Leftrightarrow x_{n}=\sum _{k=1}^{n}[f^{-1}]_{x=f(a)}^{(k)}B_{n,k}(y_{1},y_{2},\dots ,y_{n-k+1})} [1]

Cas particuliers

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

  • [ f ] x = 0 ( k ) = 1 {\displaystyle [f]_{x=0}^{(k)}=1}
  • [ f − 1 ] x = f ( 0 ) ( k ) = ( − 1 ) k − 1 ( k − 1 ) ! {\displaystyle [f^{-1}]_{x=f(0)}^{(k)}=(-1)^{k-1}(k-1)!}

d’où :

y n = ∑ k = 1 n B n , k ( x 1 , x 2 , … , x n − k + 1 ) ⇔ x n = ∑ k = 1 n ( − 1 ) k − 1 ( k − 1 ) ! B n , k ( y 1 , y 2 , … , y n − k + 1 ) {\displaystyle y_{n}=\sum _{k=1}^{n}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})\Leftrightarrow x_{n}=\sum _{k=1}^{n}(-1)^{k-1}(k-1)!B_{n,k}(y_{1},y_{2},\dots ,y_{n-k+1})}

soit :

x n = ∑ k = 1 n ( − 1 ) k − 1 ( k − 1 ) ! B n , k [ B 1 ( x 1 ) , B 2 ( x 1 , x 2 ) , … , B n − k + 1 ( x 1 , x 2 , … , x n − k + 1 ) ] {\displaystyle x_{n}=\sum _{k=1}^{n}(-1)^{k-1}(k-1)!B_{n,k}[B_{1}(x_{1}),B_{2}(x_{1},x_{2}),\dots ,B_{n-k+1}(x_{1},x_{2},\dots ,x_{n-k+1})]}


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

  • [ f ] x = 1 ( k ) = α k _ {\displaystyle [f]_{x=1}^{(k)}=\alpha ^{\underline {k}}}
  • [ f − 1 ] x = f ( 1 ) ( k ) = ( 1 α ) k _ {\displaystyle [f^{-1}]_{x=f(1)}^{(k)}=\left({\frac {1}{\alpha }}\right)^{\underline {k}}}

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

y n = ∑ k = 1 n α k _ B n , k ( x 1 , x 2 , … , x n − k + 1 ) ⇔ x n = ∑ k = 1 n ( 1 α ) k _ B n , k ( y 1 , y 2 , … , y n − k + 1 ) {\displaystyle y_{n}=\sum _{k=1}^{n}\alpha ^{\underline {k}}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})\Leftrightarrow x_{n}=\sum _{k=1}^{n}\left({\frac {1}{\alpha }}\right)^{\underline {k}}B_{n,k}(y_{1},y_{2},\dots ,y_{n-k+1})}

Factorielle décroissante

∀ ( a , b ) ∈ N 2 , ∑ k = 1 n a k _ B n , k ( b 1 _ , b 2 _ , … , b n _ ) = ( a b ) k _ {\displaystyle \forall (a,b)\in \mathbb {N} ^{2},\sum _{k=1}^{n}a^{\underline {k}}B_{n,k}(b^{\underline {1}},b^{\underline {2}},\dots ,b^{\underline {n}})=(ab)^{\underline {k}}} [2]

avec .k la factorielle décroissante.

Comportement d’échelle

Polynômes de Bell partiels

Cas général
B n , k ( α β x 1 , α β 2 x 2 , … , α β n − k + 1 x n − k + 1 ) = α k β n B n , k ( x 1 , x 2 , … , x n − k + 1 ) {\displaystyle B_{n,k}(\alpha \beta x_{1},\alpha \beta ^{2}x_{2},\dots ,\alpha \beta ^{n-k+1}x_{n-k+1})=\alpha ^{k}\beta ^{n}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})}
Cas particuliers
B n , k ( α x 1 , α x 2 , … , α x n − k + 1 ) = α k B n , k ( x 1 , x 2 , … , x n − k + 1 ) {\displaystyle B_{n,k}(\alpha x_{1},\alpha x_{2},\dots ,\alpha x_{n-k+1})=\alpha ^{k}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})}
B n , k ( α x 1 , α 2 x 2 , … , α n − k + 1 x n − k + 1 ) = α n B n , k ( x 1 , x 2 , … , x n − k + 1 ) {\displaystyle B_{n,k}(\alpha x_{1},\alpha ^{2}x_{2},\dots ,\alpha ^{n-k+1}x_{n-k+1})=\alpha ^{n}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})}

Polynômes de Bell complets

Cas général
B n ( α β x 1 , α β 2 x 2 , … , α β n x n ) = β n ∑ k = 1 n α k B n , k ( x 1 , x 2 , … , x n − k + 1 ) {\displaystyle B_{n}(\alpha \beta x_{1},\alpha \beta ^{2}x_{2},\dots ,\alpha \beta ^{n}x_{n})=\beta ^{n}\sum _{k=1}^{n}\alpha ^{k}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})}
Cas particuliers
B n ( α x 1 , α x 2 , … , α x n ) = ∑ k = 1 n α k B n , k ( x 1 , x 2 , … , x n − k + 1 ) {\displaystyle B_{n}(\alpha x_{1},\alpha x_{2},\dots ,\alpha x_{n})=\sum _{k=1}^{n}\alpha ^{k}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})}
B n ( α x 1 , α 2 x 2 , … , α n x n ) = α n B n ( x 1 , x 2 , … , x n ) {\displaystyle B_{n}(\alpha x_{1},\alpha ^{2}x_{2},\dots ,\alpha ^{n}x_{n})=\alpha ^{n}B_{n}(x_{1},x_{2},\dots ,x_{n})}
Autre expression
B n ( α x 1 , α x 2 , … , α x n ) = ∑ k = 1 n α k _ B n , k [ B 1 ( x 1 ) , B 2 ( x 1 , x 2 ) , … , B n − k + 1 ( x 1 , x 2 , … , x n − k + 1 ) ] {\displaystyle B_{n}(\alpha x_{1},\alpha x_{2},\dots ,\alpha x_{n})=\sum _{k=1}^{n}\alpha ^{\underline {k}}B_{n,k}[B_{1}(x_{1}),B_{2}(x_{1},x_{2}),\dots ,B_{n-k+1}(x_{1},x_{2},\dots ,x_{n-k+1})]}

avec .k la factorielle décroissante.

Identité de convolution

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

( x ♢ y ) n = ∑ j = 1 n − 1 ( n j ) x j y n − j {\displaystyle (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 ♢ {\displaystyle x_{n}^{k\diamondsuit }} le n-ème terme de la suite x ♢ ⋯ ♢ x ⏟ k   f a c t e u r s {\displaystyle \displaystyle \underbrace {x\diamondsuit \cdots \diamondsuit x} _{k\ \mathrm {facteurs} }}

Alors :

B n , k ( x 1 , … , x n − k + 1 ) = x n k ♢ k ! {\displaystyle B_{n,k}(x_{1},\dots ,x_{n-k+1})={x_{n}^{k\diamondsuit } \over 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 :

d n d x n f ( g ( x ) ) = ∑ k = 1 n f ( k ) ( g ( x ) ) B n , k ( g ′ ( x ) , g ″ ( x ) , … , g ( n − k + 1 ) ( x ) ) {\displaystyle {d^{n} \over dx^{n}}f(g(x))=\sum _{k=1}^{n}f^{(k)}(g(x))B_{n,k}\left(g'(x),g''(x),\dots ,g^{(n-k+1)}(x)\right)}

De même, on peut donner une version de cette formule concernant les séries formelles : supposons que

f ( x ) = ∑ n = 1 ∞ a n n ! x n {\displaystyle f(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}} et g ( x ) = ∑ n = 1 ∞ b n n ! x n {\displaystyle g(x)=\sum _{n=1}^{\infty }{b_{n} \over n!}x^{n}}

Alors :

g ( f ( x ) ) = ∑ n = 1 ∞ ∑ k = 1 n b k B n , k ( a 1 , … , a n − k + 1 ) n ! x n {\displaystyle g(f(x))=\sum _{n=1}^{\infty }{\sum _{k=1}^{n}b_{k}B_{n,k}(a_{1},\dots ,a_{n-k+1}) \over n!}x^{n}}

Les polynômes de Bell complets apparaissent dans l’exponentielle d’une série formelle :

exp ⁡ ( ∑ n = 1 ∞ a n n ! x n ) = ∑ n = 0 ∞ B n ( a 1 , … , a n ) n ! x n {\displaystyle \exp \left(\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}\right)=\sum _{n=0}^{\infty }{B_{n}(a_{1},\dots ,a_{n}) \over n!}x^{n}}

Moments et cumulants

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

m r = B r ( κ 1 , κ 2 , … , κ r ) {\displaystyle m_{r}=B_{r}(\kappa _{1},\kappa _{2},\dots ,\kappa _{r})}

avec mr le moment ordinaire d’ordre r et κ1, κ2, …, κr les cumulants d’ordre 1 à r.

Représentations de suites polynomiales

Pour toute suite a1, a2, a3, … de scalaires, soit :

p n ( x ) = ∑ k = 1 n B n , k ( a 1 , … , a n − k + 1 ) x k {\displaystyle 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 ) = ∑ k = 0 n ( n k ) p k ( x ) p n − k ( y ) {\displaystyle 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 ) = ∑ n = 1 ∞ a n n ! x n {\displaystyle h(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}}

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

h − 1 ( d d x ) p n ( x ) = n p n − 1 ( x ) {\displaystyle h^{-1}\left({\mathrm {d} \over \mathrm {d} x}\right)p_{n}(x)=np_{n-1}(x)}

Notes et références

  1. ↑ (en) W.-S. Chaou, Leetsch C. Hsu, Peter J.-S. Shiue, “Application of Faà di Bruno’s formula in characterization of inverse relations”, dans Journal of Computational and Applied Mathematics, vol. 190, 2006, p. 151–169
  2. ↑ (en) Andrzej Korzeniowski, “Binomial Tails Domination for Random Graphs via Bell Polynomials”, dans JPSS, vol. 4, n° 1, 2006, p. 99-105
  • (en) Eric Temple Bell, « Partition Polynomials », Ann. Math., vol. 29, nos 1/4,‎ 1927-1928, p. 38-46 (DOI 10.2307/1967979)
  • (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

  • icône décorative Portail des mathématiques