Polynômes de Bell

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 donnés par :

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, …, jnk+1 d'entiers naturels telles que :

j_1+j_2+\cdots = k et j_1+2j_2+3j_3+\cdots=n

Polynômes de Bell complets[modifier | modifier le code]

La somme

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 Bnk 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, \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}
 = \begin{vmatrix} {j-1 \choose i-1} x_{j-i+1} - \delta_{j-i+1} \end{vmatrix}

avec δk le symbole de Kronecker. On notera avec intérêt que la matrice dont Bn est le déterminant est une matrice de Hessenberg.

Interprétation combinatoire[modifier | modifier le code]

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[modifier | modifier le code]

Par exemple, nous avons :

B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_5x_1+15x_4x_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_4x_1^2+60x_3x_2x_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[modifier | modifier le code]

Formule de récurrence[modifier | modifier le code]

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.

Nombre de Stirling de seconde espèce[modifier | modifier le code]

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

Nombre de Bell[modifier | modifier le code]

B_n(1, 1, \dots, 1) = B_n

Nombre de Lah[modifier | modifier le code]

B_{n,k}(1!, 2!, \dots, (n-k+1)!) = \left\lfloor \begin{matrix} n \\ k \end{matrix} \right\rfloor

Factorielle[modifier | modifier le code]

B_n(0, 1, \dots, n-1) = n!

pour n ≥ 2.

B_n(0!, 1!, \dots, (n-1)!) = n!
B_n(-0!, -1!, \dots, -(n-1)!) = 0

Dernier argument[modifier | modifier le code]

  • B_{n,1}(x_1, x_2, \dots, x_n) = x_n
  • \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, \dots, x_{n-1}, x_n) = B_n(x_1, x_2, \dots, x_{n-1}, 0) + x_n

Type binomial[modifier | modifier le code]

Article détaillé : Type binomial (en).
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[modifier | modifier le code]

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)}_{x=a} B_{n,k}(x_1, x_2, \dots, x_{n-k+1}) \Leftrightarrow x_n = \sum_{k=1}^n [f^{-1}]^{(k)}_{x=f(a)} B_{n,k}(y_1, y_2, \dots, y_{n-k+1})[1]

Cas particuliers[modifier | modifier le code]

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

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

d’où :

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 = \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]^{(k)}_{x=1} = \alpha^{\underline{k}}
  • [f^{-1}]^{(k)}_{x=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, 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[modifier | modifier le code]

\forall (a,b) \in \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[modifier | modifier le code]

Polynômes de Bell partiels[modifier | modifier le code]

Cas général
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}(\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}(\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[modifier | modifier le code]

Cas général
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(\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(\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(\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[modifier | modifier le code]

Pour des suites xn, yn, 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}) = {x_{n}^{k\diamondsuit} \over k!}

Applications[modifier | modifier le code]

Formule de Faà di Bruno[modifier | modifier le code]

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

{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)=\sum_{n=1}^\infty {a_n \over n!} x^n et g(x)=\sum_{n=1}^\infty {b_n \over n!} x^n

Alors :

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 (en) :

\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[modifier | modifier le code]

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

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[modifier | modifier le code]

Pour toute suite a1, a2, a3, … 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 (en), 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 \over n!} x^n

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

h^{-1}\left( {d \over dx}\right) p_n(x) = n p_{n-1}(x)

Note et références[modifier | modifier le code]

  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

Articles connexes[modifier | modifier le code]