ベル番号

一般的に、${\displaystyle B_{n}}$サイズが の集合の分割数${\displaystyle n}$集合の分割${\displaystyle S}$は、空でない、互いに素な部分集合の族として定義される。${\displaystyle S}$その組合は${\displaystyle S}$。 例えば、${\displaystyle B_{3}=5}$3要素セットなので${\displaystyle \{a,b,c\}}$5つの異なる方法で分割できます。

${\displaystyle \{\{a\},\{b\},\{c\}\},}$

${\displaystyle \{\{a\},\{b,c\}\},}$

${\displaystyle \{\{b\},\{a,c\}\},}$

${\displaystyle \{\{c\},\{a,b\}\},}$

${\displaystyle \{\{a,b,c\}\}.}$

上記の集合表記が示すように、族内の部分集合の順序は考慮されません。順序付けられた分割は、順序付けられたベル数と呼ばれる別の数列によって数えられます。${\displaystyle B_{0}}$空集合の分割がちょうど 1 つ存在するため、 は 1 になります。この分割自体が空集合であり、空集合の部分集合の族として解釈できます。この族の部分集合はすべて空集合の空でない部分集合であり、かつ互いに素な部分集合であることは自明です。なぜなら、このようなあり得ない性質を持つ部分集合は存在しないからです。

集合の分割は、その同値関係と1対1に対応します。これらは反射的、対称的、推移的な二項関係です。分割に対応する同値関係は、2つの要素が互いに同じ分割部分集合に属する場合に、それらが同値であると定義します。逆に、すべての同値関係は同値類への分割に対応します。^{[ 2 ]}したがって、ベル数も同値関係を数えます。

数字${\displaystyle N}$は平方因子を持たない正の整数であり、つまり、ある数の積である。${\displaystyle n}$異なる素数の${\displaystyle B_{n}}$の異なる乗法分割の数を示します${\displaystyle N}$これらはの因数分解です${\displaystyle N}$1より大きい数に分解し、2つの因数分解が同じ因数であっても順序が異なる場合は同じものとして扱います。^{[ 3 ]}例えば、30は3つの素数2、3、5の積であり 、${\displaystyle B_{3}}$= 5つの因数分解:

${\displaystyle 30=2\times 15=3\times 10=5\times 6=2\times 3\times 5}$

ベル数では、n行の詩またはスタンザの押韻構成も数えます。押韻構成は、どの行が互いに押韻しているかを記述するもので、行のセットを押韻する部分集合に分割したものと解釈できます。押韻構成は通常、1 行につき 1 つのローマ字のシーケンスとして記述され、押韻する行には同じ文字が割り当てられ、各押韻セットの最初の行はアルファベット順にラベル付けされます。したがって、可能な 15 通りの 4 行の押韻構成は、AAAA、AAAB、AABA、AABB、AABC、ABAA、ABAB、ABAC、ABBA、ABBB、ABBC、ABCA、ABCB、ABCC、および ABCD です。^{[ 1 ]}

ベル数は、 Gardner 1978の補遺で言及されているカードシャッフル問題で登場します。n枚のカードのデッキを、一番上のカードを繰り返し取り除き、デッキ内の任意の場所 (デッキの一番上の元の位置を含む) に再び挿入することによってシャッフルする場合、この操作を正確にn回繰り返すと、実行できるシャッフルはn ⁿ通りあります。これらのうち、デッキを元のソート順に戻すシャッフルの数は正確にB _nです。したがって、このようにシャッフルした後にデッキが元の順序になっている確率はB _n / n ⁿであり、これはデッキの均一ランダム置換を表す確率1/ n ! よりもはるかに大きくなります。

カードシャッフルに関連して、ベル数によって解決される特殊な順列の数え上げに関する他のいくつかの問題があります。たとえば、 n番目のベル数は、n個のアイテムの順列のうち、ソートされた 3 つの値の最後の 2 つが連続しない順列の数に等しくなります。連続しなければならない値は隣り合って書かれ、連続しない値もダッシュで区切られる一般化された順列パターンの表記では、これらの順列は、パターン 1-23 を避ける順列として記述できます。一般化されたパターン 12-3、32-1、3-21、1-32、3-12、21-3、および 23-1 を避ける順列もベル数によってカウントされます。^{[ 4 ]}連続する値に制限のないすべての 321 パターンを 3241 パターンに拡張できる順列もベル数によってカウントされます。^{[ 5 ]}しかし、ベル数は、このように一般化されていないパターンを回避する順列を数えるには速すぎるほど増加します。スタンレー・ウィルフ予想（現在は証明済み）によれば、そのような順列の数は単一指数関数的であり、ベル数はそれよりも高い漸近的増加率を持っています。

ベル数は二項係数を含む漸化式を満たす：^{[ 7 ]}

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}B_{k}.}$

