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

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

$B_{n,k}(x_1,x_2,\dots <!--\; \dots \; -->,x_{n-<!--\; -\; -->k+1})=\sum <!--\; \sum \; -->\frac{n!}{j_1!j_2!\cdots <!--\; \cdots \; -->j_{n-<!--\; -\; -->k+1}!}{\left(\frac{x_1}{1!}\right)}^{j_1}{\left(\frac{x_2}{2!}\right)}^{j_2}\cdots <!--\; \cdots \; -->{\left(\frac{x_{n-<!--\; -\; -->k+1}}{(n-<!--\; -\; -->k+1)!}\right)}^{j_{n-<!--\; -\; -->k+1}},$$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}},$

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

$j_1+j_2+\cdots <!--\; \cdots \; -->=k$$j_{1}+j_{2}+\cdots =k$ и $j_1+2j_2+3j_3+\cdots <!--\; \cdots \; -->=n.$$j_{1}+2j_{2}+3j_{3}+\cdots =n.$

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

Полные полиномы БеллаПравить

Сумма

$B_n(x_1,\dots <!--\; \dots \; -->,x_n)=\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}{B}_{n,k}(x_1,x_2,\dots <!--\; \dots \; -->,x_{n-<!--\; -\; -->k+1})$$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 {\begin{bmatrix}x_{1}&{n-1 \choose 1}x_{2}&{n-1 \choose 2}x_{3}&{n-1 \choose 3}x_{4}&{n-1 \choose 4}x_{5}&\cdots &\cdots &x_{n}\\\\-1&x_{1}&{n-2 \choose 1}x_{2}&{n-2 \choose 2}x_{3}&{n-2 \choose 3}x_{4}&\cdots &\cdots &x_{n-1}\\\\0&-1&x_{1}&{n-3 \choose 1}x_{2}&{n-3 \choose 2}x_{3}&\cdots &\cdots &x_{n-2}\\\\0&0&-1&x_{1}&{n-4 \choose 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}\\\\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\\\0&0&0&0&0&\cdots &-1&x_{1}\end{bmatrix}}.$ 

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

Если в разбиении числа 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$$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$$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 <!--\; \dots \; -->,(n-<!--\; -\; -->k+1)!)=(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k-<!--\; -\; -->1})(n-<!--\; -\; -->k)!$$B_{n,k}(1!,2!,\dots ,(n-k+1)!)={\binom {n}{k}}{\binom {n-1}{k-1}}(n-k)!$ 

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

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

$B_{n,k}(1,1,\dots <!--\; \dots \; -->)=S(n,k)=\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}.$$B_{n,k}(1,1,\dots )=S(n,k)=\left\{{n \atop k}\right\}.$ 

Сумма

$\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}{B}_{n,k}(1,1,1,\dots <!--\; \dots \; -->)=\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$$\sum _{k=1}^{n}B_{n,k}(1,1,1,\dots )=\sum _{k=1}^{n}\left\{{n \atop k}\right\}$ 

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

Тождество сверткиПравить

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

$(x\mathrm{♢<!--\; ♢\; -->}y{)}_n=\underset{j=1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{j})x_j{y}_{n-<!--\; -\; -->j}.$$(x\diamondsuit y)_{n}=\sum _{j=1}^{n-1}{n \choose j}x_{j}y_{n-j}.$ 

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

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

$\underset{k\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{s}}{\underset{⏟<!--\; ⏟\; -->}{x\mathrm{♢<!--\; ♢\; -->}\cdots <!--\; \cdots \; -->\mathrm{♢<!--\; ♢\; -->}x}}.$$\displaystyle \underbrace {x\diamondsuit \cdots \diamondsuit x} _{k\ \mathrm {factors} }.$ 

Тогда

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

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

$x=(x_1,x_2,x_3,x_4,\dots <!--\; \dots \; -->),$$x=(x_{1},\ x_{2},\ x_{3},\ x_{4},\ldots ),$ 

$x\mathrm{♢<!--\; ♢\; -->}x=(0,2x_1^2,6x_1{x}_2,8x_1{x}_3+6x_2^2,\dots <!--\; \dots \; -->),$$x\diamondsuit x=(0,\ 2x_{1}^{2}\ ,\ 6x_{1}x_{2}\ ,\ 8x_{1}x_{3}+6x_{2}^{2}\ ,\ldots ),$ 

$x\mathrm{♢<!--\; ♢\; -->}x\mathrm{♢<!--\; ♢\; -->}x=(0,0,6x_1^3,36x_1^2{x}_2,\dots <!--\; \dots \; -->),$$x\diamondsuit x\diamondsuit x=(0,\ 0,\ 6x_{1}^{3},\ 36x_{1}^{2}x_{2},\ldots ),$ 

то

