本記事では、Bell多項式の定義とBell多項式の組み合わせ論的な意味について書いていきます。
続く記事では、Bell多項式とstirling数やBernoulli数などと絡めて記事を書いていくつもりです。
では、早速始めて行きましょう。
n個の異なるモノを
1個のみからなる$b_{1}$個のグループ
2個のみからなる$b_{2}$個のグループ
$\cdots$
k個のみからなる$b_{k}$個のグループ(ただし$1b_{1}+2b_{2}+\cdots kb_{k}=n$)
に分けるときその可能な分け方の総数は次の計算式で与えられる。
\begin{eqnarray}
\begin{array}{l}
\frac{n!}{b_{1}!b_{2}!\cdots b_{k}!}\frac{1}{(1!)^{b_{1}}(2!)^{b_{2}}\cdots (k!)^{b_{k}}}\\
\end{array}
\end{eqnarray}
1個のみからなる$b_{1}$個のグループのどれかにモノが属していれば色1を塗る。同様にして、i個のみからなる$b_{i}$個のグループのどれかにモノが属しているならば色iを塗る。
また、i個のみからなる$b_{i}$個のグループだけに着目し、それぞれのグループij(j=1,2,3,...,$b_{i}$)のどれか、例えばグループijにモノが属すならば番号jをそのモノに書き込む。
すると、モノの塗られた色と書き込まれた番号を見ればどのグループに属しているかがわかる。
つまり、まずn個のモノを順に並べて場所を固定し、そのうちから$b_{1}$個を選び色1を、残りの$n-b_{1}$個のモノから$2b_{2}$個のモノを選び色2を塗り、同様にして、残りの$n-b_{1}-2b_{2}-\cdots (i-1)b_{i-1}$個から$ib_{i}$個選んで色を塗っていけば
色1のモノが$b_{1}$個
色2のモノが$2b_{2}$個
$\cdots$
色kのモノが$kb_{k}$個
の様にモノが分けられる。また、色iのモノにだけ着目し、$ib_{i}$このうちからi個を選んで番号1を、残りの$i(b_{i}-1)$個からi個選んで番号2を、以下繰り返せば与えられた分け方に対応する色の塗り方と番号が割り振られた状態を一つ作れる。
この事から、求める総数はこの色の塗り方と番号の割り振り方の総数となることがわかる。ゆえに
\begin{eqnarray}
\begin{array}{l}
(求める総数)&={ n \choose b_{1} }{ n-b_{1} \choose 2b_{2} }\cdots { n-b_{1}-2b_{2}-\cdots -(k-1)b_{k-1} \choose kb_{k} }&\\
&\times {b_{1} \choose 1}{b_{1}-1 \choose 1}\cdots {1 \choose 1}& \\
&\times {2b_{2} \choose 2}{2(b_{2}-2) \choose 2}\cdots {2 \choose 2} & \\
&\cdots &\\
&\times {kb_{2} \choose k}{k(b_{k}-k) \choose k}\cdots {k \choose k} &\\
&\times \frac{1}{b_{1}!b_{2}!\cdots b_{k}!}&\\
&=\frac{n!}{b_{1}!b_{2}!\cdots b_{k}!}\frac{1}{(1!)^{b_{1}}(2!)^{b_{2}}\cdots (k!)^{b_{k}}}&
\end{array}
\end{eqnarray}
を得るので証明が終わる。
なお、$\frac{1}{b_{1}!b_{2}!\cdots b_{k}!}$は各i個からなるグループ内のものは色と番号で区別できない事からくるものである。
これでやっと、Bell多項式を定義する準備が整った。
なので早速Bell多項式を定義しよう。
n,kを0または正整数で$n\geq k \geq 0$をみたすようにとる。このとき次の多項式をBell多項式という。
\begin{equation}
B_{n,k}(x_{1},x_{2},...,x_{n-k+1})=\sum \frac{n!}{\prod_{i=1}^{k}b_{i}!}\prod_{i=1}^{n-k+1}(\frac{x_{i}}{i!})^{b_{i}}
\end{equation}
ただし、$\Sigma$は$\sum_{i=1}^{n-k+1}b_{i}=k \land \sum_{i=1}^{n-k+1}ib_{i}=n \land b_{1},b_{2},...,b_{n-k+1}\in \{0\}\cap \mathbb{N}$を満たす$b_{1},b_{2},...,b_{n-k+1}$全体で総和を取る事を意味するものとする。
定理1より直ちに、$B_{n,k}(x_{1},x_{2},...,x_{n-k+1})$の各$x_{1}^{b_{1}}x_{2}^{b_{2}}\cdots x_{n-k+1}^{b_{n-k+1}}$の係数は
n個の異なるモノを
1個のみからなる$b_{1}$個のグループ
2個のみからなる$b_{2}$個のグループ
$\cdots$
n-k+1個のみからなる$b_{n-k+1}$個のグループ(ただし$\sum_{i=1}^{n-k+1}b_{i}=k \land \sum_{i=1}^{n-k+1}ib_{i}=n \land b_{1},b_{2},...,b_{n-k+1}\in \{0\}\cap \mathbb{N}$)
を満たすように分ける総数を表していることが分かる。
今回は以上です。
では引き続きよろしくお願いいたします。