出典: フリー百科事典『ウィキペディア(Wikipedia)』
2014年5月1日 (木) 11:41時点における版
組合せ数学 におけるベル多項式 (ベルたこうしき、英 : Bell polynomials )とは、エリック・テンプル・ベル の名にちなむ、次の多項式で与えられる三角形配列のことである。
B
n
,
k
(
x
1
,
x
2
,
…
,
x
n
−
k
+
1
)
{\displaystyle B_{n,k}(x_{1},x_{2},\dots ,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 =\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
+
⋯
=
k
and
j
1
+
2
j
2
+
3
j
3
+
⋯
=
n
{\displaystyle j_{1}+j_{2}+\cdots =k\quad {\mbox{and}}\quad j_{1}+2j_{2}+3j_{3}+\cdots =n}
を満たすすべての非負整数の列 j 1 , j 2 , j 3 , ..., j n −k +1 について取られている。
完全ベル多項式
次の和
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}}.}
組合せ論的な意味
例
例えば、次が得られる。
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 の集合を 5 + 1 に分割する方法は 6 通り
6 の集合を 4 + 2 に分割する方法は 15 通り
6 の集合を 3 + 3 に分割する方法は 10 通り
だからである。同様に
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}}
が得られる。なぜならば
6 の集合を 4 + 1 + 1 に分割する方法は 15 通り
6 の集合を 3 + 2 + 1 に分割する方法は 60 通り
6 の集合を 2 + 2 + 2 に分割する方法は 15 通り
だからである。
性質
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 が 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}}
.
ここで直和の上下限は 0 と n ではなく、1 と n − 1 であることに注意されたい。
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}\ ,\dots )}
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}\ ,\dots )}
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}\ ,\dots )}
であるため、
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}}
となる。
関連項目
参考文献
Eric Temple Bell (1927–1928). “Partition Polynomials”. Annals of Mathematics 29 (1/4): 38–46. doi :10.2307/1967979 . JSTOR 1967979 . MR 1502817 .
Louis Comtet (1974). Advanced Combinatorics: The Art of Finite and Infinite Expansions . Dordrecht, Holland / Boston, U.S.: Reidel Publishing Company
Steven Roman . The Umbral Calculus . Dover Publications
Vassily G. Voinov, Mikhail S. Nikulin (1994). “On power series, Bell polynomials, Hardy-Ramanujan-Rademacher problem and its statistical applications”. Kybernetika 30 (3): 343–358. ISSN 00235954 .
Andrews, George E. (1998). The Theory of Partitions . Cambridge Mathematical Library (1st pbk ed.). Cambridge University Press . pp. 204–211. ISBN 0-521-63766-X
Silvia Noschese, Paolo E. Ricci (2003). “Differentiation of Multivariable Composite Functions and Bell Polynomials”. Journal of Computational Analysis and Applications 5 (3): 333–340. doi :10.1023/A:1023227705558 .
Abbas, Moncef; Bouroubi, Sadek (2005). “On new identities for Bell's polynomial”. Disc. Math (293): 5–10. doi :10.1016/j.disc.2004.08.023 . MR 2136048 .
Khristo N. Boyadzhiev (2009). “Exponential Polynomials, Stirling Numbers, and Evaluation of Some Gamma Integrals”. Abstract and Applied Analysis 2009 : Article ID 168672. doi :10.1155/2009/168672 . (contains also elementary review of the concept Bell-polynomials)
V. V. Kruchinin (2011). "Derivation of Bell Polynomials of the Second Kind". arXiv :1104.5065 。
Griffiths, Martin (2012). “Families of sequences from a class of multinomial sums” . Journal of Integer Sequences 15 . MR 2872465 . http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Griffiths/griffiths20.html .