第一種スターリング数

数学、特に組合せ論 において、第一種スターリング数は順列の研究において用いられる。特に、第一種符号なしスターリング数は順列をその循環数（固定点を長さ1の循環として数える）に応じて数える。^[1]

第一種スターリング数と第二種スターリング数は、三角行列として見ると、互いの逆行列として理解できます。この記事では、第一種スターリング数の詳細について説明します。2つの種を結びつける恒等式については、スターリング数に関する記事をご覧ください。

定義

代数による定義

第一種スターリング数は、階乗の展開における係数である。${\displaystyle s(n,k)}$

${\displaystyle (x)_{n}=x(x-1)(x-2)\cdots (x-n+1)}$

変数のべき乗に： ${\displaystyle x}$

${\displaystyle (x)_{n}=\sum _{k=0}^{n}s(n,k)x^{k},}$

たとえば、 の場合、値、、 が得られます。 ${\displaystyle (x)_{3}=x(x-1)(x-2)=x^{3}-3x^{2}+2x}$ ${\displaystyle s(3,3)=1}$ ${\displaystyle s(3,2)=-3}$ ${\displaystyle s(3,1)=2}$

符号なしスターリング数は、上昇階乗の係数として代数的に定義することもできます。

${\displaystyle x^{\overline {n}}=x(x+1)\cdots (x+n-1)=\sum _{k=0}^{n}\left[{n \atop k}\right]x^{k}}$ 。

このページで使用されているスターリング数の表記法は普遍的なものではなく、他の資料の表記法と矛盾する可能性があります。角括弧表記法はガウス係数の一般的な表記法でもあります。^[2]${\displaystyle \left[{n \atop k}\right]}$

順列による定義

その後、これらの数の絶対値は、特定の種類の順列の数に等しいことが発見されました。これらの絶対値は第一種符号なしスターリング数として知られ、しばしばまたは と表記されます。これらは、互いに素な閉路を持つ元の順列の数として直接定義することもできます。^[1]${\displaystyle |s(n,k)|}$ ${\displaystyle c(n,k)}$ ${\displaystyle \left[{n \atop k}\right]}$ ${\displaystyle n}$ ${\displaystyle k}$

例えば、3つの要素の順列のうち、3つの循環を持つ順列（恒等順列、1行表記では 、循環表記では で表されます）、2つの循環を持つ順列（ 、、 ）が3つ、そして1つの循環を持つ順列（ 、）が2つあります。したがって、 、、 です。これらは、に対するの前述の代数計算と一致することがわかります。${\displaystyle 3!=6}$ ${\displaystyle 123}$ ${\displaystyle (1)(2)(3)}$ ${\displaystyle 132=(1)(23)}$ ${\displaystyle 213=(12)(3)}$ ${\displaystyle 321=(13)(2)}$ ${\displaystyle 312=(132)}$ ${\displaystyle 231=(123)}$ ${\displaystyle \left[{3 \atop 3}\right]=1}$ ${\displaystyle \left[{3 \atop 2}\right]=3,}$ ${\displaystyle \left[{3 \atop 1}\right]=2}$ ${\displaystyle s(n,k)}$ ${\displaystyle n=3}$

s(4,2)=11

別の例として、右の図は、 4つのオブジェクト上の対称群には、次の形式の3つの順列がある ことを示しています。${\displaystyle \left[{4 \atop 2}\right]=11}$

${\displaystyle (\bullet \bullet )(\bullet \bullet )}$ （軌道が2つあり、それぞれサイズが2）

そして、8つの順列がある。

${\displaystyle (\bullet \bullet \bullet )(\bullet )}$ (サイズ 3 の軌道が 1 つとサイズ 1 の軌道が 1 つあります)。

これらの数は、軌道を共役類とみなすことで計算できます。アルフレッド・レーニは、第一種符号なしスターリング数が、 左から右への最大値を持つサイズの順列の数も数えることを観察しました。^[3]${\displaystyle \left[{n \atop k}\right]}$ ${\displaystyle n}$ ${\displaystyle k}$

標識

第一種符号付きスターリング数の符号はn − kの偶奇性のみに依存します。

${\displaystyle s(n,k)=(-1)^{n-k}\left[{n \atop k}\right].}$

再帰関係

第一種符号なしスターリング数は再帰関係に従う

${\displaystyle \left[{n+1 \atop k}\right]=n\left[{n \atop k}\right]+\left[{n \atop k-1}\right]}$

の場合、境界条件 ${\displaystyle k>0}$

${\displaystyle \left[{0 \atop 0}\right]=1\quad {\mbox{and}}\quad \left[{n \atop 0}\right]=\left[{0 \atop n}\right]=0}$

のために。^[2]${\displaystyle n>0}$

第一種符号スターリング数は、次の再帰性を満たすことが直ちに分かる。

${\displaystyle s(n+1,k)=-n\cdot s(n,k)+s(n,k-1)}$ 。

代数的証明

スターリング数の定義を階乗の項を用いて用いて、漸化式を証明する。積の最後の項を分配すると、

${\displaystyle x^{\overline {n+1}}=x(x+1)\cdots (x+n-1)(x+n)=n\cdot x^{\overline {n}}+x\cdot x^{\overline {n}}.}$

