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 ℕ^{2}, B_{n, k} (x_{1}, x_{2}, \dots) \overset{def}{=} n! \sum_{\begin{matrix} (m_{1}, m_{2}, \dots) \in ℕ^{ℕ^{*}} \\ {\begin{matrix} \sum_{i \in ℕ^{*}} m_{i} = k \\ \sum_{i \in ℕ^{*}} i \cdot m_{i} = n \end{matrix} \end{matrix}} \prod_{i \in ℕ^{*}} \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 ℕ^{n - k + 1} \\ {\begin{matrix} \sum_{i = 1}^{n - k + 1} m_{i} = k \\ \sum_{i = 1}^{n - k + 1} i \cdot m_{i} = n \end{matrix} \end{matrix}} \prod_{i = 1}^{n - k + 1} \frac{x_{i}^{m_{i}}}{m_{i}! (i!)^{m_{i}}}

Démonstration

Si $m 1 = k - 1$ et $m n - k +1 = 1$ , alors $\sum m i = k$ et $\sum i \cdot 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 \geq1$ valides.

Supposons qu'il existe un indice $j > n - k + 1$ tel que $m j \neq 0$ , soit $m j \geq 1$ . Les indices commençant à 1, on a également $j \geq 1$ , soit $j - 1 \geq 0$ , d'où $(j - 1)\cdot m j \geq j - 1$ En outre, les inégalités $i \geq 1$ et $m i \geq 0$ donnent $i \cdot m i \geq m i$ . On obtient donc

\begin{matrix} n & = \sum_{i \in ℕ^{*}} i \cdot m_{i} \\ = j \cdot m_{j} + \sum_{i \in ℕ^{*} ∖ {j}} i \cdot m_{i} \\ \geq j \cdot m_{j} + \sum_{i \in ℕ^{*} ∖ {j}} m_{i} (par i \cdot m_{i} \geq m_{i}) \\ = (j - 1) \cdot m_{j} + \sum_{i \in ℕ^{*}} m_{i} \\ = (j - 1) \cdot m_{j} + k \\ \geq j - 1 + k (par (j - 1) \cdot m_{j} \geq (j - 1)) \\ > (n - k + 1) - 1 + k (par j > n - k + 1) \\ = n \end{matrix}

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 \geq1$ 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 $m 1$ sous-ensembles de cardinalité 1, $m 2$ sous-ensembles de cardinalité 2, etc. Le nombre de telles partitions est le coefficient du monôme unitaire $x m 1 1 x m 2 2 \dots$ dans le polynôme de Bell $B n, k (x 1, x 2, \dots)$ . On notera que :

par construction, on a $\sum m i = k$ (nombre de sous-ensembles) et $\sum i \cdot 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 1$ premiers éléments de la liste, puis 2 par 2 les $2\cdot m 2$ é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 = 1$ , $m 2 = 2$ et $m 3 = 1$ (soit $k = 4$ et $n = 8$ ), et pour un ensemble de départ ${A, B, \dots, 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 1$ fois par $1!$ , $m 2$ fois par $2!$ , etc., soit au final par $\prod (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!\cdot2!\cdot3! = 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 1!\cdot m 2!\cdot\dots = \prod 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\cdot2! = 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 1, m 2, m 3) = (1, 2, 1)$ . En conclusion, l'un des monômes du polynôme de Bell $B 8,4 (x 1, x 2, \dots)$ est donc $840 x 3 x 22 x 1$ (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! / \prod (i!) m i \cdot \prod m i! = n! / \prod m i!\cdot(i!) m i$ , coefficient associé au monôme unitaire $x m 1 1 x m 2 2 \dots = \prod x m i i$ .

Exemples

On a :

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}

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}

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{matrix} (\binom{0}{0}) x_{1} & (\binom{1}{0}) x_{2} & (\binom{2}{0}) x_{3} & (\binom{3}{0}) x_{4} & \dots & (\binom{n - 2}{0}) x_{n - 1} & (\binom{n - 1}{0}) x_{n} \\ - 1 & (\binom{1}{1}) x_{1} & (\binom{2}{1}) x_{2} & (\binom{3}{1}) x_{3} & \dots & (\binom{n - 2}{1}) x_{n - 2} & (\binom{n - 1}{1}) x_{n - 1} \\ 0 & - 1 & (\binom{2}{2}) x_{1} & (\binom{3}{2}) x_{2} & \dots & (\binom{n - 2}{2}) x_{n - 3} & (\binom{n - 1}{2}) x_{n - 2} \\ 0 & 0 & - 1 & (\binom{3}{3}) x_{1} & \dots & (\binom{n - 2}{3}) x_{n - 4} & (\binom{n - 1}{3}) x_{n - 3} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋱ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & \dots & (\binom{n - 2}{n - 2}) x_{1} & (\binom{n - 1}{n - 2}) x_{2} \\ 0 & 0 & 0 & 0 & \dots & - 1 & (\binom{n - 1}{n - 1}) x_{1} \end{matrix} | = | (\binom{j - 1}{i - 1}) x_{j - i + 1} - δ_{j - i + 1} |

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}$	$3 x_{2} x_{1}$	$x_{1}^{3}$
4	$0$	$x_{4}$	$4 x_{3} x_{1} + 3 x_{2}^{2}$	$6 x_{2} x_{1}^{2}$	$x_{1}^{4}$
5	$0$	$x_{5}$	$5 x_{4} x_{1} + 10 x_{3} x_{2}$	$10 x_{3} x_{1}^{2} + 15 x_{2}^{2} x_{1}$	$10 x_{2} x_{1}^{3}$	$x_{1}^{5}$
6	$0$	$x_{6}$	$6 x_{5} x_{1} + 15 x_{4} x_{2} + 10 x_{3}^{2}$	$15 x_{4} x_{1}^{2} + 60 x_{3} x_{2} x_{1} + 15 x_{2}^{3}$	$20 x_{3} x_{1}^{3} + 45 x_{2}^{2} x_{1}^{2}$	$15 x_{2} x_{1}^{4}$	$x_{1}^{6}$