これは、 n  + 1 個の項目からなる任意の分割から 、最初の項目を含む集合を取り除くと、0 からnまでの範囲の何らかの数kに対して、より小さなk個の項目からなる分割が残ることを観察することで説明できます。${\displaystyle {\tbinom {n}{k}}}$1つのセットを取り除いた後に残るk個のアイテムに対する選択肢と、それらを分割するBk_{個の選択肢。}

別の総和式では、各ベル数は第2種スターリング数の和として表される。

${\displaystyle B_{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}.}$

スターリング数${\displaystyle \left\{{n \atop k}\right\}}$は、 nの要素数を持つ集合を、ちょうどk個の空でない部分集合に分割する方法の数です。したがって、ベル数とスターリング数を関連付ける式では、式の左辺で数えられる各分割は、右辺の和の項のうち、kが分割内の集合の数である項のうちの 1 つに正確に数えられます。^{[ 8 ]}

したがって、後者の式を用いると、ベル数を非再帰的に計算できる。

${\displaystyle B_{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}=\sum _{k=0}^{n}{\frac {1}{k!}}\sum _{i=0}^{k}(-1)^{ki}{\binom {k}{i}}i^{n},}$

第2種スターリング数の明示的な公式の1つを使用する。^{[ 9 ]}

Spivey（2008）は、これら2つの総和を組み合わせた公式を提示している。

${\displaystyle B_{n+m}=\sum _{k=0}^{n}\sum _{j=0}^{m}\left\{{m \atop j}\right\}{n \choose k}j^{nk}B_{k}.}$

パスカルの逆公式を漸化式に適用すると、次の式が得られる。

$${\displaystyle B_{n}=\sum _{k=0}^{n}{\binom {n}{k}}(-1)^{nk}B_{k+1},}$$

これは次のように一般化できる。^{[ 10 ]}

$${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}B_{k+j}=\sum _{i=0}^{k}{\binom {k}{i}}(-1)^{k-i}B_{n+i+1}.}$$

第一種スターリング数を用いたその他の有限和公式には^{[ 10 ]}が含まれる。

$${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}a^{j}b^{n-j}B_{j}=\sum _{i=0}^{k}\left[{k \atop i}\right](-1)^{k-i}\sum _{j=0}^{n}{\binom {n}{j}}a^{j}(b-ak)^{n-j}B_{j+i},}$$

これは以下のように簡略化されます${\displaystyle k=1}$に

$${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}a^{j}b^{n-j}B_{j}=\sum _{j=0}^{n}{\binom {n}{j}}a^{j}(b-a)^{n-j}B_{j+1}}$$

そして${\displaystyle a=1}$、${\displaystyle b=k}$ に

$${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}B_{j}k^{n-j}=\sum _{i=0}^{k}\left[{k \atop i}\right]B_{n+i}(-1)^{k-i}}$$これは、スピビーの公式にスターリング数の逆公式を適用した ものと見なすことができる。

ベル数の指数生成関数は

${\displaystyle B(x)=\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}=e^{e^{x}-1}.}$

この式において、中央の総和は任意の数列に対する指数母関数を定義するために用いられる一般形であり、右側の式はベル数という特定のケースで総和を計算した結果である。

この結果を導き出す方法の一つは、解析的組み合わせ論を用いる。これは、数学的対象の集合をより単純な対象から構成されることを説明する式で記述し、それらの式を操作して対象の組み合わせ的性質を導き出す数学的推論のスタイルである。解析的組み合わせ論の言語では、集合の分割は、1からnまでのラベルが付けられた要素が分配された空でない壺の集合として記述でき、すべての分割の組み合わせクラス（すべてのnについて）は、次の記法で表すことができる。

${\displaystyle \mathrm {S\scriptstyle ET} (\mathrm {S\scriptstyle ET} _{\geq 1}({\mathcal {Z}})).}$

ここ、${\displaystyle {\mathcal {Z}}}$これは、サイズ1のメンバーが1つだけ存在する組み合わせクラスであり、壺に入れることができる要素です。${\displaystyle \mathrm {S\scriptstyle ET} _{\geq 1}}$演算子は、1 つ以上のラベル付き要素を含むセットまたは壺を記述し、外側の ${\displaystyle \mathrm {S\scriptstyle ET} }$全体分割をこれらの壺の集合として記述します。指数生成関数は、この表記から翻訳することで読み取ることができます。${\displaystyle \mathrm {S\scriptstyle ET} }$演算子を指数関数に、非空制約 ≥1 を 1 による減算に置き換える。^{[ 11 ]}

同じ生成関数を導出する別の方法として、ベル数の漸化式を二項係数で表し、指数生成関数が微分方程式を満たすことを示す方法がある。${\displaystyle B'(x)=e^{x}B(x)}$関数自体は、この方程式を解くことで求めることができます。^{[ 12 ] [ 13 ] [ 14 ]}

ベル数はドビンスキーの公式を満たす^{[ 15 ] [ 12 ] [ 14 ]}

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}.}$