この式の左辺におけるの係数は です。におけるの係数はであり、におけるの係数は です。両辺は多項式として等しいので、両辺における の係数は等しくなければならず、結果は次のようになります。 ${\displaystyle x^{k}}$ ${\displaystyle \left[{n+1 \atop k}\right]}$ ${\displaystyle x^{k}}$ ${\displaystyle n\cdot x^{\overline {n}}}$ ${\displaystyle n\cdot \left[{n \atop k}\right]}$ ${\displaystyle x^{k}}$ ${\displaystyle x\cdot x^{\overline {n}}}$ ${\displaystyle \left[{n \atop k-1}\right]}$ ${\displaystyle x^{k}}$

組み合わせ論的証明

与えられたサイクル数（またはそれと同等の軌道）を持つ順列に関してスターリング数の定義を使用して再帰関係を証明します。

オブジェクトの順列に、区別できるオブジェクトを追加することで、オブジェクトの順列を形成することを考えてみましょう。これを実現するには、正確に2つの方法があります。まず、単項循環を形成する、つまり、追加のオブジェクトをそのまま残すという方法があります。これにより循環の数が1増え、漸化式の項が説明されます。また、新しいオブジェクトを既存の循環の1つに挿入することもできます。循環を持つオブジェクトの任意の順列を考え、オブジェクトにラベルを付けると、順列は次のように表されます。 ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle \left[{n \atop k-1}\right]}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle a_{1},\dots ,a_{n}}$

${\displaystyle \displaystyle \underbrace {(a_{1}\ldots a_{j_{1}})(a_{j_{1}+1}\ldots a_{j_{2}})\ldots (a_{j_{k-1}+1}\ldots a_{n})} _{k\ \mathrm {cycles} }.}$

オブジェクトと循環の新しい順列を形成するには、この配列に新しいオブジェクトを挿入する必要があります。この挿入には複数の方法があり、既存のオブジェクトのいずれかの直後に新しいオブジェクトを挿入します。これが「再帰関係」という用語の由来です。これら2つのケースはすべての可能性を含んでいるため、再帰関係は成り立ちます。 ${\displaystyle n+1}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle a_{i}}$ ${\displaystyle n\left[{n \atop k}\right]}$

値の表

以下は、パスカルの三角形に似た、第一種スターリング数の符号なし値の三角形配列です。これらの値は、前の節の再帰関係を用いて簡単に生成できます。

け n	0	1	2	3	4	5	6	7	8	9	10
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1
7	0	720	1764	1624	735	175	21	1
8	0	5040	13068	13132	6769	1960	322	28	1
9	0	40320	109584	118124	67284	22449	4536	546	36	1
10	0	362880	1026576	1172700	723680	269325	63273	9450	870	45	1

プロパティ

シンプルなアイデンティティ

クロネッカーのデルタを使うと、

${\displaystyle \left[{n \atop 0}\right]=\delta _{n}}$

そして

${\displaystyle \left[{0 \atop k}\right]=0}$ 、またはより一般的にはk > nの場合。${\displaystyle k>0}$ ${\displaystyle \left[{n \atop k}\right]=0}$

また

${\displaystyle \left[{n \atop 1}\right]=(n-1)!,\quad \left[{n \atop n}\right]=1,\quad \left[{n \atop n-1}\right]={n \choose 2},}$

そして

${\displaystyle \left[{n \atop n-2}\right]={\frac {3n-1}{4}}{n \choose 3}\quad {\mbox{ and }}\quad \left[{n \atop n-3}\right]={n \choose 2}{n \choose 4}.}$

スターリング数に関する同様の関係は、ベルヌーイ多項式にも当てはまる。スターリング数に関する多くの関係は、二項係数に関する同様の関係を覆い隠している。これらの「覆い隠された関係」の研究は、アンブラル計算と呼ばれ、シェファー列の理論に集約される。両種類のスターリング数を任意の複素数値入力に一般化することは、これらの三角形とスターリング畳み込み多項式との関係を通じて拡張できる。^[4]

組み合わせ論的証明

これらの恒等式は、順列を直接列挙することによって導出できる。例えば、n − 3 個の循環を持つn個の要素の順列は 、次のいずれかの形式をとる必要がある。

• n  − 6個の固定点と3個の2サイクル
• n  − 5 個の固定点、3 サイクルと 2 サイクル、または
• n  − 4 個の固定点と 4 サイクル。

3 つのタイプは次のようになります。

• 2 つのサイクルに入る 6 つの要素を選択し、それらを 2 つのサイクルに分解します。サイクルの順序は重要ではないことを考慮します。

${\displaystyle {n \choose 6}{6 \choose 2,2,2}{\frac {1}{6}}}$

• 3 サイクルと 2 サイクルに入る 5 つの要素を選択し、3 サイクルの要素を選択し、3 つの要素が 2 つの 3 サイクルを生成することを考慮に入れます。

${\displaystyle {n \choose 5}{5 \choose 3}\times 2}$

• 4 サイクルの 4 つの要素を選択し、4 つの要素から 6 つの 4 サイクルが生成されることに注意してください。

${\displaystyle {n \choose 4}\times 6.}$

3つの貢献を合計すると

