記号的組合せ論におけるスターリング数と指数生成関数

指数生成関数(EGF)を使用してスターリング数の特性を調べることは、組み合わせ数学の古典的な演習であり、記号組み合わせ論の使用方法の標準的な例である可能性があります。また、この 2 種類の数の構成における類似点を示し、それらに使用される二項式スタイルの表記法を裏付けています。

この記事では、形式的冪級数の係数抽出演算子と、記号的組合せ論のページで説明されている組合せクラス上の (ラベル付き) 演算子 (サイクル用) および (セット用)を使用します。組合せクラスが与えられた場合、サイクル演算子は、循環対称性を考慮したある長さのサイクルに沿ってソースクラスのオブジェクトを配置することによって得られるクラスを作成し、セット演算子は、セット (対称群からの対称性、つまり「非構造化バッグ」) にソースクラスのオブジェクトを配置することによって得られるクラスを作成します。2 つの組合せクラス (追加のマーカーなしで表示) は次のとおりです。 ${\displaystyle [z^{n}]}$${\displaystyle {\mathfrak {C}}}$${\displaystyle {\mathfrak {P}}}$

• 順列（第一種符号なしスターリング数の場合）:

${\displaystyle {\mathcal {P}}=\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}})),}$

そして

• 空でない部分集合への分割（第2種スターリング数の場合）:

${\displaystyle {\mathcal {B}}=\operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})),}$

シングルトンクラスは どこにありますか。${\displaystyle {\mathcal {Z}}}$

警告: ここでスターリング数に使用されている表記法は、スターリング数に関する Wikipedia の記事の表記法とは異なります。ここでは、角括弧は符号付きスターリング数を示します。

第一種符号なしスターリング数は、[ n ]のkサイクルの順列の数を数える。順列はサイクルの集合であり、したがって順列の集合は次のように与えられる。 ${\displaystyle {\mathcal {P}}\,}$

${\displaystyle {\mathcal {P}}=\operatorname {SET} ({\mathcal {U}}\times \operatorname {CYC} ({\mathcal {Z}})),\,}$

ここで、シングルトンはサイクルを表します。この分解については、ランダム順列の統計に関するページで詳しく説明します。 ${\displaystyle {\mathcal {U}}}$

生成関数に変換すると、第一種符号なしスターリング数の混合生成関数が得られます。

${\displaystyle G(z,u)=\exp \left(u\log {\frac {1}{1-z}}\right)=\left({\frac {1}{1-z}}\right)^{u}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.}$

第一種の符号付きスターリング数は、符号なしスターリング数から次の関係式によって得られる。

${\displaystyle (-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right].}$

したがって、これらの数の 生成関数は${\displaystyle H(z,u)}$

${\displaystyle H(z,u)=G(-z,-u)=\left({\frac {1}{1+z}}\right)^{-u}=(1+z)^{u}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.}$

この生成関数を操作することで、さまざまな恒等式を導出できます。

${\displaystyle (1+z)^{u}=\sum _{n=0}^{\infty }{u \choose n}z^{n}=\sum _{n=0}^{\infty }{\frac {z^{n}}{n!}}\sum _{k=0}^{n}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}=\sum _{k=0}^{\infty }u^{k}\sum _{n=k}^{\infty }{\frac {z^{n}}{n!}}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=e^{u\log(1+z)}.}$

特に、合計の順序を交換し、導関数を取ってから、zまたはu を固定することができます。

単純な計算は${\displaystyle n\geq 2}$

${\displaystyle \sum _{k=0}^{n}(-1)^{k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=0.}$

この式が成り立つのは、和の指数生成関数が

${\displaystyle H(z,-1)={\frac {1}{1+z}}\quad {\mbox{and hence}}\quad n![z^{n}]H(z,-1)=(-1)^{n}n!.}$

無限和には次のようなものがある。

${\displaystyle \sum _{n=k}^{\infty }\left[{\begin{matrix}n\\k\end{matrix}}\right]{\frac {z^{n}}{n!}}={\frac {\left(-\log(1-z)\right)^{k}}{k!}}}$

ここで（ のに最も近い特異点は にあります） ${\displaystyle |z|<1}$${\displaystyle z=0}$${\displaystyle \log(1+z)}$${\displaystyle z=-1.}$

この関係は、

${\displaystyle [u^{k}]H(z,u)=[u^{k}]\exp \left(u\log(1+z)\right)={\frac {\left(\log(1+z)\right)^{k}}{k!}}.}$

これらの数は[ n ]をk個の空でない部分集合に分割する回数を数える。まず、分割の総数、すなわちBn_を考える。

${\displaystyle B_{n}=\sum _{k=1}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}{\mbox{ and }}B_{0}=1,}$

すなわち、ベル数である。フラジョレ・セジウィック基本定理が適用される（ラベル付きの場合）。空でない部分集合への分割集合は、（「空でない単独集合の集合」）で与えられる。 ${\displaystyle {\mathcal {B}}\,}$

${\displaystyle {\mathcal {B}}=\operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})).}$

この分解は、次のように表されるサイクルからの順列の集合 の構築と完全に類似している。${\displaystyle {\mathcal {P}}\,}$

${\displaystyle {\mathcal {P}}=\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}})).}$

そして、第一種スターリング数を生成します。そのため、「第二種スターリング数」と呼ばれます。

分解はEGFと同等である

${\displaystyle B(z)=\exp \left(\exp z-1\right).}$

微分して得る

${\displaystyle {\frac {d}{dz}}B(z)=\exp \left(\exp z-1\right)\exp z=B(z)\exp z,}$

これは、

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k},}$

指数生成関数の畳み込みによって、また EGF を微分すると最初の係数が削除され、B _{n +1 が}z ⁿ / nにシフトされるためです。  

第二種スターリング数のEGFは、分割に入るすべての部分集合を という項でマークすることによって得られ、 ${\displaystyle {\mathcal {U}}\,}$

${\displaystyle {\mathcal {B}}=\operatorname {SET} ({\mathcal {U}}\times \operatorname {SET} _{\geq 1}({\mathcal {Z}})).}$

これを生成関数に翻訳すると、

${\displaystyle B(z,u)=\exp \left(u\left(\exp z-1\right)\right).}$

この EGF は、第 2 種のスターリング数の式を生成します。

${\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=n![u^{k}][z^{n}]B(z,u)=n![z^{n}]{\frac {(\exp z-1)^{k}}{k!}}}$

または

${\displaystyle n![z^{n}]{\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}\exp(jz)(-1)^{k-j}}$

これは次のように単純化される

${\displaystyle {\frac {n!}{k!}}\sum _{j=0}^{k}{k \choose j}(-1)^{k-j}{\frac {j^{n}}{n!}}={\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}(-1)^{k-j}j^{n}.}$

• ロナルド・グラハム、ドナルド・クヌース、オーレン・パタシュニック（1989）：『具体的な数学』、アディソン・ウェズレー、ISBN  0-201-14236-8
• DS Mitrinovic、Sur une classe de nombre relies aux nombres de Stirling、CR Acad。科学。パリ 252 (1961)、2354–2356。
• ACR ベルトン、「単調なポアソン過程」、量子確率（M. ボゼコ、W. ムロトコフスキー、J. ウィソクザンスキー編）、バナッハ センター出版 73、ポーランド科学アカデミー、ワルシャワ、2006 年
• ミルトン・アブラモウィッツとアイリーン・A・ステガン、『数式、グラフ、数学表付き数学関数ハンドブック』、USGPO、1964年、ワシントンDC、ISBN 0-486-61272-4