この式は、指数関数のテイラー級数を用いて指数生成関数を展開し、同じ指数を持つ項をまとめることで導出できます。 ^{[ 11 ]} これにより、B _nは期待値1のポアソン分布のn次モーメントとして解釈できます。

n番目のベル数は、 n番目の完全なベル多項式の係数の合計でもあり、これは任意の確率分布のn番目のモーメントを最初のn個のキュムラントの関数として表します。

ベル数はトゥシャールの合同式に従う。pが任意の素数である場合、^{[ 16 ]}

${\displaystyle B_{p+n}\equiv B_{n}+B_{n+1}{\pmod {p}}}$

または、一般化すると^{[ 17 ]}

${\displaystyle B_{p^{m}+n}\equiv mB_{n}+B_{n+1}{\pmod {p}}.}$

トゥシャールの合同式により、ベル数はすべての素数 p に対して p を法として周期的になります。例えば、p = 2 の場合、ベル数は奇数-奇数-偶数のパターンを周期 3 で繰り返します。任意の素数pに対するこの繰り返しの周期は、  

${\displaystyle {\frac {p^{p}-1}{p-1}}}$

そしてすべてのプライム${\displaystyle p\leq 101}$そして${\displaystyle p=113,163,167}$、 または${\displaystyle 173}$まさにこの番号です（ OEISのシーケンスA001039）。^{[ 18 ] [ 19 ]}

nを法とするベル数の周期は

1、3、13、12、781、39、137257、24、39、2343、28531167061、156、... （ OEISの配列A054767）

指数母関数にコーシーの積分公式を適用すると、複素積分表現が得られる。

${\displaystyle B_{n}={\frac {n!}{2\pi ie}}\int _{\gamma }{\frac {e^{e^{z}}}{z^{n+1}}}\,dz.}$

漸近表現は、最急降下法の標準的な適用によって導出することができる。^{[ 20 ]}

ベル数は対数凸数列を形成する。それらを階乗B _n / n ! で割ると、対数凹数列が得られる。^{[ 21 ] [ 22 ] [ 23 ]}

ベル数に関する漸近公式はいくつか知られている。Berend & Tassa (2010)では、以下の境界が確立された。

${\displaystyle B_{n}<\left({\frac {0.792n}{\ln(n+1)}}\right)^{n}}$すべての正の整数に対して${\displaystyle n}$;

さらに、もし${\displaystyle \varepsilon >0}$そしてすべての${\displaystyle n>n_{0}(\varepsilon )}$、

${\displaystyle B_{n}<\left({\frac {e^{-0.6+\varepsilon }n}{\ln(n+1)}}\right)^{n}}$

どこ ${\displaystyle ~n_{0}(\varepsilon )=\max \left\{e^{4},d^{-1}(\varepsilon )\right\}~}$ そして ${\displaystyle ~d(x):=\ln \ln(x+1)-\ln \ln x+{\frac {1+e^{-1}}{\ln x}}\,.}$ ベル数は、対数と同じ成長率を持つ関数であるランベルトW関数を使用して近似することもできます^{[ 24 ]。}

${\displaystyle B_{n}\sim {\frac {1}{\sqrt {n}}}\left({\frac {n}{W(n)}}\right)^{n+{\frac {1}{2}}}\exp \left({\frac {n}{W(n)}}-n-1\right).}$

モーザー＆ワイマンは1955年に拡張を確立した

${\displaystyle B_{n+h}={\frac {(n+h)!}{W(n)^{n+h}}}\times {\frac {\exp(e^{W(n)}-1)}{(2\pi B)^{1/2}}}\times \left(1+{\frac {P_{0}+hP_{1}+h^{2}P_{2}}{e^{W(n)}}}+{\frac {Q_{0}+hQ_{1}+h^{2}Q_{2}+h^{3}Q_{3}+h^{4}Q_{4}}{e^{2W(n)}}}+O(e^{-3W(n)})\right)}$

均一に${\displaystyle h=O(\ln(n))}$として${\displaystyle n\rightarrow \infty }$、 どこ${\displaystyle B}$そしてそれぞれ${\displaystyle P_{i}}$そして${\displaystyle Q_{i}}$は、${\displaystyle W(n)}$[ ^{25 ]​}

漸近式

${\displaystyle {\begin{aligned}{\frac {\ln B_{n}}{n}}&=\ln n-\ln \ln n-1+{\frac {\ln \ln n}{\ln n}}+{\frac {1}{\ln n}}+{\frac {1}{2}}\left({\frac {\ln \ln n}{\ln n}}\right)^{2}+O\left({\frac {\ln \ln n}{(\ln n)^{2}}}\right)\\&{}\qquad {\text{as }}n\to \infty \end{aligned}}}$

1981 年に de Bruijnによって設立されました。