${\displaystyle {n \choose 6}{6 \choose 2,2,2}{\frac {1}{6}}+{n \choose 5}{5 \choose 3}\times 2+{n \choose 4}\times 6={n \choose 2}{n \choose 4}.}$

上記のすべての組み合わせ証明では、 の二項式または多項式のいずれかが使用されていることに注意してください。 ${\displaystyle n}$

したがって、が素数の場合、次のようになります。 ${\displaystyle p}$

${\displaystyle p\ |\left[{p \atop k}\right]}$ のために。 ${\displaystyle 1<k<p}$

固定の拡張け

スターリング数は根が0, 1, ..., n − 1である多項式の係数なので、ヴィエタの公式に よれば、

$${\displaystyle \left[{\begin{matrix}n\\n-k\end{matrix}}\right]=\sum _{0\leq i_{1}<\ldots <i_{k}<n}i_{1}i_{2}\cdots i_{k}.}$$

言い換えれば、第一種スターリング数は0, 1, ..., n − 1で評価される基本対称多項式で与えられる。^[5] この形式では、上記の単純な恒等式は次の形を取る。

$${\displaystyle \left[{\begin{matrix}n\\n-1\end{matrix}}\right]=\sum _{i=0}^{n-1}i={\binom {n}{2}},}$$ $${\displaystyle \left[{\begin{matrix}n\\n-2\end{matrix}}\right]=\sum _{i=0}^{n-1}\sum _{j=0}^{i-1}ij={\frac {3n-1}{4}}{\binom {n}{3}},}$$ $${\displaystyle \left[{\begin{matrix}n\\n-3\end{matrix}}\right]=\sum _{i=0}^{n-1}\sum _{j=0}^{i-1}\sum _{k=0}^{j-1}ijk={\binom {n}{2}}{\binom {n}{4}},}$$ 等々。

同様のアプローチに代数的操作を加えることで、第一種スターリング数の別の形を作り出すこともできる。

${\displaystyle (x+1)(x+2)\cdots (x+n-1)=(n-1)!\cdot (x+1)\left({\frac {x}{2}}+1\right)\cdots \left({\frac {x}{n-1}}+1\right),}$

ニュートンの公式から、第一種スターリング数を一般化調和数で展開できることがわかる。これにより、次のような恒等式が得られる。

${\displaystyle \left[{n \atop 2}\right]=(n-1)!\;H_{n-1},}$

${\displaystyle \left[{n \atop 3}\right]={\frac {1}{2}}(n-1)!\left[(H_{n-1})^{2}-H_{n-1}^{(2)}\right]}$

${\displaystyle \left[{n \atop 4}\right]={\frac {1}{3!}}(n-1)!\left[(H_{n-1})^{3}-3H_{n-1}H_{n-1}^{(2)}+2H_{n-1}^{(3)}\right],}$

ここでH _nは調和数 、H _n ^{( m )}は一般化調和数である。 ${\displaystyle H_{n}={\frac {1}{1}}+{\frac {1}{2}}+\ldots +{\frac {1}{n}}}$ $${\displaystyle H_{n}^{(m)}={\frac {1}{1^{m}}}+{\frac {1}{2^{m}}}+\ldots +{\frac {1}{n^{m}}}.}$$

これらの関係は次のように一般化できる。

${\displaystyle {\frac {1}{(n-1)!}}\left[{\begin{matrix}n\\k+1\end{matrix}}\right]=\sum _{i_{1}=1}^{n-1}\sum _{i_{2}=i_{1}+1}^{n-1}\cdots \sum _{i_{k}=i_{k-1}+1}^{n-1}{\frac {1}{i_{1}i_{2}\cdots i_{k}}}={\frac {w(n,k)}{k!}}}$

ここで、w ( n , m )は一般化調和数を用いて再帰的に定義される。

${\displaystyle w(n,m)=\delta _{m,0}+\sum _{k=0}^{m-1}(1-m)_{k}H_{n-1}^{(k+1)}w(n,m-1-k).}$

（ここでδはクロネッカーのデルタ関数であり、はポッホハマー記号である。）^[6]${\displaystyle (m)_{k}}$

固定の場合、これらの重み付き調和数展開は生成関数によって生成される。 ${\displaystyle n\geq 0}$

${\displaystyle {\frac {1}{n!}}\left[{\begin{matrix}n+1\\k\end{matrix}}\right]=[x^{k}]\exp \left(\sum _{m\geq 1}{\frac {(-1)^{m-1}H_{n}^{(m)}}{m}}x^{m}\right),}$

ここで、表記は、次の形式的な冪級数から係数を抽出することを意味します（非指数ベル多項式と^[7]の第3節を参照）。 ${\displaystyle [x^{k}]}$ ${\displaystyle x^{k}}$

より一般的には、第一種スターリング数のこれらの重み付き調和数展開に関連する和は、生成関数の一般化ゼータ級数変換を通じて定義できます。^{[8] [9]}

次調和数で与えられたこれらのスターリング数の関係を「逆転」させて、整数次一般調和数を第一種スターリング数を含む項の重み付き和で表すこともできる。例えば、二次および三次の調和数が次のように与えられる 場合、${\displaystyle k}$ ${\displaystyle k=2,3}$

