組合せ論における重要なシーケンス
数学
において 、 スターリング数は 様々な 解析的 問題や 組合せ的 問題で登場する。スターリング数は、 ジェームズ・スターリング が著書 『微分法』 （1730年）で純粋に代数的な設定でスターリング数を導入したことにちなんで名付けられた。 スターリング数は1782年に坂正信によって再発見され、組合せ的意味が与えられた。
この名前を持つ数は、第 1 種のスターリング数 と 第 2 種のスターリング数 という2 つの異なる数のセットです 。さらに、 Lah 数は 第 3 種のスターリング数と呼ばれることもあります。それぞれの種類についてはそれぞれの記事で詳しく説明されており、この記事ではそれらの関係について説明します。
これら 3 種類の共通点は、組み合わせ論で頻繁に出現する 3 つの異なる多項式列に関連する係数を記述することです。さらに、これら 3 種類はすべて、 n個の要素を k 個の空でない部分集合に分割する回数として定義できます 。各部分集合には、特定の種類の順序 (無順序、循環的、または線形) が与えられます。
表記 スターリング数にはいくつかの異なる表記法が使用されています。 第一種の通常の（符号付き）スターリング数は、 一般的に次のように表記されます。
s （ ん 、 け ） 。
{\displaystyle s(n,k)\,.}
第一種符号なしスターリング数は、 n 個の要素と k 個 の 互いに素な 閉路の 順列 の数を数え 、次のように表される。
[
ん け
]
= c （ ん 、 け ） =
|
s （ ん 、 け ）
|
= （ − 1
）
ん − け
s （ ん 、 け ）
{\displaystyle {\biggl [}{n \atop k}{\biggr ]}=c(n,k)=|s(n,k)|=(-1)^{nk}s(n,k)\,}
第二種スターリング数、これは n 個の要素の集合を k個 の空でない部分集合に分割する方法の数を数えるものである : [3]
{
ん
け
}
= S （ ん 、 け ） =
S
ん
（ け ）
{\displaystyle {\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}=S(n,k)=S_{n}^{(k)}\,}
アブラモウィッツとステグンは、 スターリング数の第1種と第2種にそれぞれ 大文字 と 黒文字を使用しています。括弧と波括弧の表記は、 二項係数に類似しており、1935年に ジョヴァン・カラマタ によって導入され 、後に ドナルド・クヌースによって推進されましたが、括弧表記は ガウス 係数の一般的な表記と矛盾しています 。 [4]このタイプの表記の数学的動機、およびその他のスターリング数の公式については、 スターリング数と指数生成関数 のページをご覧ください 。
S
{\displaystyle S}
S
{\displaystyle {\mathfrak {S}}}
他にあまり使われない表記法は および です 。
s
1
(
n
,
k
)
{\displaystyle s_{1}(n,k)}
s
2
(
n
,
k
)
{\displaystyle s_{2}(n,k)}
下降階乗と上昇階乗の展開 スターリング数は、下降階乗と上昇階乗 の展開における係数 (ポッホハマー記号とも呼ばれる) を多項式として表現します。
つまり、 下降階乗は 、次のように定義される、 n 次の x の多項式であり 、その展開は
(
x
)
n
=
x
(
x
−
1
)
⋯
(
x
−
n
+
1
)
,
{\displaystyle \ (x)_{n}=x(x-1)\ \cdots (x-n+1)\ ,}
(
x
)
n
=
∑
k
=
0
n
s
(
n
,
k
)
x
k
{\displaystyle (x)_{n}\ =\ \sum _{k=0}^{n}\ s(n,k)\ x^{k}\ }
第一種（符号付き）スターリング数を係数とする。
慣例により、これは 空の積 であるため、 となることに注意してください。 下降階乗と 上昇階乗の 表記もよく使用されます。 [5] （紛らわしいことに、 下降 階乗によく使用されるポッホハマー記号は、 上昇 階乗の 特殊関数 で使用されます 。）
(
x
)
0
≡
1
,
{\displaystyle \ (x)_{0}\equiv 1\ ,}
x
n
_
{\displaystyle \ x^{\underline {n}}\ }
x
n
¯
{\displaystyle \ x^{\overline {n}}\ }
同様に、 と定義される 上昇階乗は、展開すると次のようになる、 n 次の x の多項式である 。
x
(
n
)
=
x
(
x
+
1
)
⋯
(
x
+
n
−
1
)
,
{\displaystyle \ x^{(n)}\ =\ x(x+1)\ \cdots (x+n-1)\ ,}
x
(
n
)
=
∑
k
=
0
n
[
n
k
]
x
k
=
∑
k
=
0
n
(
−
1
)
n
−
k
s
(
n
,
k
)
x
k
,
{\displaystyle x^{(n)}\ =\ \sum _{k=0}^{n}\ {\biggl [}{n \atop k}{\biggr ]}\ x^{k}\ =\ \sum _{k=0}^{n}\ (-1)^{n-k}\ s(n,k)\ x^{k}\ ,}
第一種符号なしスターリング数を係数とする。これらの展開の1つは、次の式からもう1つを導くことができる。
x
(
n
)
=
(
−
1
)
n
(
−
x
)
n
.
{\displaystyle \ x^{(n)}=(-1)^{n}(-x)_{n}~.}
第二種スターリング数は逆の関係を表します。
x
n
=
∑
k
=
0
n
S
(
n
,
k
)
(
x
)
k
{\displaystyle \ x^{n}\ =\ \sum _{k=0}^{n}\ S(n,k)\ (x)_{k}\ }
そして
x
n
=
∑
k
=
0
n
(
−
1
)
n
−
k
S
(
n
,
k
)
x
(
k
)
.
{\displaystyle \ x^{n}\ =\ \sum _{k=0}^{n}\ (-1)^{n-k}\ S(n,k)\ x^{(k)}~.}
基礎係数の変化として （不定）変数 xの 多項式 の集合を ベクトル空間として考えると、3つのシーケンスのそれぞれは
x
0
,
x
1
,
x
2
,
x
3
,
…
(
x
)
0
,
(
x
)
1
,
(
x
)
2
,
…
x
(
0
)
,
x
(
1
)
,
x
(
2
)
,
…
{\displaystyle x^{0},x^{1},x^{2},x^{3},\dots \quad (x)_{0},(x)_{1},(x)_{2},\dots \quad x^{(0)},x^{(1)},x^{(2)},\dots }
は基底 です 。つまり、 x のすべての多項式は、いくつかの一意の係数 の和として表すことができます(他の 2 つの基底についても同様)。上記の関係は、次の 可換図 にまとめられているように、それらの間の 基底の変化を 表します 。
a
0
x
(
0
)
+
a
1
x
(
1
)
+
⋯
+
a
n
x
(
n
)
{\displaystyle a_{0}x^{(0)}+a_{1}x^{(1)}+\dots +a_{n}x^{(n)}}
a
i
{\displaystyle a_{i}}
異なるスターリング数が多項式の基底を別の基底に変更する際の係数をどのように与えるかを示す図 2 つの底部変化の係数は、以下の Lah 数で表されます。任意の基底の係数は一意であるため、スターリング数を、ある基底の多項式を別の基底で表す係数、つまり上記のように 下降階乗と上昇階乗に関連する一意の数として定義できます。
x
n
{\displaystyle x^{n}}
階乗降は、スケーリングを除けば、二項係数 と同じ多項式を定義します : 。したがって、標準基底 と基底の間の変化は 、同様の式で記述されます:
(
x
k
)
=
(
x
)
k
/
k
!
{\textstyle {\binom {x}{k}}=(x)_{k}/k!}
x
0
,
x
1
,
x
2
,
…
{\displaystyle \textstyle x^{0},x^{1},x^{2},\dots }
(
x
0
)
,
(
x
1
)
,
(
x
2
)
,
…
{\textstyle {\binom {x}{0}},{\binom {x}{1}},{\binom {x}{2}},\dots }
x
n
=
∑
k
=
0
n
{
n
k
}
k
!
(
x
k
)
and
(
x
n
)
=
∑
k
=
0
n
s
(
n
,
k
)
n
!
x
k
{\displaystyle x^{n}=\sum _{k=0}^{n}{\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}k!{\binom {x}{k}}\quad {\text{and}}\quad {\binom {x}{n}}=\sum _{k=0}^{n}{\frac {s(n,k)}{n!}}x^{k}}
。
例 多項式を階乗の基底で表現することは、連続する整数で評価された多項式の和を計算するのに便利です。実際、固定 k での階乗の和は、別の階乗の基底で表現できます（ の場合 ）
k
≠
−
1
{\displaystyle k\neq -1}
∑
0
≤
i
<
n
(
i
)
k
=
(
n
)
k
+
1
k
+
1
{\displaystyle \sum _{0\leq i<n}(i)_{k}={\frac {(n)_{k+1}}{k+1}}}
これは帰納法 によって証明できます 。
たとえば、 n までの整数の 4 乗の合計 (今回は n を含む) は次のようになります。
∑
i
=
0
n
i
4
=
∑
i
=
0
n
∑
k
=
0
4
{
4
k
}
(
i
)
k
=
∑
k
=
0
4
{
4
k
}
∑
i
=
0
n
(
i
)
k
=
∑
k
=
0
4
{
4
k
}
(
n
+
1
)
k
+
1
k
+
1
=
{
4
1
}
(
n
+
1
)
2
2
+
{
4
2
}
(
n
+
1
)
3
3
+
{
4
3
}
(
n
+
1
)
4
4
+
{
4
4
}
(
n
+
1
)
5
5
=
1
2
(
n
+
1
)
2
+
7
3
(
n
+
1
)
3
+
6
4
(
n
+
1
)
4
+
1
5
(
n
+
1
)
5
.
{\displaystyle {\begin{aligned}\sum _{i=0}^{n}i^{4}&=\sum _{i=0}^{n}\sum _{k=0}^{4}{\biggl \{}{\!4\! \atop \!k\!}{\biggr \}}(i)_{k}=\sum _{k=0}^{4}{\biggl \{}{\!4\! \atop \!k\!}{\biggr \}}\sum _{i=0}^{n}(i)_{k}=\sum _{k=0}^{4}{\biggl \{}{\!4\! \atop \!k\!}{\biggr \}}{\frac {(n{+}1)_{k+1}}{k{+}1}}\\[10mu]&={\biggl \{}{\!4\! \atop \!1\!}{\biggr \}}{\frac {(n{+}1)_{2}}{2}}+{\biggl \{}{\!4\! \atop \!2\!}{\biggr \}}{\frac {(n{+}1)_{3}}{3}}+{\biggl \{}{\!4\! \atop \!3\!}{\biggr \}}{\frac {(n{+}1)_{4}}{4}}+{\biggl \{}{\!4\! \atop \!4\!}{\biggr \}}{\frac {(n{+}1)_{5}}{5}}\\[8mu]&={\frac {1}{2}}(n{+}1)_{2}+{\frac {7}{3}}(n{+}1)_{3}+{\frac {6}{4}}(n{+}1)_{4}+{\frac {1}{5}}(n{+}1)_{5}\,.\end{aligned}}}
ここで、スターリング数は、4 つの要素をk 個の空でないラベルなしサブセット
に分割する数としての定義から計算できます。
対照的に、標準基底における 和は ファウルハーバーの公式 によって与えられ、これは一般にはより複雑です。
∑
i
=
0
n
i
k
{\textstyle \sum _{i=0}^{n}i^{k}}
逆行列として 第 1 種と第 2 種のスターリング数は、互いに逆数であると考えることができます。
∑
j
=
k
n
s
(
n
,
j
)
S
(
j
,
k
)
=
∑
j
=
k
n
(
−
1
)
n
−
j
[
n
j
]
{
j
k
}
=
δ
n
,
k
{\displaystyle \sum _{j=k}^{n}s(n,j)S(j,k)=\sum _{j=k}^{n}(-1)^{n-j}{\biggl [}{n \atop j}{\biggr ]}{\biggl \{}{\!j\! \atop \!k\!}{\biggr \}}=\delta _{n,k}}
そして
∑
j
=
k
n
S
(
n
,
j
)
s
(
j
,
k
)
=
∑
j
=
k
n
(
−
1
)
j
−
k
{
n
j
}
[
j
k
]
=
δ
n
,
k
,
{\displaystyle \sum _{j=k}^{n}S(n,j)s(j,k)=\sum _{j=k}^{n}(-1)^{j-k}{\biggl \{}{\!n\! \atop \!j\!}{\biggr \}}{\biggl [}{j \atop k}{\biggr ]}=\delta _{n,k},}
ここで、は クロネッカーのデルタ です 。これら2つの関係は、行列の逆関係として理解できます。つまり、 を 第一種スターリング数の
下三角行列 とし、その行列要素は この行列の 逆行列
は S で、 第二種スターリング数の 下三角行列 であり、その要素は です 。記号的に、これは次のように書きます。
δ
n
k
{\displaystyle \delta _{nk}}
s
n
k
=
s
(
n
,
k
)
.
{\displaystyle s_{nk}=s(n,k).\,}
S
n
k
=
S
(
n
,
k
)
.
{\displaystyle S_{nk}=S(n,k).}
s
−
1
=
S
{\displaystyle s^{-1}=S\,}
s と S は無限大なので 、積の項の計算には無限和が含まれますが、これらの行列は下三角なので行列の乗算は機能し、和の項のうちゼロ以外の項は有限個だけです。
数字 ラー数は 第三種スターリング数と呼ばれることもある。 [6]
慣例により、 または の 場合 。
L
(
n
,
k
)
=
(
n
−
1
k
−
1
)
n
!
k
!
{\displaystyle L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}}
L
(
0
,
0
)
=
1
{\displaystyle L(0,0)=1}
L
(
n
,
k
)
=
0
{\displaystyle L(n,k)=0}
n
<
k
{\displaystyle n<k}
k
=
0
<
n
{\displaystyle k=0<n}
これらの数値は、上昇する階乗で下降する階乗を表す係数であり、その逆も同様です。
x
(
n
)
=
∑
k
=
0
n
L
(
n
,
k
)
(
x
)
k
{\displaystyle x^{(n)}=\sum _{k=0}^{n}L(n,k)(x)_{k}\quad }
そして
(
x
)
n
=
∑
k
=
0
n
(
−
1
)
n
−
k
L
(
n
,
k
)
x
(
k
)
.
{\displaystyle \quad (x)_{n}=\sum _{k=0}^{n}(-1)^{n-k}L(n,k)x^{(k)}.}
上で述べたように、これは基底 との間の基底の変化を表し 、図が完成することを意味します。特に、一方の式は他方の式の逆であるため、次のようになります。
(
x
)
0
,
(
x
)
1
,
(
x
)
2
,
⋯
{\displaystyle (x)_{0},(x)_{1},(x)_{2},\cdots }
x
(
0
)
,
x
(
1
)
,
x
(
2
)
,
⋯
{\displaystyle x^{(0)},x^{(1)},x^{(2)},\cdots }
∑
j
=
k
n
(
−
1
)
j
−
k
L
(
n
,
j
)
L
(
j
,
k
)
=
δ
n
,
k
.
{\displaystyle \sum _{j=k}^{n}(-1)^{j-k}L(n,j)L(j,k)=\delta _{n,k}.}
同様に、 からへ の基底の変化と から への基底の変化を組み合わせると、 から へ の 基底の変化が直接得られます 。
x
(
n
)
{\displaystyle x^{(n)}}
x
n
{\displaystyle x^{n}}
x
n
{\displaystyle x^{n}}
(
x
)
n
{\displaystyle (x)_{n}}
x
(
n
)
{\displaystyle x^{(n)}}
(
x
)
n
{\displaystyle (x)_{n}}
L
(
n
,
k
)
=
∑
j
=
k
n
[
n
j
]
{
j
k
}
,
{\displaystyle L(n,k)=\sum _{j=k}^{n}{\biggl [}{n \atop j}{\biggr ]}{\biggl \{}{\!j\! \atop \!k\!}{\biggr \}},}
他の合成についても同様です。行列に関しては、 が要素を持つ行列を表し 、 が要素を持つ行列を表す 場合 、一方が他方の逆になります。 第一種符号なしスターリング数の行列を第二種スターリング数の行列と合成すると、Lah 数が得られます 。
L
{\displaystyle L}
L
n
k
=
L
(
n
,
k
)
{\displaystyle L_{nk}=L(n,k)}
L
−
{\displaystyle L^{-}}
L
n
k
−
=
(
−
1
)
n
−
k
L
(
n
,
k
)
{\displaystyle L_{nk}^{-}=(-1)^{n-k}L(n,k)}
L
−
=
L
−
1
{\displaystyle L^{-}=L^{-1}}
L
=
|
s
|
⋅
S
{\displaystyle L=|s|\cdot S}
列挙的 に、は、 n 個の要素を k 個の空でないラベルなし部分集合に 分割する回数として定義できます。ここで、各部分集合には、それぞれ順序なし、 巡回順序 、または線形順序が与えられます。特に、これは不等式を意味します。
{
n
k
}
,
[
n
k
]
,
L
(
n
,
k
)
{\textstyle \left\{{\!n\! \atop \!k\!}\right\},\left[{n \atop k}\right],L(n,k)}
{
n
k
}
≤
[
n
k
]
≤
L
(
n
,
k
)
.
{\displaystyle {\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}\leq {\biggl [}{n \atop k}{\biggr ]}\leq L(n,k).}
任意の数列のペア、 およびに対して 、有限和で関係付けられるスターリング数公式は、
{
f
n
}
{\displaystyle \{f_{n}\}}
{
g
n
}
{\displaystyle \{g_{n}\}}
g
n
=
∑
k
=
0
n
{
n
k
}
f
k
,
{\displaystyle g_{n}=\sum _{k=0}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}f_{k},}
すべての整数 に対して 、 の対応する 逆関数の公式 は次のよう
に与えられる。
n
≥
0
{\displaystyle n\geq 0}
f
n
{\displaystyle f_{n}}
f
n
=
∑
k
=
0
n
[
n
k
]
(
−
1
)
n
−
k
g
k
.
{\displaystyle f_{n}=\sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right](-1)^{n-k}g_{k}.}
下位のインデックスは ～ の間の任意の整数になり ます 。
0
{\textstyle 0}
n
{\textstyle n}
2つのシーケンス間の反転関係は、 スターリング（生成関数） 変換によって与えられるシーケンス 指数生成関数 間の関数方程式に変換されます。
G
^
(
z
)
=
F
^
(
e
z
−
1
)
{\displaystyle {\widehat {G}}(z)={\widehat {F}}\left(e^{z}-1\right)}
そして
F
^
(
z
)
=
G
^
(
log
(
1
+
z
)
)
.
{\displaystyle {\widehat {F}}(z)={\widehat {G}}\left(\log(1+z)\right).}
に対して 、 微分演算子 とは 次の式ですべての整数に対して関連付けられる ： [7]
D
=
d
/
d
x
{\displaystyle D=d/dx}
x
n
D
n
{\displaystyle x^{n}D^{n}}
(
x
D
)
n
{\displaystyle (xD)^{n}}
n
≥
0
{\displaystyle n\geq 0}
(
x
D
)
n
=
∑
k
=
0
n
S
(
n
,
k
)
x
k
D
k
x
n
D
n
=
∑
k
=
0
n
s
(
n
,
k
)
(
x
D
)
k
=
(
x
D
)
n
=
x
D
(
x
D
−
1
)
…
(
x
D
−
n
+
1
)
{\displaystyle {\begin{aligned}(xD)^{n}&=\sum _{k=0}^{n}S(n,k)x^{k}D^{k}\\x^{n}D^{n}&=\sum _{k=0}^{n}s(n,k)(xD)^{k}=(xD)_{n}=xD(xD-1)\ldots (xD-n+1)\end{aligned}}}
スターリング数を 含むもう1組の「 反転 」関係は、 関数の 前進差分 と通常の 導関数 を関係づけるものであり、これはすべての関数に対して解析的であり、次の 式によって 表される [8]。
n
t
h
{\displaystyle n^{th}}
f
(
x
)
{\displaystyle f(x)}
x
{\displaystyle x}
1
k
!
d
k
d
x
k
f
(
x
)
=
∑
n
=
k
∞
s
(
n
,
k
)
n
!
Δ
n
f
(
x
)
{\displaystyle {\frac {1}{k!}}{\frac {d^{k}}{dx^{k}}}f(x)=\sum _{n=k}^{\infty }{\frac {s(n,k)}{n!}}\Delta ^{n}f(x)}
1
k
!
Δ
k
f
(
x
)
=
∑
n
=
k
∞
S
(
n
,
k
)
n
!
d
n
d
x
n
f
(
x
)
.
{\displaystyle {\frac {1}{k!}}\Delta ^{k}f(x)=\sum _{n=k}^{\infty }{\frac {S(n,k)}{n!}}{\frac {d^{n}}{dx^{n}}}f(x).}
類似物件 詳細については、それぞれの記事を参照してください。
アブラモウィッツとステグンは、第一種スターリング数と第二種スターリング数を関連付ける次の対称式を与えている。 [9]
[
n
k
]
=
∑
j
=
n
2
n
−
k
(
−
1
)
j
−
k
(
j
−
1
k
−
1
)
(
2
n
−
k
j
)
{
j
−
k
j
−
n
}
{\displaystyle \left[{n \atop k}\right]=\sum _{j=n}^{2n-k}(-1)^{j-k}{\binom {j-1}{k-1}}{\binom {2n-k}{j}}\left\{{j-k \atop j-n}\right\}}
そして
{
n
k
}
=
∑
j
=
n
2
n
−
k
(
−
1
)
j
−
k
(
j
−
1
k
−
1
)
(
2
n
−
k
j
)
[
j
−
k
j
−
n
]
{\displaystyle \left\{{n \atop k}\right\}=\sum _{j=n}^{2n-k}(-1)^{j-k}{\binom {j-1}{k-1}}{\binom {2n-k}{j}}\left[{j-k \atop j-n}\right]}
負の積分値を持つスターリング数 スターリング数は負の整数値に拡張できるが、すべての著者が同じ方法で拡張しているわけではない。 [10] [11] [12] どのようなアプローチをとったとしても、第一種と第二種のスターリング数は次の関係で結びついていることは注目に値する。
[
n
k
]
=
{
−
k
−
n
}
and
{
n
k
}
=
[
−
k
−
n
]
{\displaystyle {\biggl [}{n \atop k}{\biggr ]}={\biggl \{}{\!-k\! \atop \!-n\!}{\biggr \}}\quad {\text{and}}\quad {\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}={\biggl [}{-k \atop -n}{\biggr ]}}
n と k が非負の整数の場合 、 は次の表のようになります 。
[
−
n
−
k
]
{\displaystyle \left[{-n \atop -k}\right]}
ドナルド・クヌース [12] は、 すべての整数に 再帰関係を 拡張することで、より一般的なスターリング数を定義しました。このアプローチでは、 n が負で k が非負の場合、およびは0になります。または、 n が非負で k が負の場合、およびは0になります。したがって、 任意の 整数 n と k に対して 、
[
n
k
]
{\textstyle \left[{n \atop k}\right]}
{
n
k
}
{\textstyle \left\{{\!n\! \atop \!k\!}\right\}}
[
n
k
]
=
{
−
k
−
n
}
and
{
n
k
}
=
[
−
k
−
n
]
.
{\displaystyle {\biggl [}{n \atop k}{\biggr ]}={\biggl \{}{\!-k\! \atop \!-n\!}{\biggr \}}\quad {\text{and}}\quad {\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}={\biggl [}{-k \atop -n}{\biggr ]}.}
一方、正の整数 n と k に対して、David Branson [11]は 、および を定義しました （またはは定義していません ） 。このアプローチでは、 第一種スターリング数の
再帰関係 が次のように拡張されます。
[
−
n
−
k
]
,
{\textstyle \left[{-n \atop -k}\right]\!,}
{
−
n
−
k
}
,
{\textstyle \left\{{\!-n\! \atop \!-k\!}\right\}\!,}
[
−
n
k
]
,
{\textstyle \left[{-n \atop k}\right]\!,}
{
−
n
k
}
{\textstyle \left\{{\!-n\! \atop \!k\!}\right\}}
[
n
−
k
]
{\textstyle \left[{n \atop -k}\right]}
{
n
−
k
}
{\textstyle \left\{{\!n\! \atop \!-k\!}\right\}}
[
−
n
k
]
=
(
−
1
)
n
+
1
n
!
∑
i
=
1
n
(
−
1
)
i
+
1
i
k
(
n
i
)
{\displaystyle {\biggl [}{-n \atop k}{\biggr ]}={\frac {(-1)^{n+1}}{n!}}\sum _{i=1}^{n}{\frac {(-1)^{i+1}}{i^{k}}}{\binom {n}{i}}}
、 たとえば、 負の整数 n に対する の値の次の表が得られます 。
[
−
5
k
]
=
1
120
(
5
−
10
2
k
+
10
3
k
−
5
4
k
+
1
5
k
)
.
{\textstyle \left[{-5 \atop k}\right]={\frac {1}{120}}{\Bigl (}5-{\frac {10}{2^{k}}}+{\frac {10}{3^{k}}}-{\frac {5}{4^{k}}}+{\frac {1}{5^{k}}}{\Bigr )}.}
[
n
k
]
{\textstyle \left[{n \atop k}\right]}
この場合、 は ベル数 なので 、負のベル数を で定義できます 。
∑
n
=
1
∞
[
−
n
−
k
]
=
B
k
{\textstyle \sum _{n=1}^{\infty }\left[{-n \atop -k}\right]=B_{k}}
B
k
{\displaystyle B_{k}}
∑
n
=
1
∞
[
−
n
k
]
=:
B
−
k
{\textstyle \sum _{n=1}^{\infty }\left[{-n \atop k}\right]=:B_{-k}}
たとえば、これは 一般にを生成します 。
∑
n
=
1
∞
[
−
n
1
]
=
B
−
1
=
1
e
∑
j
=
1
∞
1
j
⋅
j
!
=
1
e
∫
0
1
e
t
−
1
t
d
t
=
0.4848291
…
{\textstyle \sum _{n=1}^{\infty }\left[{-n \atop 1}\right]=B_{-1}={\frac {1}{e}}\sum _{j=1}^{\infty }{\frac {1}{j\cdot j!}}={\frac {1}{e}}\int _{0}^{1}{\frac {e^{t}-1}{t}}dt=0.4848291\dots }
B
−
k
=
1
e
∑
j
=
1
∞
1
j
k
j
!
{\textstyle B_{-k}={\frac {1}{e}}\sum _{j=1}^{\infty }{\frac {1}{j^{k}j!}}}
参照
引用
^ Ronald L. Graham、Donald E. Knuth、Oren Patashnik (1988) 具体的な数学 、Addison-Wesley、Reading MA. ISBN 0-201-14236-8 、p. 244. ^ Knuth, Donald E. (1992). 「表記法に関する2つの注意」. American Mathematical Monthly . 99 (5): 403–422. doi :10.2307/2325085. JSTOR 2325085 – JSTOR経由. ^ Aigner, Martin (2007). 「セクション 1.2 - サブセットと二項係数」. 列挙のコース . Springer. pp. 561. ISBN 978-3-540-39032-9 。 ^ サンダー、ジョゼフ;クリスティチ、ボリスラフ (2004)。整数論ハンドブック II。 Kluwer Academic Publishers 。 p. 464.ISBN 9781402025464 。 ^ 具体的な数学の第 6 章の演習 13。この式は、 生成関数変換 に関するメイン記事で示されている最初の正の次数スターリング数変換を直ちに意味することに注意してください 。 ^ Olver, Frank; Lozier, Daniel; Boisvert, Ronald; Clark, Charles (2010). 「NIST 数学関数ハンドブック」。NIST 数学関数ハンドブック 。 （第26.8条） ^ Goldberg, K.; Newman, M; Haynsworth, E. (1972)、「第一種スターリング数、第二種スターリング数」、Abramowitz, Milton、Stegun, Irene A. (編)、『 数式、グラフ、および数学表付き数学関数ハンドブック』、第 10 刷 、ニューヨーク: Dover、pp. 824–825 ^ Loeb, Daniel E. (1992) [1989年11月3日受理]. 「スターリング数の一般化」. 離散数学 . 103 (3): 259–269. doi : 10.1016/0012-365X(92)90318-A . ^ ab Branson, David (1994年8月). 「スターリング数の拡張」 (PDF) . The Fibonacci Quarterly . 2011年8月27日時点のオリジナルより アーカイブ (PDF) . 2017年 12月6日 閲覧 。 ^ DE Knuth、1992年 より。
参考文献
ローゼン、ケネス H. 編 (2018)、 離散数学と組合せ数学ハンドブック 、CRC プレス、 ISBN 978-1-5848-8780-5 マンスール、トゥフィック、ショルク、マティアス（2015）、 交換関係、正規順序、およびスターリング数 、CRCプレス、 ISBN 978-1-4665-7989-7
さらに読む Adamchik, Victor (1997). 「スターリング数とオイラー和について」 (PDF) . Journal of Computational and Applied Mathematics . 79 : 119–130. doi : 10.1016/s0377-0427(96)00167-7 . 2004-12-14 にオリジナルからアーカイブ (PDF)されました。 Benjamin, Arthur T.; Preston, Gregory O.; Quinn, Jennifer J. (2002). 「A Stirling Encounter with Harmonic Numbers」 （PDF） . Mathematics Magazine . 75 （2）：95–103. CiteSeerX 10.1.1.383.722 . doi :10.2307/3219141. JSTOR 3219141. 2020-09-10にオリジナルからアーカイブ （PDF）されました。 Boyadzhiev, Khristo N. (2012). 「第 2 種のスターリング数との接近遭遇」 (PDF) . Mathematics Magazine . 85 (4): 252–266. arXiv : 1806.09468 . doi :10.4169/math.mag.85.4.252. S2CID 115176876. 2015 年 9 月 5 日にオリジナルからアーカイブ (PDF)されました。 コンテット、ルイ (1970)。 「ヴァルール ド s(n, k)」 。 『分析コンビナトワール』第 2 冊 （フランス語）: 51。 コムテット、ルイ (1974)。『Advanced Combinatorics: The Art of Finite and Infinite Expansions 』 。ドルドレヒト-オランダ/ボストン-USA: Reidel Publishing Company。ISBN 9789027703804 。 Hsien-Kuei Hwang (1995). 「第一種スターリング数の漸近展開」. 組合せ理論ジャーナル、シリーズA. 71 ( 2): 343–351. doi : 10.1016/0097-3165(95)90010-1 . Knuth, DE (1992)、「表記法に関する2つの注意」、 Amer. Math. Monthly 、 99 (5): 403–422、 arXiv : math/9205211 、 doi :10.2307/2325085、 JSTOR 2325085、 S2CID 119584305 ミクサ、フランシス L. (1956 年 1 月)。「第一種スターリング数: UMT ファイルに保管されているタイプライターで作成された原稿から 27 枚の葉を複製」。 数学 表とその他の計算補助: 表と書籍のレビューと説明 。10 (53): 37–38。JSTOR 2002617 。 Miksa, Francis L. (1972) [1964]. 「組み合わせ解析、表 24.4、第 2 種のスターリング数」。Abramowitz, Milton、Stegun, Irene A. (編)。 数学関数ハンドブック (公式、グラフ、数学表付き) 。55。米国商務省、国立標準局、応用数学。835 ページ。 ミトリノヴィッチ、ドラゴスラフ S. (1959)。 「スターリングの特別な命名法とスターリングの多能性」 (PDF) 。 出版物 de la Faculté d'Electrotechnique de l'Université de Belgrade、Série Mathématiques et Physique (フランス語) (23): 1–20。 ISSN 0522-8441。 2009 年 6 月 17 日にオリジナルから アーカイブ (PDF)されました。 オコナー、ジョン J.、ロバートソン、エドマンド F. (1998 年 9 月)。「ジェームズ スターリング (1692–1770)」。 Sixdeniers, JM; Penson, KA; Solomon, AI (2001). 「超幾何指数法による拡張ベル数とスターリング数」 (PDF) . Journal of Integer Sequences . 4 : 01.1.4. arXiv : math/0106123 . Bibcode :2001JIntS...4...14S. Spivey, Michael Z. (2007). 「組み合わせ和と有限差分」. 離散数学 . 307 (24): 3130–3146. CiteSeerX 10.1.1.134.8665 . doi : 10.1016/j.disc.2007.03.052 . Sloane, N. J. A. (編)。「シーケンス A008275 (第一種スターリング数)」。 整数シーケンスのオンライン百科事典 。OEIS Foundation。 Sloane, N. J. A. (編)。「数列 A008277 (第 2 種のスターリング数)」。 整数数列のオンライン百科事典 。OEIS 財団。
![{\displaystyle {\biggl [}{n \atop k}{\biggr ]}=c(n,k)=|s(n,k)|=(-1)^{nk}s(n,k)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff56ff0a1f39d29c4fdb9e43faf74d13818fbd34)
![{\displaystyle x^{(n)}\ =\ \sum _{k=0}^{n}\ {\biggl [}{n \atop k}{\biggr ]}\ x^{k}\ = \ \sum _{k=0}^{n}\ (-1)^{nk}\ s(n,k)\ x^{k}\ ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee5872df65edaf1c6a66b8ae2796137048cfceba)
![{\displaystyle {\begin{aligned}\sum _{i=0}^{n}i^{4}&=\sum _{i=0}^{n}\sum _{k=0}^{4}{\biggl \{}{\!4\! \atop \!k\!}{\biggr \}}(i)_{k}=\sum _{k=0}^{4}{\biggl \{}{\!4\! \atop \!k\!}{\biggr \}}\sum _{i=0}^{n}(i)_{k}=\sum _{k=0}^{4}{\biggl \{}{\!4\! \atop \!k\!}{\biggr \}}{\frac {(n{+}1)_{k+1}}{k{+}1}}\\[10mu]&={\biggl \{}{\!4\! \atop \!1\!}{\biggr \}}{\frac {(n{+}1)_{2}}{2}}+{\biggl \{}{\!4\! \atop \!2\!}{\biggr \}}{\frac {(n{+}1)_{3}}{3}}+{\biggl \{}{\!4\! \atop \!3\!}{\biggr \}}{\frac {(n{+}1)_{4}}{4}}+{\biggl \{}{\!4\! \atop \!4\!}{\biggr \}}{\frac {(n{+}1)_{5}}{5}}\\[8mu]&={\frac {1}{2}}(n{+}1)_{2}+{\frac {7}{3}}(n{+}1)_{3}+{\frac {6}{4}}(n{+}1)_{4}+{\frac {1}{5}}(n{+}1)_{5}\,.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ae77860888a00722dde0d01f031c9d189ddae65)
![{\displaystyle \sum _{j=k}^{n}s(n,j)S(j,k)=\sum _{j=k}^{n}(-1)^{nj}{\biggl [}{n \atop j}{\biggr ]}{\biggl \{}{\!j\! \atop \!k\!}{\biggr \}}=\delta _{n,k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d866c838f784a76038bc6835d191d0a428fa703f)
![{\displaystyle \sum _{j=k}^{n}S(n,j)s(j,k)=\sum _{j=k}^{n}(-1)^{jk}{\biggl \{}{\!n\! \atop \!j\!}{\biggr \}}{\biggl [}{j \atop k}{\biggr ]}=\delta _{n,k},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00a0a9383d73081a147f80c791b4cbfbbad44eef)
![{\displaystyle L(n,k)=\sum _{j=k}^{n}{\biggl [}{n \atop j}{\biggr ]}{\biggl \{}{\!j\! \atop \!k\!}{\biggr \}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce67f09dcebbc9f778fde72e43f31696e49d2f40)
![{\textstyle \left\{{\!n\! \atop \!k\!}\right\},\left[{n \atop k}\right],L(n,k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc26eedaa94e5b7e121762310ad713db0b92b2e3)
![{\displaystyle {\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}\leq {\biggl [}{n \atop k}{\biggr ]}\leq L(n,k).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df78c5212ed960b65aed0ba87be0ca3eefdd293c)
^{nk} g_{k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf0de636ecc3989622d39a0e7eb8c91859991778)
![{\displaystyle \left[{n \atop k}\right]=\sum _{j=n}^{2n-k}(-1)^{jk}{\binom {j-1}{k-1 }}{\binom {2n-k}{j}}\left\{{jk \atop jn}\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55b396b7588b8b75ad99d03868f7aa1eadbb5c5b)
![{\displaystyle \left\{{n \atop k}\right\}=\sum _{j=n}^{2n-k}(-1)^{jk}{\binom {j-1}{k -1}}{\binom {2n-k}{j}}\left[{jk \atop jn}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b536640328c88e08cf7a068aeb47c3a77c7d5e8)
![{\displaystyle {\biggl [}{n \atop k}{\biggr ]}={\biggl \{}{\!-k\! \atop \!-n\!}{\biggr \}}\quad {\text{および}}\quad {\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}={\biggl [}{-k \atop -n}{\biggr ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9f12872029952e3a00f2a2e6cff8da907b5c372)
![{\displaystyle \left[{-n \atop -k}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4b082da53ea89c6b9e736335552cceb8ed6069e)
![{\textstyle \left[{n \atop k}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0eda457849a3bdae75a608661a9520cae5ce8a6c)
![{\displaystyle {\biggl [}{n \atop k}{\biggr ]}={\biggl \{}{\!-k\! \atop \!-n\!}{\biggr \}}\quad {\text{および}}\quad {\biggl \{}{\!n\! \atop \!k\!}{\biggr \}}={\biggl [}{-k \atop -n}{\biggr ]}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b03ad1a4792348c1acf9f5ef46b70b35687264f)
![{\textstyle \left[{-n \atop -k}\right]\!,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e5922f6d16f68a5c91afc67a34cece3be89fc24)
![{\textstyle \left[{-n \atop k}\right]\!,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e115fa99ba4cc0fff4c01ce6932201079e4dc3e)
![{\textstyle \left[{n \atop -k}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8da0d6e5d3f6db3106312f622e6d954b1f65070)
![{\displaystyle {\biggl [}{-n \atop k}{\biggr ]}={\frac {(-1)^{n+1}}{n!}}\sum _{i=1}^{n}{\frac {(-1)^{i+1}}{i^{k}}}{\binom {n}{i}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffdb9afe821b203f793c2c8ba04aab0b713a296b)
![{\textstyle \left[{-5 \atop k}\right]={\frac {1}{120}}{\Bigl (}5-{\frac {10}{2^{k}}}+{\frac {10}{3^{k}}}-{\frac {5}{4^{k}}}+{\frac {1}{5^{k}}}{\Bigr )}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a92356fcae50ab1ac548ebe38fa6b1764e322699)
![{\textstyle \sum _{n=1}^{\infty }\left[{-n \atop -k}\right]=B_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/900906e78c8883aa541b8798614bc2145bf4a72b)
![{\textstyle \sum _{n=1}^{\infty }\left[{-n \atop k}\right]=:B_{-k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81cddaa2425275840e603da66b2f8f76bdd23fea)
![{\textstyle \sum _{n=1}^{\infty }\left[{-n \atop 1}\right]=B_{-1}={\frac {1}{e}}\sum _{j=1}^{\infty }{\frac {1}{j\cdot j!}}={\frac {1}{e}}\int _{0}^{1}{\frac {e^{t}-1}{t}}dt=0.4848291\dots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a13a7742887bd6a1555435cc16dd9f2326d5592)
