Полиномы Белла

В математике, в частности в комбинаторике, полиномы Белла — это полиномы вида

$B_{n,k}(x_1,x_2,\dots ,x_{n-k+1})=\sum \frac{n!}{j_1!j_2!\cdots j_{n-k+1}!}{\left(\frac{x_1}{1!}\right)}^{j_1}{\left(\frac{x_2}{2!}\right)}^{j_2}\cdots {\left(\frac{x_{n-k+1}}{(n-k+1)!}\right)}^{j_{n-k+1}},$

где сумма берётся по всем последовательностям j₁, j₂, j₃, ..., j_n−k+1 неотрицательных целых чисел таким, что

$j_1+j_2+\cdots =k$ и $j_1+2j_2+3j_3+\cdots =n.$

Полиномы Белла названы так в честь математика Э. Белла.

Полные полиномы Белла

Сумма

$B_n(x_1,\dots ,x_n)=\sum _{k=1}^n{B}_{n,k}(x_1,x_2,\dots ,x_{n-k+1})$

иногда называется n-м полным полиномом Белла. Для отличия от полных полиномов Белла, полиномы B_n, k, определённые выше, иногда называют «частичными» полиномами Белла.

Полные полиномы Белла удовлетворяют следующим условиям:

$B_n(x_1,\dots ,x_n)=\det \left[\begin{array}{cccccccc}{x}_1& (\genfrac{}{}{0ex}{}{n-1}{1})x_2& (\genfrac{}{}{0ex}{}{n-1}{2})x_3& (\genfrac{}{}{0ex}{}{n-1}{3})x_4& (\genfrac{}{}{0ex}{}{n-1}{4})x_5& \cdots & \cdots & x_n\\ \\ -1& x_1& (\genfrac{}{}{0ex}{}{n-2}{1})x_2& (\genfrac{}{}{0ex}{}{n-2}{2})x_3& (\genfrac{}{}{0ex}{}{n-2}{3})x_4& \cdots & \cdots & x_{n-1}\\ \\ 0& -1& x_1& (\genfrac{}{}{0ex}{}{n-3}{1})x_2& (\genfrac{}{}{0ex}{}{n-3}{2})x_3& \cdots & \cdots & x_{n-2}\\ \\ 0& 0& -1& x_1& (\genfrac{}{}{0ex}{}{n-4}{1})x_2& \cdots & \cdots & x_{n-3}\\ \\ 0& 0& 0& -1& x_1& \cdots & \cdots & x_{n-4}\\ \\ 0& 0& 0& 0& -1& \cdots & \cdots & x_{n-5}\\ \\ ⋮& ⋮& ⋮& ⋮& ⋮& \ddots & \ddots & ⋮\\ \\ 0& 0& 0& 0& 0& \cdots & -1& x_1\end{array}\right].$

Комбинаторная интерпретация

Если в разбиении числа n слагаемое 1 появляется j₁ раз, 2 появляется j₂ раза, и т.д., то количество разбиений множества мощности n, в котором мощности частей образуют это разбиение числа n, равно соответствующему коэффициенту полинома Белла.

Примеры

Для n = 6, k = 2 мы имеем

$B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_5{x}_1+15x_4{x}_2+10x_3^2$

потому что есть

• 6 способов разбить множество мощности 6 на подмножества мощностей 5 + 1,
• 15 способов разбить множество мощности 6 на подмножества мощностей 4 + 2,
• 10 способов разбить множество мощности 6 на подножества мощностей 3 + 3.

Аналогично,

$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$

потому что есть

15 способов разбить множество мощности 6 на подмножества мощностей 4 + 1 + 1,

60 способов разбить множество мощности 6 на подмножества мощностей 3 + 2 + 1, and

15 способов разбить множество мощности 6 на подмножества мощностей 2 + 2 + 2.

Свойства

• $B_{n,k}(1!,2!,\dots ,(n-k+1)!)=(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n-1}{k-1})(n-k)!$

Связь с числами Стирлинга и Белла

Значение полинома Белла B_n,k(x₁, x₂, …), где все x_i равны 1 является числом Стирлинга второго рода:

$B_{n,k}(1,1,\dots )=S(n,k)=\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}.$

Сумма

$\sum _{k=1}^n{B}_{n,k}(1,1,1,\dots )=\sum _{k=1}^n\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$