${\displaystyle (n!)^{2}\cdot H_{n}^{(2)}=\left[{\begin{matrix}n+1\\2\end{matrix}}\right]^{2}-2\left[{\begin{matrix}n+1\\1\end{matrix}}\right]\left[{\begin{matrix}n+1\\3\end{matrix}}\right]}$

${\displaystyle (n!)^{3}\cdot H_{n}^{(3)}=\left[{\begin{matrix}n+1\\2\end{matrix}}\right]^{3}-3\left[{\begin{matrix}n+1\\1\end{matrix}}\right]\left[{\begin{matrix}n+1\\2\end{matrix}}\right]\left[{\begin{matrix}n+1\\3\end{matrix}}\right]+3\left[{\begin{matrix}n+1\\1\end{matrix}}\right]^{2}\left[{\begin{matrix}n+1\\4\end{matrix}}\right].}$

より一般的には、スターリング数のベル多項式生成関数を-次調和数で展開して逆変換すると、整数に対するベル多項式生成関数が得られる。${\displaystyle m}$ ${\displaystyle m\geq 2}$

${\displaystyle H_{n}^{(m)}=-m\times [x^{m}]\log \left(1+\sum _{k\geq 1}\left[{\begin{matrix}n+1\\k+1\end{matrix}}\right]{\frac {(-x)^{k}}{n!}}\right).}$

有限和

順列は循環の数によって分割されるので、

${\displaystyle \sum _{k=0}^{n}\left[{n \atop k}\right]=n!}$

アイデンティティ

${\displaystyle \sum _{k=0}^{n}\left[{n \atop k}\right]u^{k}=n!{\binom {n+u-1}{u-1}},\,u>0}$

そして

${\displaystyle \sum _{p=k}^{n}{\left[{n \atop p}\right]{\binom {p}{k}}}=\left[{n+1 \atop k+1}\right]}$

スターリング数と指数生成関数#第一種スターリング数と二項係数#通常の生成関数の手法で証明できます 。

『具体的数学』第6.1節の表には、スターリング数を含む有限和の一般化された形式が多数示されています。本稿に関連する具体的な有限和としては、以下のものがあります。

${\displaystyle {\begin{aligned}\left[{n \atop m}\right]&=\sum _{k=m}^{n}\left[{n+1 \atop k+1}\right]{\binom {k}{m}}(-1)^{m-k}\\\left[{n+1 \atop m+1}\right]&=\sum _{k=m}^{n}\left[{k \atop m}\right]{\frac {n!}{k!}}\\\left[{m+n+1 \atop m}\right]&=\sum _{k=0}^{m}(n+k)\left[{n+k \atop k}\right]\\\left[{n \atop l+m}\right]{\binom {l+m}{l}}&=\sum _{k}\left[{k \atop l}\right]\left[{n-k \atop m}\right]{\binom {n}{k}}.\end{aligned}}}$

さらに、 2階オイラー数を三角再帰関係^[10]で定義すると、

${\displaystyle \left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle =(k+1)\left\langle \!\!\left\langle {n-1 \atop k}\right\rangle \!\!\right\rangle +(2n-1-k)\left\langle \!\!\left\langle {n-1 \atop k-1}\right\rangle \!\!\right\rangle ,}$

スターリング畳み込み多項式の形式に関連する次の恒等式に到達します。これを使用して、スターリング数三角形の両方を入力の任意の実数値または複素数値に一般化できます。 ${\displaystyle x}$

${\displaystyle \left[{x \atop x-n}\right]=\sum _{k=0}^{n}\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle {\binom {x+k}{2n}}.}$

前の恒等式の特別な展開により、 の最初のいくつかの小さな値に対して第一種スターリング数を展開する次の恒等式が得られます。 ${\displaystyle n:=1,2,3}$

${\displaystyle {\begin{aligned}\left[{\begin{matrix}x\\x-1\end{matrix}}\right]&={\binom {x}{2}}\\\left[{\begin{matrix}x\\x-2\end{matrix}}\right]&={\binom {x}{4}}+2{\binom {x+1}{4}}\\\left[{\begin{matrix}x\\x-3\end{matrix}}\right]&={\binom {x}{6}}+8{\binom {x+1}{6}}+6{\binom {x+2}{6}}.\end{aligned}}}$

スターリング数とオイラー数を含む有限和を扱うためのソフトウェアツールは、MathematicaのRISC Stirling.mパッケージユーティリティによって提供されています。スターリング数やその他の特殊な三角形を含む数列（および多項式数列の和）の式を推測するためのソフトウェアパッケージは、 Mathematica用（こちら）とSage用（こちら）の両方で利用可能です。^[11]

合同性

次の合同性は生成関数に基づくアプローチによって証明できる：^[12]

${\displaystyle {\begin{aligned}\left[{\begin{matrix}n\\m\end{matrix}}\right]&\equiv {\binom {\lfloor n/2\rfloor }{m-\lceil n/2\rceil }}=[x^{m}]\left(x^{\lceil n/2\rceil }(x+1)^{\lfloor n/2\rfloor }\right)&&{\pmod {2}},\end{aligned}}}$

