Полиномы Белла
В математике, в частности в комбинаторике, полиномы Белла — это полиномы вида
- [math]\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}}, }[/math]
где сумма берётся по всем последовательностям j1, j2, j3, ..., jn−k+1 неотрицательных целых чисел таким, что
- [math]\displaystyle{ j_1+j_2+\cdots = k }[/math] и [math]\displaystyle{ j_1+2j_2+3j_3+\cdots=n. }[/math]
Полиномы Белла названы так в честь математика Э. Белла.
Полные полиномы Белла
Сумма
- [math]\displaystyle{ B_n(x_1,\dots,x_n)=\sum_{k=1}^n B_{n,k}(x_1,x_2,\dots,x_{n-k+1}) }[/math]
иногда называется n-м полным полиномом Белла. Для отличия от полных полиномов Белла, полиномы Bn, k, определённые выше, иногда называют «частичными» полиномами Белла.
Полные полиномы Белла удовлетворяют следующим условиям:
- [math]\displaystyle{ 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}. }[/math]
Комбинаторная интерпретация
Если в разбиении числа n слагаемое 1 появляется j1 раз, 2 появляется j2 раза, и т.д., то количество разбиений множества мощности n, в котором мощности частей образуют это разбиение числа n, равно соответствующему коэффициенту полинома Белла.
Примеры
Для n = 6, k = 2 мы имеем
- [math]\displaystyle{ B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_5x_1+15x_4x_2+10x_3^2 }[/math]
потому что есть
- 6 способов разбить множество мощности 6 на подмножества мощностей 5 + 1,
- 15 способов разбить множество мощности 6 на подмножества мощностей 4 + 2,
- 10 способов разбить множество мощности 6 на подножества мощностей 3 + 3.
Аналогично,
- [math]\displaystyle{ B_{6,3}(x_1,x_2,x_3,x_4)=15x_4x_1^2+60x_3x_2x_1+15x_2^3 }[/math]
потому что есть
- 15 способов разбить множество мощности 6 на подмножества мощностей 4 + 1 + 1,
- 60 способов разбить множество мощности 6 на подмножества мощностей 3 + 2 + 1, and
- 15 способов разбить множество мощности 6 на подмножества мощностей 2 + 2 + 2.
Свойства
- [math]\displaystyle{ B_{n,k}(1!,2!,\dots,(n-k+1)!) = \binom{n}{k}\binom{n-1}{k-1} (n-k)! }[/math]
Связь с числами Стирлинга и Белла
Значение полинома Белла Bn,k(x1, x2, …), где все xi равны 1 является числом Стирлинга второго рода:
- [math]\displaystyle{ B_{n,k}(1,1,\dots)=S(n,k)=\left\{{n\atop k}\right\}. }[/math]
Сумма
- [math]\displaystyle{ \sum_{k=1}^n B_{n,k}(1,1,1,\dots) = \sum_{k=1}^n \left\{{n\atop k}\right\} }[/math]
есть n-е число Белла (количество разбиений множества мощности n).
Тождество свертки
Для последовательности xn, yn, n = 1, 2, …, определёна свёртка:
- [math]\displaystyle{ (x \diamondsuit y)_n = \sum_{j=1}^{n-1} {n \choose j} x_j y_{n-j}. }[/math]
(Заметим, что пределы суммирования здесь 1 и n − 1, а не 0 и n.)
Положим, что [math]\displaystyle{ x_n^{k\diamondsuit} }[/math] есть n-й член последовательности
- [math]\displaystyle{ \displaystyle\underbrace{x\diamondsuit\cdots\diamondsuit x}_{k\ \mathrm{factors}}. }[/math]
Тогда
- [math]\displaystyle{ B_{n,k}(x_1,\dots,x_{n-k+1}) = {x_{n}^{k\diamondsuit} \over k!}. }[/math]
Для примера вычислим [math]\displaystyle{ B_{4,3}(x_1,x_2) }[/math]. Так как
- [math]\displaystyle{ x = ( x_1,\ x_2, \ x_3, \ x_4, \ldots ), }[/math]
- [math]\displaystyle{ x \diamondsuit x = ( 0,\ 2 x_1^2 \ ,\ 6 x_1 x_2 \ , \ 8 x_1 x_3 + 6 x_2^2 \ , \ldots ), }[/math]
- [math]\displaystyle{ x \diamondsuit x \diamondsuit x = ( 0,\ 0, \ 6 x_1^3, \ 36 x_1^2 x_2, \ldots ), }[/math]
то
- [math]\displaystyle{ B_{4,3}(x_1,x_2) = \frac{ ( x \diamondsuit x \diamondsuit x)_4 }{3!} = 6 x_1^2 x_2. }[/math]
Применения
Формула Фаа-ди-Бруно
Формула Фаа-ди-Бруно может быть сформулирована в терминах полиномов Белла следующим образом:
- [math]\displaystyle{ {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). }[/math]
Кроме того, мы можем использовать полиномы Белла, если
- [math]\displaystyle{ f(x)=\sum_{n=1}^\infty {a_n \over n!} x^n \qquad }[/math] и [math]\displaystyle{ \qquad g(x)=\sum_{n=1}^\infty {b_n \over n!} x^n, }[/math]
то
- [math]\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. }[/math]
В частности, полные полиномы Белла появляются в разложении экспоненты формального степенного ряда
- [math]\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. }[/math]
Моменты и кумулянты
Сумма
- [math]\displaystyle{ B_n(\kappa_1,\dots,\kappa_n)=\sum_{k=1}^n B_{n,k}(\kappa_1,\dots,\kappa_{n-k+1}) }[/math]
есть n-й момент распределения вероятностей, первые n кумулянтов которых равны κ1, …, κn. Другими словами, n-й момент равен значению n-го полного полинома Белла на первых n кумулянтах.
Представление полиномиальных последовательностей биномиального типа
Для заданной последовательности чисел a1, a2, a3, … положим
- [math]\displaystyle{ p_n(x)=\sum_{k=1}^n B_{n,k}(a_1,\dots,a_{n-k+1}) x^k. }[/math]
Тогда эта последовательность полиномов имеет биномиальный тип, т.е. она удовлетворяет биномиальным условиям
- [math]\displaystyle{ p_n(x+y)=\sum_{k=0}^n {n \choose k} p_k(x) p_{n-k}(y) }[/math] для n ≥ 0.
- Теорема: Все полиномиальные последовательности биномиального типа представляются в таком виде.
Eсли мы рассмотрим
- [math]\displaystyle{ h(x)=\sum_{n=1}^\infty {a_n \over n!} x^n }[/math]
как формальный степенной ряд, то для всех n,
- [math]\displaystyle{ h^{-1}\left( {d \over dx}\right) p_n(x) = n p_{n-1}(x). }[/math]
Программное обеспечение
- Полиномы Белла, полные полиномы Белла и обобщённые полиномы Белла реализованы в 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. — .
- 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 по полиномам Белла, примеры