есть n-е число Белла (количество разбиений множества мощности n).

Тождество свертки

Для последовательности x_n, y_n, n = 1, 2, …, определёна свёртка:

$(x\mathrm{♢}y{)}_n=\sum _{j=1}^{n-1}(\genfrac{}{}{0ex}{}{n}{j})x_j{y}_{n-j}.$

(Заметим, что пределы суммирования здесь 1 и n − 1, а не 0 и n.)

Положим, что $x_n^{k\mathrm{♢}}$ есть n-й член последовательности

$\underset{k\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{s}}{\underbrace{x\mathrm{♢}\cdots \mathrm{♢}x}}.$

Тогда

$B_{n,k}(x_1,\dots ,x_{n-k+1})=\frac{x_n^{k\mathrm{♢}}}{k!}.$

Для примера вычислим $B_{4,3}(x_1,x_2)$. Так как

$x=(x_1,x_2,x_3,x_4,\dots ),$

$x\mathrm{♢}x=(0,2x_1^2,6x_1{x}_2,8x_1{x}_3+6x_2^2,\dots ),$

$x\mathrm{♢}x\mathrm{♢}x=(0,0,6x_1^3,36x_1^2{x}_2,\dots ),$

то

$B_{4,3}(x_1,x_2)=\frac{(x\mathrm{♢}x\mathrm{♢}x{)}_4}{3!}=6x_1^2{x}_2.$

Применения

Формула Фаа-ди-Бруно

Формула Фаа-ди-Бруно может быть сформулирована в терминах полиномов Белла следующим образом:

$\frac{d^n}{d{x}^n}f(g(x))=\sum _{k=0}^n{f}^{(k)}(g(x))B_{n,k}(g^{\prime }(x),g^{″}(x),\dots ,g^{(n-k+1)}(x)).$

Кроме того, мы можем использовать полиномы Белла, если

$f(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{a_n}{n!}{x}^n$ и $g(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{b_n}{n!}{x}^n,$

то

$g(f(x))=\sum _{n=1}^{\mathrm{\infty }}\frac{\sum _{k=1}^n{b}_k{B}_{n,k}(a_1,\dots ,a_{n-k+1})}{n!}{x}^n.$

В частности, полные полиномы Белла появляются в разложении экспоненты формального степенного ряда

$\exp \left(\sum _{n=1}^{\mathrm{\infty }}\frac{a_n}{n!}{x}^n\right)=\sum _{n=0}^{\mathrm{\infty }}\frac{B_n(a_1,\dots ,a_n)}{n!}{x}^n.$

Моменты и кумулянты

Сумма

$B_n({\kappa }_1,\dots ,{\kappa }_n)=\sum _{k=1}^n{B}_{n,k}({\kappa }_1,\dots ,{\kappa }_{n-k+1})$

есть n-й момент распределения вероятностей, первые n кумулянтов которых равны κ₁, …, κ_n. Другими словами, n-й момент равен значению n-го полного полинома Белла на первых n кумулянтах.

Представление полиномиальных последовательностей биномиального типа

Для заданной последовательности чисел a₁, a₂, a₃, … положим

$p_n(x)=\sum _{k=1}^n{B}_{n,k}(a_1,\dots ,a_{n-k+1})x^k.$

Тогда эта последовательность полиномов имеет биномиальный тип, т.е. она удовлетворяет биномиальным условиям

$p_n(x+y)=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})p_k(x)p_{n-k}(y)$ для n ≥ 0.

Теорема: Все полиномиальные последовательности биномиального типа представляются в таком виде.

Eсли мы рассмотрим

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

как формальный степенной ряд, то для всех n,

$h^{-1}\left(\frac{d}{dx}\right)p_n(x)=n{p}_{n-1}(x).$

Программное обеспечение

• Полиномы Белла, полные полиномы Белла и обобщённые полиномы Белла реализованы в Mathematica как BellY Шаблон:Wayback.

Источники

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья (contains also elementary review of the concept Bell-polynomials)
• Шаблон:Статья '
• Шаблон:Статья
• Kruchinin, V.V., 2011 , Derivation of Bell Polynomials of the Second Kind Шаблон:Wayback(ArXiv)
• Конспект лекции Шаблон:Wayback по полиномам Белла, примеры