より最近の結果は、単一の階乗関数と一般化された階乗関連積を生成するヤコビ型J分数を提供し、第一種スターリング数に対する他の新しい合同な結果につながる。^[13] 例えば、法を作用させて、次のことを証明できる。 ${\displaystyle 2}$

${\displaystyle {\begin{aligned}\left[{\begin{matrix}n\\1\end{matrix}}\right]&\equiv {\frac {2^{n}}{4}}[n\geq 2]+[n=1]&&{\pmod {2}}\\\left[{\begin{matrix}n\\2\end{matrix}}\right]&\equiv {\frac {3\cdot 2^{n}}{16}}(n-1)[n\geq 3]+[n=2]&&{\pmod {2}}\\\left[{\begin{matrix}n\\3\end{matrix}}\right]&\equiv 2^{n-7}(9n-20)(n-1)[n\geq 4]+[n=3]&&{\pmod {2}}\\\left[{\begin{matrix}n\\4\end{matrix}}\right]&\equiv 2^{n-9}(3n-10)(3n-7)(n-1)[n\geq 5]+[n=4]&&{\pmod {2}}\end{aligned}}}$

アイバーソンブラケットはどこですか？ ${\displaystyle [b]}$

そして法を当てはめて同様に証明できる。 ${\displaystyle 3}$

