ベル多項式

組合せ数学におけるベル多項式（ベルたこうしき、英: 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 ! ∏ i = 1 n − k + 1 j i ! ∏ i = 1 n − k + 1 ( x i i ! ) j i {\displaystyle :=\sum {\frac {n!}{\prod \limits _{i=1}^{n-k+1}j_{i}!}}\prod _{i=1}^{n-k+1}{\left({\frac {x_{i}}{i!}}\right)^{j_{i}}}} ただしこの和は、 ∑ i = 1 n − k + 1 j i = k ∧ ∑ i = 1 n − k + 1 i j i = n {\displaystyle \sum _{i=1}^{n-k+1}j_{i}=k\land \sum _{i=1}^{n-k+1}ij_{i}=n} を満たすすべての非負整数の列 j1, j2, j3, …, jn−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 次完全ベル多項式と呼ばれる。それらと比較するために、上で定義された多項式 Bn,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)!} ベル多項式 Bn,k(x1,x2, …) のすべての 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\}} である。 数列 xn, yn, 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}} となる。 ベル多項式を用いることで、ファー・ディ・ブルーノの公式（英語版）は次のように書き表すことができる。 d n d x n f ( g ( x ) ) = ∑ k = 1 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=1}^{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 a n d g ( x ) = ∑ n = 1 ∞ b n n ! x n {\displaystyle f(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}\qquad \mathrm {and} \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 個のキュムラントが κ1, …, κn であるような確率分布の n 次モーメントである。言い換えると、n 次モーメントとは初めの n 個のキュムラントによって評価される n 次完全ベル多項式である。 任意のスカラー列 a1, a2, a3, … に対し、次を定める。 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 に対して成立する。実際、次の結果が得られる。 定理 すべての二項型の多項式列はこの形式で表現できる。 今 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)} が成り立つ。 ベル多項式、完全ベル多項式および一般化ベル多項式は、Mathematicaにおいては BellY で、Maple においては BellB で、Sage においては bell_polynomial で計算することができる。