В математике , в частности в комбинаторике , полиномы Белла — это полиномы вида
B
n
,
k
(
x
1
,
x
2
,
…
,
x
n
−
k
+
1
)
=
∑
n
!
j
1
!
j
2
!
⋯
j
n
−
k
+
1
!
(
x
1
1
!
)
j
1
(
x
2
2
!
)
j
2
⋯
(
x
n
−
k
+
1
(
n
−
k
+
1
)
!
)
j
n
−
k
+
1
,
{\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}},}
где сумма берётся по всем последовательностям j 1 , j 2 , j 3 , ..., j n −k +1 неотрицательных целых чисел таким, что
j
1
+
j
2
+
⋯
=
k
{\displaystyle j_{1}+j_{2}+\cdots =k}
и
j
1
+
2
j
2
+
3
j
3
+
⋯
=
n
.
{\displaystyle j_{1}+2j_{2}+3j_{3}+\cdots =n.}
Полиномы Белла названы так в честь математика Э. Белла .
Сумма
B
n
(
x
1
,
…
,
x
n
)
=
∑
k
=
1
n
B
n
,
k
(
x
1
,
x
2
,
…
,
x
n
−
k
+
1
)
{\displaystyle 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
,
…
,
x
n
)
=
det
[
x
1
(
n
−
1
1
)
x
2
(
n
−
1
2
)
x
3
(
n
−
1
3
)
x
4
(
n
−
1
4
)
x
5
⋯
⋯
x
n
−
1
x
1
(
n
−
2
1
)
x
2
(
n
−
2
2
)
x
3
(
n
−
2
3
)
x
4
⋯
⋯
x
n
−
1
0
−
1
x
1
(
n
−
3
1
)
x
2
(
n
−
3
2
)
x
3
⋯
⋯
x
n
−
2
0
0
−
1
x
1
(
n
−
4
1
)
x
2
⋯
⋯
x
n
−
3
0
0
0
−
1
x
1
⋯
⋯
x
n
−
4
0
0
0
0
−
1
⋯
⋯
x
n
−
5
⋮
⋮
⋮
⋮
⋮
⋱
⋱
⋮
0
0
0
0
0
⋯
−
1
x
1
]
.
{\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}}.}
Комбинаторная интерпретация
править
Если в разбиении числа n слагаемое 1 появляется j 1 раз, 2 появляется j 2 раза, и т.д., то количество разбиений множества мощности n , в котором мощности частей образуют это разбиение числа n , равно соответствующему коэффициенту полинома Белла.
Для n = 6, k = 2 мы имеем
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
{\displaystyle 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
)
=
15
x
4
x
1
2
+
60
x
3
x
2
x
1
+
15
x
2
3
{\displaystyle 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
!
,
…
,
(
n
−
k
+
1
)
!
)
=
(
n
k
)
(
n
−
1
k
−
1
)
(
n
−
k
)
!
{\displaystyle B_{n,k}(1!,2!,\dots ,(n-k+1)!)={\binom {n}{k}}{\binom {n-1}{k-1}}(n-k)!}
Связь с числами Стирлинга и Белла
править
Значение полинома Белла B n ,k (x 1 , x 2 , …), где все x i равны 1 является числом Стирлинга второго рода :
B
n
,
k
(
1
,
1
,
…
)
=
S
(
n
,
k
)
=
{
n
k
}
.
{\displaystyle B_{n,k}(1,1,\dots )=S(n,k)=\left\{{n \atop k}\right\}.}
Сумма
∑
k
=
1
n
B
n
,
k
(
1
,
1
,
1
,
…
)
=
∑
k
=
1
n
{
n
k
}
{\displaystyle \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
♢
y
)
n
=
∑
j
=
1
n
−
1
(
n
j
)
x
j
y
n
−
j
.
{\displaystyle (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
♢
{\displaystyle x_{n}^{k\diamondsuit }}
есть n -й член последовательности
x
♢
⋯
♢
x
⏟
k
f
a
c
t
o
r
s
.
{\displaystyle \displaystyle \underbrace {x\diamondsuit \cdots \diamondsuit x} _{k\ \mathrm {factors} }.}
Тогда
B
n
,
k
(
x
1
,
…
,
x
n
−
k
+
1
)
=
x
n
k
♢
k
!
.
{\displaystyle B_{n,k}(x_{1},\dots ,x_{n-k+1})={x_{n}^{k\diamondsuit } \over k!}.}
Для примера вычислим
B
4
,
3
(
x
1
,
x
2
)
{\displaystyle B_{4,3}(x_{1},x_{2})}
. Так как
x
=
(
x
1
,
x
2
,
x
3
,
x
4
,
…
)
,
{\displaystyle x=(x_{1},\ x_{2},\ x_{3},\ x_{4},\ldots ),}
x
♢
x
=
(
0
,
2
x
1
2
,
6
x
1
x
2
,
8
x
1
x
3
+
6
x
2
2
,
…
)
,
{\displaystyle x\diamondsuit x=(0,\ 2x_{1}^{2}\ ,\ 6x_{1}x_{2}\ ,\ 8x_{1}x_{3}+6x_{2}^{2}\ ,\ldots ),}
x
♢
x
♢
x
=
(
0
,
0
,
6
x
1
3
,
36
x
1
2
x
2
,
…
)
,
{\displaystyle x\diamondsuit x\diamondsuit x=(0,\ 0,\ 6x_{1}^{3},\ 36x_{1}^{2}x_{2},\ldots ),}
то
B
4
,
3
(
x
1
,
x
2
)
=
(
x
♢
x
♢
x
)
4
3
!
=
6
x
1
2
x
2
.
{\displaystyle B_{4,3}(x_{1},x_{2})={\frac {(x\diamondsuit x\diamondsuit x)_{4}}{3!}}=6x_{1}^{2}x_{2}.}
Формула Фаа-ди-Бруно может быть сформулирована в терминах полиномов Белла следующим образом:
d
n
d
x
n
f
(
g
(
x
)
)
=
∑
k
=
0
n
f
(
k
)
(
g
(
x
)
)
B
n
,
k
(
g
′
(
x
)
,
g
″
(
x
)
,
…
,
g
(
n
−
k
+
1
)
(
x
)
)
.
{\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).}
Кроме того, мы можем использовать полиномы Белла, если
f
(
x
)
=
∑
n
=
1
∞
a
n
n
!
x
n
{\displaystyle f(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}\qquad }
и
g
(
x
)
=
∑
n
=
1
∞
b
n
n
!
x
n
,
{\displaystyle \qquad g(x)=\sum _{n=1}^{\infty }{b_{n} \over n!}x^{n},}
то
g
(
f
(
x
)
)
=
∑
n
=
1
∞
∑
k
=
1
n
b
k
B
n
,
k
(
a
1
,
…
,
a
n
−
k
+
1
)
n
!
x
n
.
{\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}.}
В частности, полные полиномы Белла появляются в разложении экспоненты формального степенного ряда
exp
(
∑
n
=
1
∞
a
n
n
!
x
n
)
=
∑
n
=
0
∞
B
n
(
a
1
,
…
,
a
n
)
n
!
x
n
.
{\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}.}
Сумма
B
n
(
κ
1
,
…
,
κ
n
)
=
∑
k
=
1
n
B
n
,
k
(
κ
1
,
…
,
κ
n
−
k
+
1
)
{\displaystyle B_{n}(\kappa _{1},\dots ,\kappa _{n})=\sum _{k=1}^{n}B_{n,k}(\kappa _{1},\dots ,\kappa _{n-k+1})}
есть n -й момент распределения вероятностей , первые n кумулянтов которых равны κ1 , …, κn . Другими словами, n -й момент равен значению n -го полного полинома Белла на первых n кумулянтах.
Представление полиномиальных последовательностей биномиального типа
править
Для заданной последовательности чисел a 1 , a 2 , a 3 , … положим
p
n
(
x
)
=
∑
k
=
1
n
B
n
,
k
(
a
1
,
…
,
a
n
−
k
+
1
)
x
k
.
{\displaystyle p_{n}(x)=\sum _{k=1}^{n}B_{n,k}(a_{1},\dots ,a_{n-k+1})x^{k}.}
Тогда эта последовательность полиномов имеет биномиальный тип , т.е. она удовлетворяет биномиальным условиям
p
n
(
x
+
y
)
=
∑
k
=
0
n
(
n
k
)
p
k
(
x
)
p
n
−
k
(
y
)
{\displaystyle p_{n}(x+y)=\sum _{k=0}^{n}{n \choose k}p_{k}(x)p_{n-k}(y)}
для n ≥ 0.
Теорема: Все полиномиальные последовательности биномиального типа представляются в таком виде.
Eсли мы рассмотрим
h
(
x
)
=
∑
n
=
1
∞
a
n
n
!
x
n
{\displaystyle h(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}}
как формальный степенной ряд, то для всех n ,
h
−
1
(
d
d
x
)
p
n
(
x
)
=
n
p
n
−
1
(
x
)
.
{\displaystyle h^{-1}\left({d \over dx}\right)p_{n}(x)=np_{n-1}(x).}
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 по полиномам Белла, примеры