${\displaystyle {\begin{aligned}\left[{\begin{matrix}n\\m\end{matrix}}\right]&\equiv [x^{m}](x^{\lceil n/3\rceil }(x+1)^{\lceil (n-1)/3\rceil }(x+2)^{\lfloor n/3\rfloor }&&{\pmod {3}}\\&\equiv \sum _{k=0}^{m}{\binom {\lceil (n-1)/3\rceil }{k}}{\binom {\lfloor n/3\rfloor }{m-k-\lfloor n/3\rfloor }}2^{\lceil n/3\rceil +\lfloor n/3\rfloor -m+k}&&{\pmod {3}}\end{aligned}}}$

より一般的には、固定整数に対して、順序根を定義すると、 ${\displaystyle h\geq 3}$

${\displaystyle \left(\omega _{h,i}\right)_{i=1}^{h-1}:=\left\{\omega _{j}:\sum _{i=0}^{h-1}{\binom {h-1}{i}}{\frac {h!}{(i+1)!}}(-\omega _{j})^{i}=0,\ 1\leq j<h\right\},}$

すると、これらのスターリング数の合同式を係数として展開することができる。

${\displaystyle \left[{\begin{matrix}n\\m\end{matrix}}\right]=[R^{m}]R(R+1)\cdots (R+n-1),}$

次の形式では、関数、、は、それぞれ、、、およびについて、次数 の固定多項式を表します。 ${\displaystyle p_{h,i}^{[m]}(n)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle h}$ ${\displaystyle m}$ ${\displaystyle i}$

${\displaystyle \left[{\begin{matrix}n\\m\end{matrix}}\right]=\left(\sum _{i=0}^{h-1}p_{h,i}^{[m]}(n)\times \omega _{h,i}^{n}\right)[n>m]+[n=m]\qquad {\pmod {h}},}$

上記の参考文献のセクション6.2では、次調和数と一般化階乗積、に対するこれらの合同性に関するより明示的な展開が示さ れています。${\displaystyle r}$ ${\displaystyle p_{n}(\alpha ,R):=R(R+\alpha )\cdots (R+(n-1)\alpha )}$

生成関数

生成関数を操作することで、さまざまな恒等式を導くことができます（基底変換を参照）。

${\displaystyle H(z,u)=(1+z)^{u}=\sum _{n=0}^{\infty }{u \choose n}z^{n}=\sum _{n=0}^{\infty }{\frac {z^{n}}{n!}}\sum _{k=0}^{n}s(n,k)u^{k}=\sum _{k=0}^{\infty }u^{k}\sum _{n=k}^{\infty }{\frac {z^{n}}{n!}}s(n,k).}$

等式を使って

${\displaystyle (1+z)^{u}=e^{u\log(1+z)}=\sum _{k=0}^{\infty }(\log(1+z))^{k}{\frac {u^{k}}{k!}},}$

すると

${\displaystyle \sum _{n=k}^{\infty }s(n,k){\frac {z^{n}}{n!}}={\frac {(\log(1+z))^{k}}{k!}}}$

そして

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

この恒等式は形式的な冪級数に対して有効であり、その和は複素平面上で| z | < 1 に対して収束します。

他の恒等式は、和の順序を入れ替えたり、導関数をとったり、zやuを代入したりすることで得られる。例えば、次のように導出できる。^[14]

${\displaystyle {\frac {\log ^{m}(1+z)}{1+z}}=m!\sum _{k=0}^{\infty }{\frac {s(k+1,m+1)\,z^{k}}{k!}},\qquad m=1,2,3,\ldots \quad |z|<1}$

または

${\displaystyle \sum _{n=i}^{\infty }{\frac {\left[{n \atop i}\right]}{n\,(n!)}}=\zeta (i+1),\qquad i=1,2,3,\ldots }$

そして

${\displaystyle \sum _{n=i}^{\infty }{\frac {\left[{n \atop i}\right]}{n\,(v)_{n}}}=\zeta (i+1,v),\qquad i=1,2,3,\ldots \quad \Re (v)>0}$

ここで、とはそれぞれリーマンゼータ関数とフルヴィッツゼータ関数であり、この積分を評価することもできる。 ${\displaystyle \zeta (k)}$ ${\displaystyle \zeta (k,v)}$

${\displaystyle \int _{0}^{1}{\frac {\log ^{z}(1-x)}{x^{k}}}\,dx={\frac {(-1)^{z}\Gamma (z+1)}{(k-1)!}}\sum _{r=1}^{k-1}s(k-1,r)\sum _{m=0}^{r}{\binom {r}{m}}(k-2)^{r-m}\zeta (z+1-m),\qquad \Re (z)>k-1,\quad k=3,4,5,\ldots }$

ここではガンマ関数です。スターリング数を含むゼータ関数には、より複雑な表現も存在します。例えば、 ${\displaystyle \Gamma (z)}$

${\displaystyle \zeta (s,v)={\frac {k!}{(s-k)_{k}}}\sum _{n=0}^{\infty }{\frac {1}{(n+k)!}}\left[{n+k \atop n}\right]\sum _{l=0}^{n+k-1}\!(-1)^{l}{\binom {n+k-1}{l}}(l+v)^{k-s},\quad k=1,2,3,\ldots }$

この級数はハッセ級数をフルヴィッツゼータ関数に対して一般化したものである（ハッセ級数はk = 1と設定することで得られる）。^{[15] [16]}

漸近解析

オイラーガンマ定数を用いた次の推定値が適用される：^[17]

${\displaystyle \left[{\begin{matrix}n+1\\k+1\end{matrix}}\right]{\underset {n\to \infty }{\sim }}{\frac {n!}{k!}}\left(\gamma +\ln n\right)^{k},\ {\text{ uniformly for }}k=o(\ln n).}$

固定の場合、次の推定値が得られます。 ${\displaystyle n}$

${\displaystyle \left[{\begin{matrix}n+k\\k\end{matrix}}\right]{\underset {k\to \infty }{\sim }}{\frac {k^{2n}}{2^{n}n!}}.}$

明示的な式

第一種スターリング数に対する一和公式は現在のところ知られていない。スターリング数の対称公式の一つと第二種スターリング数の明示的公式を組み合わせることで、二和公式が得られる。

${\displaystyle \left[{n \atop k}\right]=\sum _{j=n}^{2n-k}{\binom {j-1}{k-1}}{\binom {2n-k}{j}}\sum _{m=0}^{j-n}{\frac {(-1)^{m+n-k}m^{j-k}}{m!(j-n-m)!}}}$

先に述べたように、ヴィエタの公式により、次の式が得られる。スターリング数s(n,np)は^[18]式から求められる。$${\displaystyle \left[{\begin{matrix}n\\k\end{matrix}}\right]=\sum _{0\leq i_{1}<\ldots <i_{n-k}<n}i_{1}i_{2}\cdots i_{n-k}.}$$

${\displaystyle {\begin{aligned}s(n,n-p)&={\frac {1}{(n-p-1)!}}\sum _{0\leq k_{1},\ldots ,k_{p}:\sum _{1}^{p}mk_{m}=p}(-1)^{K}{\frac {(n+K-1)!}{k_{1}!k_{2}!\cdots k_{p}!~2!^{k_{1}}3!^{k_{2}}\cdots (p+1)!^{k_{p}}}},\end{aligned}}}$

ここで、合計はpのすべてのパーティションの 合計です。 ${\displaystyle K=k_{1}+\cdots +k_{p}.}$

これらのスターリング数に対するもう一つの正確な入れ子和展開は、形式の積の係数に対応する基本対称多項式によって計算される。特に、 ${\displaystyle x}$ ${\displaystyle (1+c_{1}x)\cdots (1+c_{n-1}x)}$

${\displaystyle {\begin{aligned}\left[{n \atop k+1}\right]&=[x^{k}](x+1)(x+2)\cdots (x+n-1)=(n-1)!\cdot [x^{k}](x+1)\left({\frac {x}{2}}+1\right)\cdots \left({\frac {x}{n-1}}+1\right)\\&=\sum _{1\leq i_{1}<\cdots <i_{k}<n}{\frac {(n-1)!}{i_{1}\cdots i_{k}}}.\end{aligned}}}$

上記の展開と組み合わせたニュートンの恒等式は、すでに上で述べた一般化された調和数を含む重み付き展開の別の証明を与えるために使用できます。

自然対数関数との関係

自然対数のμ乗のn階微分には、第一種符号付きスターリング数が含まれる。

${\displaystyle {\operatorname {d} ^{n}\!(\ln x)^{\mu } \over \operatorname {d} \!x^{n}}=x^{-n}\sum _{k=1}^{n}\mu ^{\underline {k}}s(n,n-k+1)(\ln x)^{\mu -k},}$

ここで、 は下降階乗、 は符号付きスターリング数です。 ${\displaystyle \mu ^{\underline {i}}}$ ${\displaystyle s(n,n-k+1)}$

それは数学的帰納法を使って証明することができます。

その他の式

第一種スターリング数はグレゴリー係数の公式やベル数を含む有限和恒等式に現れる^[19]

${\displaystyle n!G_{n}=\sum _{l=0}^{n}{\frac {s(n,l)}{l+1}}}$

${\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}}$

