ベル数[1]

ベル数 \(B_n\) とは「\(n\) 個のものを分割する方法の総数(場合の数)」です。

\(n=0,1,2,3,4 \cdots \) のとき$$B_0=1, B_1=1, B_2=2, B_3=5, B_4=15 \cdots $$であり、ベル数の漸化式は以下のようになります。$$B_{n+1}=\displaystyle\sum_{k=0}^n {}_n \mathrm{C}_k B_k$$









<証明(考え方)>

\(B_3\) について考えてみます。

\(B_3\) は「\(3\) 個のものを分割する方法」だから

「\(3\) 個のもの」を「\(A,B,C\)」とすると(コンマは分割を意味しています)

\((ABC)\,(AB,C)\,(AC,B)\,(BC,A)\,(A,B,C)\) の \(5\) 通りとなるので \(B_3=5\) です。



\(B_2\) では「\(2\) 個のもの」を「\(A,B\)」とすると

\((AB)\,(A,B)\) の \(2\) 通りとなるので \(B_2=2\) です。



\(B_1\) では「\(1\) 個のもの」を「\(A\)」とすると

\((A)\) の \(1\) 通りとなるので \(B_1=1\) です。



\(B_0\) は \(B_0=1\) とします。



同様に \(B_4\) も「\(A,B,C,D\)」を用いて数えてみると
\begin{alignat}{2}
&(ABCD)\,(ABC,D)\,(ABD,C)\,(ACD,B)\,(BCD,A)\\
&(AB,CD)\,(AB,C,D)\,(CD,A,B)\\
&(AC,BD)\,(AC,B,D)\,(BD,A,C)\\
&(AD,BC)\,(AD,B,C)\,(BC,A,D)\,(A,B,C,D)\\
\end{alignat}の \(15\) 通りとなるので \(B_4=15\) です。




ここで \(B_4\) について、次のように数えてみます。

\((α)\) 「\(D\)」だけのグループになっているものは$$(D,ABC)\,(D,AB,C)\,(D,AC,B)\,(D,BC,A)\,(D,A,B,C)$$の \(5\) 通りであり、左の「\(D\)」以外のグループを見れば、これは \(B_3\) であることが分かります。


\((β)\) 「\(D□\)」のグループが含まれるものは$$(DA,BC)\,(DA,B,C)\,(DB,AC)\,(DB,A,C)\,(DC,AB)\,(DC,A,B)$$「\(D□\)」の \(□\) は \(A,B,C\) のうちから \(1\) つ選ぶので \({}_3\mathrm{C}_1\) 通り。

その右にある \((BC)\,(B,C)\) などは \(B_2\) に等しい。よって \({}_3 \mathrm{C}_1 B_2=3 \cdot 2=6\) 通り。


\((γ)\) 「\(D□□\)」のグループが含まれるものは$$(DAB,C)\,(DAC,B)\,(DBC,A)$$「\(D□□\)」の \(□□\) は \(A,B,C\) のうちから \(2\) つ選ぶので \({}_3\mathrm{C}_2\) 通り。

残りは \(B_1\) と見れば、\({}_3 \mathrm{C}_2 B_1=3 \cdot 1=3\) 通り。

\((δ)\) 「\(D□□\,□\)」のグループであるのものは$$(DABC)$$「\(D□□\,□\)」の \(□□□\) は \(A,B,C\) のうちから \(3\) つ選ぶので \({}_3\mathrm{C}_3\) 通り。

他に選ぶものは無いので \(B_0\) すれば \({}_3 \mathrm{C}_3 B_0=3 \cdot 1=1\) 通り。

よって \(B_4\) は次のような計算で得られることが分かります。
\begin{alignat}{2}
B_4&={}_3 \mathrm{C}_3 B_0+{}_3 \mathrm{C}_2 B_1+{}_3 \mathrm{C}_1 B_2+B_3\\
&={}_3 \mathrm{C}_0 B_0+{}_3 \mathrm{C}_1 B_1+{}_3 \mathrm{C}_2 B_2+{}_3 \mathrm{C}_3B_3\\
\end{alignat}
同様に考えることで \(B_{n+1}\) は次のように表されます。$$B_{n+1}={}_n \mathrm{C}_0 B_0+{}_n \mathrm{C}_1 B_1+{}_n \mathrm{C}_2 B_2+ \cdots +{}_n \mathrm{C}_{n-1} B_{n-1}+{}_n \mathrm{C}_n B_n$$以上より$$B_{n+1}=\displaystyle\sum_{k=0}^n {}_n \mathrm{C}_k B_k$$








コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です