$B_{4,3}(x_1,x_2)=\frac{(x\mathrm{♢<!--\; ♢\; -->}x\mathrm{♢<!--\; ♢\; -->}x{)}_4}{3!}=6x_1^2{x}_2.$$B_{4,3}(x_{1},x_{2})={\frac {(x\diamondsuit x\diamondsuit x)_{4}}{3!}}=6x_{1}^{2}x_{2}.$ 

ПримененияПравить

Формула Фаа-ди-БруноПравить

Основная статья: Формула Фаа-ди-Бруно

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

$\frac{d^n}{d{x}^n}f(g(x))=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}{f}^{(k)}(g(x))B_{n,k}\left(g^{\prime }(x),g^{″}(x),\dots <!--\; \dots \; -->,g^{(n-<!--\; -\; -->k+1)}(x)\right).$${d^{n} \over dx^{n}}f(g(x))=\sum _{k=0}^{n}f^{(k)}(g(x))B_{n,k}\left(g'(x),g''(x),\dots ,g^{(n-k+1)}(x)\right).$ 

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

$f(x)=\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{a_n}{n!}{x}^n$$f(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}\qquad$  и $g(x)=\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{b_n}{n!}{x}^n,$$\qquad g(x)=\sum _{n=1}^{\infty }{b_{n} \over n!}x^{n},$ 

то

$g(f(x))=\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}{b}_k{B}_{n,k}(a_1,\dots <!--\; \dots \; -->,a_{n-<!--\; -\; -->k+1})}{n!}{x}^n.$$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}.$ 

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

$\exp <!--\; \; -->\left(\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{a_n}{n!}{x}^n\right)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{B_n(a_1,\dots <!--\; \dots \; -->,a_n)}{n!}{x}^n.$$\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}.$ 

Моменты и кумулянтыПравить

Сумма

$B_n({\mathrm{\kappa <!--\; \kappa \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\kappa <!--\; \kappa \; -->}}_n)=\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}{B}_{n,k}({\mathrm{\kappa <!--\; \kappa \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\kappa <!--\; \kappa \; -->}}_{n-<!--\; -\; -->k+1})$$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)=\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}{B}_{n,k}(a_1,\dots <!--\; \dots \; -->,a_{n-<!--\; -\; -->k+1})x^k.$$p_{n}(x)=\sum _{k=1}^{n}B_{n,k}(a_{1},\dots ,a_{n-k+1})x^{k}.$ 

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

$p_n(x+y)=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})p_k(x)p_{n-<!--\; -\; -->k}(y)$$p_{n}(x+y)=\sum _{k=0}^{n}{n \choose k}p_{k}(x)p_{n-k}(y)$  для n ≥ 0.

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

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

$h(x)=\underset{n=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{a_n}{n!}{x}^n$$h(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}$ 

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

$h^{-<!--\; -\; -->1}\left(\frac{d}{dx}\right)p_n(x)=n{p}_{n-<!--\; -\; -->1}(x).$$h^{-1}\left({d \over dx}\right)p_{n}(x)=np_{n-1}(x).$ 

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

• Полиномы Белла, полные полиномы Белла и обобщённые полиномы Белла реализованы в Mathematica как BellY Архивная копия от 20 марта 2014 на Wayback Machine.

ИсточникиПравить

• Eric Temple Bell. Partition Polynomials (неопр.) // Annals of Mathematics. — 1927–1928. — Т. 29, № 1/4. — С. 38—46. — doi:10.2307/1967979. — JSTOR 1967979.
• Louis Comtet. Advanced Combinatorics: The Art of Finite and Infinite Expansions (англ.). — Dordrecht, Holland / Boston, U.S.: Reidel Publishing Company, 1974.
• Steven Roman  (англ.) (рус.. The Umbral Calculus (неопр.). — Dover Publications.
• Khristo N. Boyadzhiev. Exponential Polynomials, Stirling Numbers, and Evaluation of Some Gamma Integrals (англ.) // Abstract and Applied Analysis  (англ.) (рус. : journal. — 2009. — Vol. 2009. — P. Article ID 168672. — doi:10.1155/2009/168672. (contains also elementary review of the concept Bell-polynomials)
• Silvia Noschese, Paolo E. Ricci. Differentiation of Multivariable Composite Functions and Bell Polynomials (англ.) // Journal of Computational Analysis and Applications : journal. — 2003. — Vol. 5, no. 3. — P. 333—340. — doi:10.1023/A:1023227705558. '
• Vassily G. Voinov, Mikhail S. Nikulin. On power series, Bell polynomials, Hardy-Ramanujan-Rademacher problem and its statistical applications (англ.) // Kybernetika : journal. — 1994. — Vol. 30, no. 3. — P. 343—358. — ISSN 00235954.
• Kruchinin, V.V., 2011 , Derivation of Bell Polynomials of the Second Kind Архивная копия от 11 сентября 2015 на Wayback Machine(ArXiv)
• Конспект лекции Архивная копия от 4 марта 2016 на Wayback Machine по полиномам Белла, примеры