スターリング数を含む有限和を含む無限級数は、しばしば特殊関数を導く。例えば^{[14] [20]}

${\displaystyle \ln \Gamma (z)=\left(z-{\frac {1}{2}}\right)\!\ln z-z+{\frac {1}{2}}\ln 2\pi +{\frac {1}{\pi }}\sum _{n=1}^{\infty }{\frac {1}{n\cdot n!}}\!\sum _{l=0}^{\lfloor n/2\rfloor }\!{\frac {(-1)^{l}(2l)!}{(2\pi z)^{2l+1}}}\left[{n \atop 2l+1}\right]}$

そして

${\displaystyle \Psi (z)=\ln z-{\frac {1}{2z}}-{\frac {1}{\pi z}}\sum _{n=1}^{\infty }{\frac {1}{n\cdot n!}}\!\sum _{l=0}^{\lfloor n/2\rfloor }\!{\frac {(-1)^{l}(2l+1)!}{(2\pi z)^{2l+1}}}\left[{n \atop 2l+1}\right]}$

あるいは

${\displaystyle \gamma _{m}={\frac {1}{2}}\delta _{m,0}+{\frac {(-1)^{m}m!}{\pi }}\!\sum _{n=1}^{\infty }{\frac {1}{n\cdot n!}}\!\sum _{k=0}^{\lfloor n/2\rfloor }{\frac {(-1)^{k}}{(2\pi )^{2k+1}}}\left[{2k+2 \atop m+1}\right]\left[{n \atop 2k+1}\right]\,}$

ここでγ _mはスティルチェス定数、δ _{m ,0は}クロネッカーのデルタ関数を表します。

この最後の恒等式は、多重対数関数、上記に示したスターリング数指数生成関数、および一般化されたニールセン多重対数関数のスターリング数ベースのべき級数間の関係を直ちに意味することに注意してください。

一般化

一般化スターリング数の概念は数多く存在し、応用に応じて様々な組み合わせ論的文脈で定義される。第一種スターリング数は、単一の階乗関数 ,の異なる多項式展開の係数に対応するため、この概念を拡張して、より一般的な積のクラスに対する三角漸化式を定義することができる。 ${\displaystyle n!=n(n-1)(n-2)\cdots 2\cdot 1}$

特に、任意の固定された算術関数と記号パラメータに対して、次の形式の関連する一般化階乗積が成り立つ。 ${\displaystyle f:\mathbb {N} \rightarrow \mathbb {C} }$ ${\displaystyle x,t}$

${\displaystyle (x)_{n,f,t}:=\prod _{k=1}^{n-1}\left(x+{\frac {f(k)}{t^{k}}}\right)}$

は、の展開における のべき乗の次の係数によって定義される第一種一般化スターリング数のクラスの観点から研究することができ、次に次の対応する三角漸化式によって研究することができる。 ${\displaystyle x}$ ${\displaystyle (x)_{n,f,t}}$

${\displaystyle {\begin{aligned}\left[{\begin{matrix}n\\k\end{matrix}}\right]_{f,t}&=[x^{k-1}](x)_{n,f,t}\\&=f(n-1)t^{1-n}\left[{\begin{matrix}n-1\\k\end{matrix}}\right]_{f,t}+\left[{\begin{matrix}n-1\\k-1\end{matrix}}\right]_{f,t}+\delta _{n,0}\delta _{k,0}.\end{aligned}}}$

これらの係数は、第一種スターリング数およびf調和数に関連する再帰関係と関数方程式と同様の多くの性質を満たしています。^[21]${\displaystyle F_{n}^{(r)}(t):=\sum _{k\leq n}t^{k}/f(k)^{r}}$

に対応するこれらの括弧付き係数の特別なケースにより、多重階乗関数または多階乗関数を の多項式として展開することができます。^[22]${\displaystyle t\equiv 1}$ ${\displaystyle n}$

両方の種類のスターリング数、二項係数、および1次と2次のオイラー数はすべて、次の形式の 三角形の超回帰の特別なケースとして定義されます。

${\displaystyle \left|{\begin{matrix}n\\k\end{matrix}}\right|=(\alpha n+\beta k+\gamma )\left|{\begin{matrix}n-1\\k\end{matrix}}\right|+(\alpha ^{\prime }n+\beta ^{\prime }k+\gamma ^{\prime })\left|{\begin{matrix}n-1\\k-1\end{matrix}}\right|+\delta _{n,0}\delta _{k,0},}$

整数に対しては となり、 または の場合は常にとなります。この意味で、第一種スターリング数の形は、固定スカラー（すべてゼロではない）に対するこのパラメータ化された超再帰によって一般化することもできます。 ${\displaystyle n,k\geq 0}$ ${\displaystyle \left|{\begin{matrix}n\\k\end{matrix}}\right|\equiv 0}$ ${\displaystyle n<0}$ ${\displaystyle k<0}$ ${\displaystyle \alpha ,\beta ,\gamma ,\alpha ^{\prime },\beta ^{\prime },\gamma ^{\prime }}$

参照

