インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

52:ベル数

52 877

n個の元からなる集合の分割の個数をBell数と言い、B_nと表します。関-Bernoulli数と同じ記号なので文脈判断の注意が必要です。あるいは、B(n)と区別して書くこともあるようです。

B_5=52と源氏物語の関係については以下の記事が参考になります:
simomath.blog.fc2.com


便宜的にB_0=B_1=1と定義し、B_2, B_3, B_4は次のようになっています:

  • B_2=1

集合\{a, b\}の分割は

\begin{equation}\begin{split} &\{a\}, \{b\} \\ &\{a, b\}\end{split}\end{equation}

の2通り。

  • B_3=5

集合\{a, b, c\}の分割は

\begin{equation}\begin{split} &\{a\}, \{b\}, \{c\} \\ &\{a\}, \{b, c\} \\ &\{b\}, \{a, c\} \\ &\{c\}, \{a, b\} \\ &\{a, b, c\}\end{split}\end{equation}

の5通り。

B_4=15
集合\{a, b, c, d\}の分割は

\begin{equation}\begin{split} &\{a\}, \{b\}, \{c\}, \{d\} \\ &\{a\}, \{b, c, d\} \\ &\{b\}, \{a, c, d\} \\ &\{c\}, \{a, b, d\} \\ &\{d\}, \{a, b, c\} \\ &\{a\}, \{b\}, \{c, d\} \\ &\{a\}, \{c\}, \{b, d\} \\ &\{a\}, \{d\}, \{b, c\} \\ &\{b\}, \{c\}, \{a, d\} \\ &\{b\}, \{d\}, \{a, c\} \\ &\{c\}, \{d\}, \{a, b\} \\ &\{a, b\}, \{c, d\} \\ &\{a, c\}, \{b, d\} \\ &\{a, d\}, \{b, c\} \\ &\{a, b, c, d\}\end{split}\end{equation}

の15通り。

数値だけ列挙すると、以下のようになっています:

B_{0}= 1
B_{1}= 1
B_{2}= 2 ←素数
B_{3}= 5 ←素数
B_{4}= 15
B_{5}= 52
B_{6}= 203
B_{7}= 877 ←素数
B_{8}= 4140
B_{9}= 21147
B_{10}= 115975
B_{11}= 678570
B_{12}= 4213597
B_{13}= 27644437 ←素数
B_{14}= 190899322
B_{15}= 1382958545
B_{16}= 10480142147
B_{17}= 82864869804
B_{18}= 682076806159
B_{19}= 5832742205057
B_{20}= 51724158235372
B_{21}= 474869816156751
B_{22}= 4506715738447323
B_{23}= 44152005855084346
B_{24}= 445958869294805289
B_{25}= 4638590332229999353
B_{26}= 49631246523618756274
B_{27}= 545717047936059989389
B_{28}= 6160539404599934652455
B_{29}= 71339801938860275191172
B_{30}= 846749014511809332450147
B_{31}= 10293358946226376485095653
B_{32}= 128064670049908713818925644
B_{33}= 1629595892846007606764728147
B_{34}= 21195039388640360462388656799
B_{35}= 281600203019560266563340426570
B_{36}= 3819714729894818339975525681317
B_{37}= 52868366208550447901945575624941
B_{38}= 746289892095625330523099540639146
B_{39}= 10738823330774692832768857986425209
B_{40}= 157450588391204931289324344702531067
B_{41}= 2351152507740617628200694077243788988
B_{42}= 35742549198872617291353508656626642567 ←素数
B_{43}= 552950118797165484321714693280737767385
B_{44}= 8701963427387055089023600531855797148876
B_{45}= 139258505266263669602347053993654079693415
B_{46}= 2265418219334494002928484444705392276158355
B_{47}= 37450059502461511196505342096431510120174682
B_{48}= 628919796303118415420210454071849537746015761
B_{49}= 10726137154573358400342215518590002633917247281
B_{50}= 185724268771078270438257767181908917499221852770
B_{51}= 3263983870004111524856951830191582524419255819477
B_{52}= 58205338024195872785464627063218599149503972126463
B_{53}= 1052928518014714166107781298021583534928402714242132
B_{54}= 19317287589145618265728950069285503257349832850302011
B_{55}= 359334085968622831041960188598043661065388726959079837 ←素数

なお、知られている最大のBell素数はB_{2841}で、Bell素数が無数に存在するかどうかについては未解決問題です。

ちなみに、877のことを私はバナナ素数と呼んでいますw

Bell数のみたす漸化式

Bell数は漸化式

\displaystyle B_{n+1} = \sum_{k=0}^n\binom{n}{k}B_k

を満たします。今、n+1個の元からなる集合\{a_0, a_1, \dots, a_n\}の分割を考えます。a_0に着目して、各分割におけるa_0が属する部分集合を考えましょう。k=0, \dots, nとするとき、その集合の元の個数がk+1個であると仮定すると(そのような集合は\binom{n}{k}=\binom{n}{n-k}通りある)、残りの部分はn-k個の元からなる集合の分割になっていることが分かります。こうして得られる各分割にはダブりがないことがわかるので、

\displaystyle B_{n+1}=\sum_{k=0}^m\binom{n}{n-k}B_{n-k} = \sum_{k=0}^n\binom{n}{k}B_n

が成り立つことがわかりました。

Bell数の母関数

Bell数は次のような母関数表示を持ちます:

\displaystyle e^{e^x-1} = \sum_{n=0}^{\infty}B_n\frac{x^n}{n!} \in \mathbb{Q}[ \! [ x ] \! ] .

証明は次回紹介します。

Touchardの合同式

Bell数に関しては次の興味深い合同式が成立します:

Touchardの合同式 任意の非負整数nと素数pに対して、合同式
B_{n+p}\equiv B_n+B_{n+1} \pmod{p}
が成立する。

n=5, p=11で確認してみましょう。

B_{5}= 52 = 11\times 4 + 8\equiv 8 \pmod{11}
B_6=203 =11\times 18 +5\equiv 5 \pmod{11}

なので

B_5+B_6 \equiv 13 \equiv 2 \pmod{11}

ですが、一方、

B_{16}= 10480142147 = 11 \times 952740195 + 2 \equiv 2 \pmod{11}

なので、

B_{16} \equiv B_5+B_6 \pmod{11}

が確認できました。
この合同式の証明も別の記事で紹介します。