Propriétés

Cas limites

$B_{n, 0} (x_{1}, x_{2}, \dots) = δ_{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!} {(\sum_{n = 1}^{\infty} x_{n} \frac{t^{n}}{n!})}^{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 \in ℕ *$ vérifiant $j \geq n - k + 1$ et $(y 1, \dots, y j)$ une suite de scalaires. La formule du multinôme de Newton établit que

{(\sum_{i = 1}^{j} y_{i})}^{k} = \sum_{\begin{matrix} (m_{1}, \dots, m_{j}) \in ℕ^{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 ℕ^{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 / i!$ , on obtient

\frac{1}{k!} {(\sum_{i = 1}^{j} x_{i} \frac{t^{i}}{i!})}^{k} = \sum_{\begin{matrix} (m_{1}, \dots, m_{j}) \in ℕ^{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 ℕ^{j} \\ \sum_{i = 1}^{j} m_{i} = k \end{matrix}} (\prod_{i = 1}^{j} \frac{x_{i}^{m_{i}}}{m_{i}! (i!)^{m_{i}}}) 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 n$ , qui vaut

c_{n} = \sum_{\begin{matrix} (m_{1}, \dots, m_{j}) \in ℕ^{j} \\ {\begin{matrix} \sum_{i = 1}^{j} m_{i} = k \\ \sum_{i = 1}^{j} i \cdot m_{i} = n \end{matrix} \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 $\sum m i = k$ et $\sum i \cdot m i = n$ font que $m i = 0$ pour tout $i > n - k + 1$ . Comme on a choisi $j \geq n - k + 1$ , la somme constituant $c n$ couvre bien toutes les suites $(m i) i \geq1$ valides, d'où

c_{n} = \sum_{\begin{matrix} (m_{1}, \dots, m_{n - k + 1}) \in ℕ^{n - k + 1} \\ {\begin{matrix} \sum_{i = 1}^{n - k + 1} m_{i} = k \\ \sum_{i = 1}^{n - k + 1} i \cdot m_{i} = n \end{matrix} \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 n$ de la série formelle obtenue en faisant tendre $j$ vers l'infini, d'où

\frac{1}{k!} {(\sum_{i = 1}^{\infty} x_{i} \frac{t^{i}}{i!})}^{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 (\sum_{n = 1}^{\infty} x_{n} \frac{t^{n}}{n!}) = \sum_{n = 0}^{\infty} B_{n} (x_{1}, \dots, x_{n}) \frac{t^{n}}{n!}$

Démonstration

\begin{matrix} \exp (\sum_{n = 1}^{\infty} x_{n} \frac{t^{n}}{n!}) & = \sum_{k = 0}^{\infty} \frac{1}{k!} {(\sum_{n = 1}^{\infty} x_{n} \frac{t^{n}}{n!})}^{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{matrix}

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} [\sum_{k = 0}^{n} f_{k} B_{n, k} (g_{1}, \dots, g_{n - k + 1})] \frac{t^{n}}{n!}

Démonstration

\begin{matrix} (f \circ g) (t) & = \sum_{k = 0}^{\infty} f_{k} \frac{g (t)^{k}}{k!} \\ = \sum_{k = 0}^{\infty} f_{k} \frac{1}{k!} {(\sum_{n = 1}^{\infty} g_{n} \frac{t^{n}}{n!})}^{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} [\sum_{k = 0}^{n} f_{k} B_{n, k} (g_{1}, \dots, g_{n - k + 1})] \frac{t^{n}}{n!} \end{matrix}

Formules de récurrence

\begin{matrix} 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{matrix}

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!} {(\sum_{n = 1}^{\infty} x_{n} \frac{t^{n}}{n!})}^{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 \to 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)!} {(\sum_{n = 1}^{\infty} x_{n} \frac{t^{n}}{n!})}^{k + 1}

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

\begin{matrix} {[\sum_{n = k + 1}^{\infty} B_{n, k + 1} (x_{1}, \dots, x_{n - k}) \frac{t^{n}}{n!}]}^{'} & = \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{matrix}

et d'autre part

\begin{matrix} {[\frac{1}{(k + 1)!} {(\sum_{n = 1}^{\infty} x_{n} \frac{t^{n}}{n!})}^{k + 1}]}^{'} & = {(\sum_{i = 1}^{\infty} x_{i} \frac{t^{i}}{i!})}^{'} \cdot \frac{1}{k!} {(\sum_{n = 1}^{\infty} x_{n} \frac{t^{n}}{n!})}^{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{matrix} i \geq 0 \\ j \geq k \end{matrix}} 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{matrix} i \geq 0 \\ n - i \geq k \end{matrix}} x_{i + 1} B_{n - i, k} (x_{1}, \dots, x_{n - i - k + 1}) \frac{t^{n}}{i! (n - i)!} \\ = \sum_{{\begin{matrix} n - k \geq i \geq 0 \\ n \geq k + i \geq k \end{matrix}} 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{matrix}

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{matrix} \frac{t^{n}}{n!} \end{matrix})}_{n \in 𝐍}$ , 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 \to n - i$ .

\begin{matrix} 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{matrix}

avec $B 0 = B 0,0 = 1$ .

Démonstration

Pour $n \geq 0$ on a $n + 1 > 0$ , d'où $B n +1,0 = 0$ , donc

\begin{matrix} 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{matrix}

La seconde forme s'obtient immédiatement par le changement de variable $i \to n - i$ .

Démonstration

La matrice $(\begin{matrix} (\binom{j - 1}{i - 1}) x_{j - i + 1} - δ_{j - i + 1} \end{matrix})$ é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{matrix} n \\ k \end{matrix}}$ (nombre de Stirling de seconde espèce non signé)
$B_{n, k} (1, - 1, 1, - 1, \dots, (- 1)^{n - k}) = (- 1)^{n - k} {\begin{matrix} n \\ k \end{matrix}}$ (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{matrix} n \\ k \end{matrix}]$ (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{matrix} n \\ k \end{matrix}]$ (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)!) = δ_{n, 0} + δ_{n, 1}$
$B_{n} (- 0!, - 1!, \dots, - (n - 1)!) = δ_{n, 0} - δ_{n, 1}$
$B_{n, k} (1!, 2!, \dots, (n - k + 1)!) = ⌊ \begin{matrix} n \\ k \end{matrix} ⌋$ (nombre de Lah non signé)
$B_{n, k} (- 1!, 2!, - 3!, 4!, \dots, (- 1)^{n - k + 1} (n - k + 1)!) = (- 1)^{n} ⌊ \begin{matrix} n \\ k \end{matrix} ⌋$ (nombre de Lah signé)

Type binomial

Article détaillé : 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 0 = 1$ .

Réciproque

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

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 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{matrix} 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{matrix}

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 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{matrix} 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{matrix}

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 $α \neq 0$ (soit $f -1 (x) = x 1/ α$ ) infiniment dérivable en 1, on a :

$f^{(k)} (1) = α^{\underline{k}}$
$[f^{- 1}]^{(k)} (f (1)) = {(\frac{1}{α})}^{\underline{k}}$

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

y_{n} = \sum_{k = 1}^{n} α^{\underline{k}} B_{n, k} (x_{1}, \dots, x_{n - k + 1}) \Leftrightarrow x_{n} = \sum_{k = 1}^{n} {(\frac{1}{α})}^{\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{matrix} B_{j - 1, i - 1} (f_{1}, \dots, f_{j - i + 1}) \end{matrix})$ (triangulaire supérieure) ainsi que $G$ et $H$ de manière similaire, on a alors :

H = F G

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} δ_{n, k} \frac{t^{n}}{n!}

(Note : la notation $e_{k}$ pour cette fonction vient de la théorie des espèces combinatoires.) 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{matrix} (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} δ_{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{matrix}

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

\begin{matrix} ℓ_{k} (t) & = \sum_{n = 0}^{\infty} B_{n, k} (f_{1}, \dots, f_{n - k + 1}) \frac{t^{n}}{n!} \\ = \sum_{n = 0}^{\infty} (ℓ_{k})_{n} \frac{t^{n}}{n!} \end{matrix}

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

\begin{matrix} (ℓ_{k} \circ g) (t) & = \sum_{n = 0}^{\infty} \sum_{i = 0}^{n} (ℓ_{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{matrix}

L'égalité $e_{k} \circ h_{+} = ℓ_{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{matrix} \frac{t^{n}}{n!} \end{matrix})}_{n \in 𝐍}$ , 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{matrix} i \\ k \end{matrix}} [\begin{matrix} n \\ i \end{matrix}] = δ_{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{matrix} i \\ k \end{matrix}] {\begin{matrix} n \\ i \end{matrix}} = δ_{n, k}

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

\sum_{i = k}^{n} {\begin{matrix} i \\ k \end{matrix}} [\begin{matrix} n \\ i \end{matrix}] = ⌊ \begin{matrix} n \\ k \end{matrix} ⌋

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

\sum_{i = k}^{n} (- 1)^{n - i} ⌊ \begin{matrix} i \\ k \end{matrix} ⌋ ⌊ \begin{matrix} n \\ i \end{matrix} ⌋ = δ_{n, k}

Factorielle décroissante

\forall (a, b) \in ℕ^{2}, \sum_{k = 1}^{n} a^{\underline{k}} B_{n, k} (b^{\underline{1}}, \dots, b^{\underline{n}}) = (a b)^{\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}, \dots, α β^{n - k + 1} x_{n - k + 1}) = α^{k} β^{n} B_{n, k} (x_{1}, \dots, x_{n - k + 1})$

Cas particuliers: $B_{n, k} (α x_{1}, \dots, α x_{n - k + 1}) = α^{k} B_{n, k} (x_{1}, \dots, x_{n - k + 1})$; $B_{n, k} (α x_{1}, \dots, α^{n - k + 1} x_{n - k + 1}) = α^{n} B_{n, k} (x_{1}, \dots, x_{n - k + 1})$

Polynômes de Bell complets

Cas général: $B_{n} (α β x_{1}, \dots, α β^{n} x_{n}) = β^{n} \sum_{k = 0}^{n} α^{k} B_{n, k} (x_{1}, \dots, x_{n - k + 1})$

Cas particuliers: $B_{n} (α x_{1}, \dots, α x_{n}) = \sum_{k = 0}^{n} α^{k} B_{n, k} (x_{1}, \dots, x_{n - k + 1})$; $B_{n} (α x_{1}, \dots, α^{n} x_{n}) = α^{n} B_{n} (x_{1}, \dots, x_{n})$

Autre expression: $B_{n} (α x_{1}, \dots, α x_{n}) = \sum_{k = 0}^{n} α^{\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)^{α} = \sum_{n = 0}^{\infty} α^{\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)^{α} = \exp (α t) = \sum_{n = 0}^{\infty} α^{n} \frac{t^{n}}{n!}

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

\begin{matrix} (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} α^{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} (α 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{matrix}

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

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

\begin{matrix} 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{matrix}

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

\begin{matrix} (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} α^{\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{matrix}

Résultat

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

\sum_{n = 0}^{\infty} B_{n} (α x_{1}, \dots, α x_{n}) \frac{t^{n}}{n!} = \sum_{n = 0}^{\infty} \sum_{k = 0}^{n} α^{\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{matrix} \frac{t^{n}}{n!} \end{matrix})}_{n \in 𝐍}$ , on obtient

B_{n} (α x_{1}, \dots, α x_{n}) = \sum_{k = 0}^{n} α^{\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 ♢ y)_{n} = \sum_{j = 1}^{n - 1} (\binom{n}{j}) x_{j} y_{n - j}

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

Soit $x_{n}^{k ♢}$ le n-ème terme de la suite $\underset{k f a c t e u r s}{\underset{⏟}{x ♢ \dots ♢ x}}$

Alors :

B_{n, k} (x_{1}, \dots, x_{n - k + 1}) = \frac{x_{n}^{k ♢}}{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} (g^{'} (x), \dots, g^{(n - k + 1)} (x))

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} (κ_{1}, \dots, κ_{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} (\binom{n}{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} (\frac{d}{d x}) p_{n} (x) = n p_{n - 1} (x)

Notes et références

↑ (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
↑ (en) Andrzej Korzeniowski, “Binomial Tails Domination for Random Graphs via Bell Polynomials”, dans JPSS, vol. 4, n^o 1, 2006, p. 99-105

(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

Portail des mathématiques

[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^o 1, 2006, p. 99-105

[1]

[2]