• スターリング数
• 第二種スターリング数
• スターリング多項式
• ランダム順列統計

参考文献

1. Wilf, Herbert S. (1990). Generatingfunctionology . San Diego, CA, USA: Academic Press. p. 73. ISBN 978-148324857-8。
2. Knuth, Donald E. (1992). 「表記法に関する2つの注意点」. American Mathematical Monthly . 99 (5): 403– 422. doi :10.2307/2325085. JSTOR  2325085.
3. アルフレッド・レンイ (1962). 「観察の機会を与える船員たち」。クレルモン大学科学誌。数学。第 8 巻 (2): 7-13。
4. 『具体的数学』のセクション6.2と6.5を参照してください。
5. Richard P. Stanley , Enumerative Combinatorics, 第1巻（第2版）。オンライン版の34ページ。
6. Adamchik, Victor (1997). 「スターリング数とオイラー和について」.計算・応用数学ジャーナル. 79 (1): 119– 130. doi : 10.1016/S0377-0427(96)00167-7 . MR  1437973.
7. Flajolet and Sedgewick (1995). 「メリン変換と漸近解析：有限差分とライス積分」（PDF） .理論計算機科学. 144 ( 1–2 ): 101–124 . doi :10.1016/0304-3975(94)00281-m.
8. k次調和数に関連するゼータ級数生成関数変換」. arXiv : 1610.09666 [math.CO].
9. Schmidt, MD (2016年11月3日). 「ゼータ級数生成関数変換と一般化スターリング数およびフルヴィッツゼータ関数の部分和」. arXiv : 1611.00957 [math.CO].
10. 2階オイラー数の表とその性質の概要は、『具体的数学』のセクション6.2にあります。例えば、 となります。これらの数には、次のような組み合わせ論的解釈もあります。の2つの出現の間のすべての数が に対してより大きいという性質を持つ多重集合のすべての順列を形成すると、 はそのような順列のうち上昇するものの数です。${\displaystyle \sum _{k}\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle =(2n-1)(2n-3)\cdots 1=(2n-1)!!}$ ${\displaystyle \{1,1,2,2,\ldots ,n,n\}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 1\leq k\leq n}$ ${\displaystyle \left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle }$ ${\displaystyle k}$
11. Schmidt, MD (2016). 「多項式列認識のためのコンピュータ代数パッケージ」. arXiv : 1609.07301 [math.CO].
12. ハーバート・ウィルフ、「生成機能学」、セクション4.6。
13. Schmidt, MD (2017). 「一般化階乗関数の通常生成関数に対するヤコビ型連分数」. J. Integer Seq . 20 (3). arXiv : 1610.09691 .
14. π ⁻¹に関連する特定の引数に対する有理係数のみを含むガンマ関数の対数に対する2つの級数展開」. Journal of Mathematical Analysis and Applications . 442 (2): 404– 434. arXiv : 1408.3902 . doi :10.1016/j.jmaa.2016.04.032. S2CID  119661147.arXiv
15. Blagouchine, Iaroslav V. (2018). 「ゼータ関数に対するSerとHasseの表現に関する3つの注釈」. INTEGERS: The Electronic Journal of Combinatorial Number Theory . 18A : 1– 45. arXiv : 1606.02044 . Bibcode :2016arXiv160602044B. doi :10.5281/zenodo.10581385.
16. Connon の論文で言及されている、より興味深い級数表現と展開も参照してください：Connon, DF (2007). 「リーマンゼータ関数、二項係数、調和数を含むいくつかの級数と積分（第1巻）」. arXiv : 0710.4022 [math.HO].。
17. これらの推定値は、 NIST 数学関数ハンドブックのセクション 26.8 に記載されています。
18. マレンファント、ジェローム (2011). 「分配関数とオイラー数、ベルヌーイ数、スターリング数の有限閉形式表現」arXiv : 1103.1585 [math.NT].
19. 小松隆夫; ピタ・ルイス・クラウディオ (2018). 「ベル数のいくつかの公式」.フィロマット. 32 (11): 3881– 3889. doi : 10.2298/FIL1811881K . ISSN  0354-5180.
20. π ⁻²の多項式級数と有理係数のみを持つ形式包絡級数への展開」. Journal of Number Theory . 158 (2): 365– 396. arXiv : 1501.00740 . doi :10.1016/j.jnt.2015.06.012.arXiv
21. 階乗関数と-調和数を展開する一般化スターリング数の組合せ恒等式」arXiv : 1611.04708 [math.CO].${\displaystyle f}$ ${\displaystyle f}$
22. Schmidt, Maxie D. (2010). 「一般化j階乗関数、多項式、およびその応用」J. Integer Seq 13 .

• コンピュータプログラミングの芸術
• 具体的な数学
• M. アブラモウィッツ、I. ステグン編 (1972). 「§24.1.3. 第一種スターリング数」.数式、グラフ、表付き数学関数ハンドブック（第9版）. ニューヨーク：ドーバー. p. 824.
• 第一種スターリング数 s(n,k) はPlanetMathで調べられます。
• Sloane, N. J. A. (編). 「数列A008275（第一種スターリング数の行で読む三角形）」.オンライン整数数列百科事典. OEIS財団.