集合を分割する方法をパラメータ化する数値
ハッセ図 に並べられた4要素集合の 15 の分割
1、2、3、4 セットを含む S (4,1)、...、 S (4, 4) = 1、7、6、1 個のパーティションがあります。 数学 、特に 組合せ論 において 、 第二種スターリング数 （ スターリング分割数）は、 n 個 のオブジェクト の 集合を k 個 の空でない部分集合に分割する 方法の数であり、 またはで表されます 。 [1]第二種スターリング数は、 組合せ論 と呼ばれる 数学 の分野 と 分割 の研究で使用されます。これらは ジェームズ・スターリング にちなんで名付けられました 。
S （ ん 、 け ）
{\displaystyle S(n,k)}
{
ん け
}
{\displaystyle \textstyle \left\{{n \atop k}\right\}}
第一 種および第二種のスターリング数は、 三角行列 として見ると、互いの逆数として理解できます。この記事では、第二種のスターリング数の詳細について説明します。2 種類のスターリング数を結び付ける恒等式については 、スターリング数 に関する記事で説明します 。
意味 または または他の表記で 書かれた第 2 種のスターリング数は、ラベル付きオブジェクト の 集合 を 空でないラベルなしのサブセット に 分割する 方法の数を数えます。同様に、要素集合で定義できる同値類 と 同値関係 の異なる数の数を数えます。実際、与えられた集合上の分割集合と同値関係集合の間には
一対一の関係 があります。明らかに、
S （ ん 、 け ）
{\displaystyle S(n,k)}
{
ん け
}
{\displaystyle \lbrace \textstyle {n \atop k}\rbrace }
ん
{\displaystyle n}
け
{\displaystyle k}
け
{\displaystyle k}
ん
{\displaystyle n}
{
ん ん
}
= 1
{\displaystyle \left\{{n \atop n}\right\}=1}
n ≥ 0の場合 、 n ≥ 1の 場合 、
{
ん 1
}
= 1
{\displaystyle \left\{{n \atop 1}\right\}=1}
n 要素の集合を n 個 の部分に分割する唯一の方法は 、集合の各要素をそれぞれの部分に置くことであり、空でない集合を 1 つの部分に分割する唯一の方法は、すべての要素を同じ部分に置くことである。 第一種スターリング数 とは異なり、これらは 1 和の公式を使用して計算できる: [2]
{
ん け
}
=
1
け ！
∑
私 = 0
け
（ − 1
）
け − 私
（
け 私
）
私
ん
=
∑
私 = 0
け
（ − 1
）
け − 私
私
ん
（ け − 私 ） ！ 私 ！
。
{\displaystyle \left\{{n \atop k}\right\}={\frac {1}{k!}}\sum _{i=0}^{k}(-1)^{ki}{\binom {k}{i}}i^{n}=\sum _{i=0}^{k}{\frac {(-1)^{ki}i^{n}}{(ki)!i!}}.}
第一種スターリング数は、不定数xの累乗を 階乗 で 表したときに生じる数として特徴付けられる [3]
（ x
）
ん
= x （ x − 1 ） （ x − 2 ） ⋯ （ x − ん + 1 ） 。
{\displaystyle (x)_{n}=x(x-1)(x-2)\cdots (x-n+1).}
（特に、（ x ） 0は 空積 なので1となる 。）
第二種スターリング数は次の関係を満たす。
∑
け = 0
ん
{
ん け
}
（ x
）
け
=
x
ん
。
{\displaystyle \sum _{k=0}^{n}\left\{{n \atop k}\right\}(x)_{k}=x^{n}.}
表記 第二種スターリング数には様々な表記法が使われてきました。 1962年にイマヌエル・マルクスとアントニオ・サルメリがこれらの数の変形に中括弧表記法を使用しました。 [4] [5] これを受けて クヌースは 、ここに示すように、 The Art of Computer Programming （1968年）の第1巻でこの表記法を使用しました。 [6] [7] The Art of Computer Programming の第3版によると、この表記法は 1935年に ジョヴァン・カラマタ によっても使用されていました。 [8] [9] 表記法 S ( n , k )は リチャード・スタンレー の著書 Enumerative Combinatorics で使用され 、さらにそれより以前には他の多くの著者によっても使用されていました。 [6]
{
ん け
}
{\textstyle \textstyle \lbrace {n \atop k}\rbrace }
このページで使用されているスターリング数の表記は普遍的なものではなく、他のソースの表記と矛盾する可能性があります。
ベル数との関係 スターリング数は n 要素の集合を k 個の部分に分割したものを数えるので 、
{
ん け
}
{\displaystyle \left\{{n \atop k}\right\}}
B
ん
=
∑
け = 0
ん
{
ん け
}
{\displaystyle B_{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}}
k のすべての値にわたって、 n 個の要素を持つ集合の分割の総数です 。この数は n 番目の ベル数 として知られています。
同様に、 順序付きベル数は 第二種スターリング数から次のように計算できる。
1つの
ん
=
∑
け = 0
ん
け ！
{
ん け
}
。
{\displaystyle a_{n}=\sum _{k=0}^{n}k!\left\{{n \atop k}\right\}.}
[10]
値の表 以下は、第 2 種のスターリング数 ( OEIS のシーケンス A008277 ) の値の 三角形配列 です 。
二項係数 と同様に、この表は k > n まで拡張できます が、エントリはすべて 0 になります。
プロパティ
再帰関係 第二種スターリング数は再帰関係に従う
{
ん + 1
け
}
= け
{
ん け
}
+
{
ん
け − 1
}
のために
0 < け < ん
{\displaystyle \left\{{n+1 \atop k}\right\}=k\left\{{n \atop k}\right\}+\left\{{n \atop k-1}\right\}\quad {\mbox{for}}\;0<k<n}
初期条件付き
{
ん ん
}
= 1
のために
ん ≥ 0
そして
{
ん 0
}
=
{
0 ん
}
= 0
のために
ん > 0
。
{\displaystyle \left\{{n \atop n}\right\}=1\quad {\mbox{ for}}\;n\geq 0\quad {\text{ かつ }}\quad \left\{{n \atop 0}\right\}=\left\{{0 \atop n}\right\}=0\quad {\text{ for }}n>0{\text{.}}}
たとえば、列k = 3、行 n = 5の数字 25 は 、25 = 7 + (3×6) で表されます。ここで、7 は 25 の上と左側の数字、6 は 25 の上にある数字、3 は 6 を含む列です。
この再帰性を証明するには、 個のオブジェクトを
ん + 1
{\displaystyle n+1}
k 個の空でない部分 集合に 分割すると、
（ ん + 1 ）
{\displaystyle (n+1)}
番目のオブジェクトが単一オブジェクトとして含まれるか含まれないかのどちらかになることに注意してください。単一オブジェクトが部分集合の1つである方法の数は次のように与えられます。
{
ん
け − 1
}
{\displaystyle \left\{{n \atop k-1}\right\}}
残りの n個のオブジェクトを 利用可能 な
け − 1
{\displaystyle k-1}
サブセットに分割する必要があるためです 。他のケースでは、
（ ん + 1 ）
{\displaystyle (n+1)}
番目のオブジェクトは他のオブジェクトを含むサブセットに属します。方法の数は次のように与えられます。
け
{
ん け
}
{\displaystyle k\left\{{n \atop k}\right\}}
（ ん + 1 ）
{\displaystyle (n+1)}
番目以外のすべてのオブジェクトを k 個 のサブセットに分割すると、 オブジェクト を挿入するための k 個の選択肢が残ります 。これら 2 つの値を合計すると、目的の結果が得られます。
ん + 1
{\displaystyle n+1}
別の再帰関係は次のように与えられる。
{
ん
け
}
=
け
ん
け ！
−
∑
r = 1
け − 1
{
ん
r
}
（ け − r ） ！
。
{\displaystyle \left\lbrace {\begin{matrix}n\\k\end{matrix}}\right\rbrace ={\frac {k^{n}}{k!}}-\sum _{r=1}^{k-1}{\frac {\left\lbrace {\begin{matrix}n\\r\end{matrix}}\right\rbrace }{(kr)!}}.}
これはで 評価することから導かれます 。
∑
r = 0
ん
{
ん r
}
（ x
）
r
=
x
ん
{\displaystyle \sum _{r=0}^{n}\left\{{n \atop r}\right\}(x)_{r}=x^{n}}
x = け
{\displaystyle x=k}
シンプルなアイデンティティ 単純なアイデンティティとしては、
{
ん
ん − 1
}
=
（
ん 2
）
。
{\displaystyle \left\{{n \atop n-1}\right\}={\binom {n}{2}}.}
これは、 n 個の要素を n − 1 個のセットに分割するということは、必然的にサイズ 2 のセット 1 つとサイズ 1 のセット n − 2 個に分割することを意味するためです 。したがって、これらの 2 つの要素を選択するだけで済みます。
そして
{
ん 2
}
=
2
ん − 1
− 1.
{\displaystyle \left\{{n \atop 2}\right\}=2^{n-1}-1.}
これを理解するには、まず、相補的なサブセット A と Bの 順序付きペアが 2 n 個あることに注目してください 。1 つのケースでは A が空で、もう 1 つのケースでは B が空なので、サブセットの順序付きペアは 2 n − 2 個残ります。最後に、 順序付き ペアではなく 順序なし ペアが必要なので、この最後の数を 2 で割ると、上記の結果が得られます。
再帰関係の別の明示的な展開により、上記の例の精神に沿った恒等式が得られます。
アイデンティティ 『Concrete Mathematics』 のセクション 6.1 の表には、 スターリング数を含む有限和の一般化された形式が多数示されています。この記事に関連する特定の有限和には次のものがあります。
{
ん + 1
け + 1
}
=
∑
じ = け
ん
（
ん じ
）
{
じ け
}
{
ん + 1
け + 1
}
=
∑
じ = け
ん
（ け + 1
）
ん − じ
{
じ け
}
{
ん + け + 1
け
}
=
∑
じ = 0
け
じ
{
ん + じ
じ
}
{
ん
ℓ + メートル
}
（
ℓ + メートル
ℓ
）
=
∑
け
{
け ℓ
}
{
ん − け
メートル
}
（
ん け
）
{\displaystyle {\begin{aligned}\left\{{n+1 \atop k+1}\right\}&=\sum _{j=k}^{n}{n \choose j}\left\{{j \atop k}\right\}\\\left\{{n+1 \atop k+1}\right\}&=\sum _{j=k}^{n}(k+1)^{nj}\left\{{j \atop k}\right\}\\\left\{{n+k+1 \atop k}\right\}&=\sum _{j=0}^{k}j\left\{{n+j \atop j}\right\}\\\left\{{n \atop \ell +m}\right\}{\binom {\ell +m}{\ell }}&=\sum _{k}\left\{{k \atop \ell }\right\}\left\{{nk \atop m}\right\}{\binom {n}{k}}\end{aligned}}}
第二種スターリング数は明示的な式で与えられます。
{
ん け
}
=
1
け ！
∑
じ = 0
け
（ − 1
）
け − じ
（
け じ
）
じ
ん
=
∑
じ = 0
け
（ − 1
）
け − じ
じ
ん
（ け − じ ） ！ じ ！
。
{\displaystyle \left\{{n \atop k}\right\}={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{k \choose j}j^{n}=\sum _{j=0}^{k}{\frac {(-1)^{k-j}j^{n}}{(k-j)!j!}}.}
これは、包含-排除法を使用して nから k への 全射を数え 、そのような全射の数が であるという事実を使用すること で導出できます 。
k
!
{
n
k
}
{\textstyle k!\left\{{n \atop k}\right\}}
さらに、この式はx = 0
で評価された 単項式 の k 番目の 前方差分 の特殊なケースです。
x
n
{\displaystyle x^{n}}
Δ
k
x
n
=
∑
j
=
0
k
(
−
1
)
k
−
j
(
k
j
)
(
x
+
j
)
n
.
{\displaystyle \Delta ^{k}x^{n}=\sum _{j=0}^{k}(-1)^{k-j}{k \choose j}(x+j)^{n}.}
ベルヌーイ多項式は これらの前進差分で表すことができる ため、 ベルヌーイ数 における関係式がすぐに得られます。
B
m
(
0
)
=
∑
k
=
0
m
(
−
1
)
k
k
!
k
+
1
{
m
k
}
.
{\displaystyle B_{m}(0)=\sum _{k=0}^{m}{\frac {(-1)^{k}k!}{k+1}}\left\{{m \atop k}\right\}.}
不完全指数 ベル多項式 B n , k ( x 1 , x 2 ,...) を 1 のシーケンス上で評価すると、第 2 種のスターリング数に等しくなります。
{
n
k
}
=
B
n
,
k
(
1
,
1
,
…
,
1
)
.
{\displaystyle \left\{{n \atop k}\right\}=B_{n,k}(1,1,\dots ,1).}
NISTの数学関数ハンドブック に記載されているもう一つの明示的な式 は
{
n
k
}
=
∑
c
1
+
…
+
c
k
=
n
−
k
c
1
,
…
,
c
k
≥
0
1
c
1
2
c
2
⋯
k
c
k
{\displaystyle \left\{{n \atop k}\right\}=\sum _{\begin{array}{c}c_{1}+\ldots +c_{k}=n-k\\c_{1},\ldots ,\ c_{k}\ \geq \ 0\end{array}}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}}
パリティ 第二種スターリング数のパリティ。 第二種スターリング数の偶奇 性は、関連する 二項係数 の偶奇性と同じです 。
{
n
k
}
≡
(
z
w
)
(
mod
2
)
,
{\displaystyle \left\{{n \atop k}\right\}\equiv {\binom {z}{w}}\ {\pmod {2}},}
どこ
z
=
n
−
⌈
k
+
1
2
⌉
,
w
=
⌊
k
−
1
2
⌋
.
{\displaystyle z=n-\left\lceil \displaystyle {\frac {k+1}{2}}\right\rceil ,\ w=\left\lfloor \displaystyle {\frac {k-1}{2}}\right\rfloor .}
この関係は、 n 座標 と k座標を シェルピンスキーの三角形 にマッピングすることによって指定されます 。
もっと直接的に言えば、2 つのセットに、それぞれの式の結果の 2 進表現における 1 の位置が含まれるとします。
A
:
∑
i
∈
A
2
i
=
n
−
k
,
B
:
∑
j
∈
B
2
j
=
⌊
k
−
1
2
⌋
.
{\displaystyle {\begin{aligned}\mathbb {A} :\ \sum _{i\in \mathbb {A} }2^{i}&=n-k,\\\mathbb {B} :\ \sum _{j\in \mathbb {B} }2^{j}&=\left\lfloor {\dfrac {k-1}{2}}\right\rfloor .\\\end{aligned}}}
次の 2 つのセットを交差させることで、ビット単位の AND 演算を模倣できます 。
{
n
k
}
mod
2
=
{
0
,
A
∩
B
≠
∅
;
1
,
A
∩
B
=
∅
;
{\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2={\begin{cases}0,&\mathbb {A} \cap \mathbb {B} \neq \emptyset ;\\1,&\mathbb {A} \cap \mathbb {B} =\emptyset ;\end{cases}}}
第二種スターリング数のパリティを O (1) 時間で求める。 擬似コード では次のようになる。
{
n
k
}
mod
2
:=
[
(
(
n
−
k
)
&
(
(
k
−
1
)
d
i
v
2
)
)
=
0
]
;
{\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2:=\left[\left(\left(n-k\right)\ \And \ \left(\left(k-1\right)\,\mathrm {div} \,2\right)\right)=0\right];}
アイバーソンブラケットは どこ ですか 。
[
b
]
{\displaystyle \left[b\right]}
第二種中心スターリング数の偶奇性が奇数となるのは 、 2進数表現で 連続する2つの1を持たない数である フィビ二進数 の 場合のみである。 [11]
{
2
n
n
}
{\displaystyle \textstyle \left\{{2n \atop n}\right\}}
n
{\displaystyle n}
生成関数 固定された整数 n に対して、 第二種スターリング数の 通常の生成関数は 次のように与えられる。
{
n
0
}
,
{
n
1
}
,
…
{\displaystyle \left\{{n \atop 0}\right\},\left\{{n \atop 1}\right\},\ldots }
∑
k
=
0
n
{
n
k
}
x
k
=
T
n
(
x
)
,
{\displaystyle \sum _{k=0}^{n}\left\{{n \atop k}\right\}x^{k}=T_{n}(x),}
ここで、は タッチャード多項式 です 。代わりに、スターリング数を階乗降数に対して合計すると、次のような恒等式が示されます。
T
n
(
x
)
{\displaystyle T_{n}(x)}
∑
k
=
0
n
{
n
k
}
(
x
)
k
=
x
n
{\displaystyle \sum _{k=0}^{n}\left\{{n \atop k}\right\}(x)_{k}=x^{n}}
そして
∑
k
=
1
n
+
1
{
n
+
1
k
}
(
x
−
1
)
k
−
1
=
x
n
,
{\displaystyle \sum _{k=1}^{n+1}\left\{{n+1 \atop k}\right\}(x-1)_{k-1}=x^{n},}
特別なケースがある
∑
k
=
0
n
{
n
k
}
(
n
)
k
=
n
n
.
{\displaystyle \sum _{k=0}^{n}\left\{{n \atop k}\right\}(n)_{k}=n^{n}.}
固定された整数 k に対して、第二種スターリング数は有理数通常生成関数を持つ。
∑
n
=
k
∞
{
n
k
}
x
n
−
k
=
∏
r
=
1
k
1
1
−
r
x
=
1
x
k
+
1
(
1
/
x
)
k
+
1
{\displaystyle \sum _{n=k}^{\infty }\left\{{n \atop k}\right\}x^{n-k}=\prod _{r=1}^{k}{\frac {1}{1-rx}}={\frac {1}{x^{k+1}(1/x)_{k+1}}}}
そして 指数関数的な生成関数 は次のように表される。
∑
n
=
k
∞
{
n
k
}
x
n
n
!
=
(
e
x
−
1
)
k
k
!
.
{\displaystyle \sum _{n=k}^{\infty }\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}={\frac {(e^{x}-1)^{k}}{k!}}.}
第二種スターリング数の混合二変量生成関数は
∑
k
=
0
∞
∑
n
=
k
∞
{
n
k
}
x
n
n
!
y
k
=
e
y
(
e
x
−
1
)
.
{\displaystyle \sum _{k=0}^{\infty }\sum _{n=k}^{\infty }\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}y^{k}=e^{y(e^{x}-1)}.}
下限と上限 かつ ならば 、
n
≥
2
{\displaystyle n\geq 2}
1
≤
k
≤
n
−
1
{\displaystyle 1\leq k\leq n-1}
1
2
(
k
2
+
k
+
2
)
k
n
−
k
−
1
−
1
≤
{
n
k
}
≤
1
2
(
n
k
)
k
n
−
k
{\displaystyle {\frac {1}{2}}(k^{2}+k+2)k^{n-k-1}-1\leq \left\{{n \atop k}\right\}\leq {\frac {1}{2}}{n \choose k}k^{n-k}}
[12]
漸近近似 第二種スターリング数の漸近値 の固定値は次 のように与えられる。
k
,
{\displaystyle k,}
n
→
∞
{\displaystyle n\rightarrow \infty }
{
n
k
}
∼
n
→
∞
k
n
k
!
.
{\displaystyle \left\{{n \atop k}\right\}{\underset {n\to \infty }{\sim }}{\frac {k^{n}}{k!}}.}
（ここで oは 小文字のo表記 を表す ）
ならば
k
=
o
(
n
)
{\displaystyle k=o({\sqrt {n}})}
{
n
+
k
n
}
∼
n
→
∞
n
2
k
2
k
k
!
.
{\displaystyle \left\{{n+k \atop n}\right\}{\underset {n\to \infty }{\sim }}{\frac {n^{2k}}{2^{k}k!}}.}
[13] 一様に有効な近似も存在する。1 < k < n となるすべての k に対して、
{
n
k
}
∼
v
−
1
v
(
1
−
G
)
(
v
−
1
v
−
G
)
n
−
k
k
n
n
k
e
k
(
1
−
G
)
(
n
k
)
,
{\displaystyle \left\{{n \atop k}\right\}\sim {\sqrt {\frac {v-1}{v(1-G)}}}\left({\frac {v-1}{v-G}}\right)^{n-k}{\frac {k^{n}}{n^{k}}}e^{k(1-G)}\left({n \atop k}\right),}
ここで 、 は の唯一の解である 。 [14] 相対誤差は約 に制限される 。
v
=
n
/
k
{\displaystyle v=n/k}
G
∈
(
0
,
1
)
{\displaystyle G\in (0,1)}
G
=
v
e
G
−
v
{\displaystyle G=ve^{G-v}}
0.066
/
n
{\displaystyle 0.066/n}
単一峰性 を固定すると 、 は単峰性、つまり、増加してから減少する。最大値は、 k の連続する最大2つの値で達成される 。
つまり 、
n
{\displaystyle n}
{
n
k
}
{\displaystyle \left\{{n \atop k}\right\}}
k
n
{\displaystyle k_{n}}
{
n
1
}
<
{
n
2
}
<
⋯
<
{
n
k
n
}
≥
{
n
k
n
+
1
}
>
⋯
>
{
n
n
}
.
{\displaystyle \left\{{n \atop 1}\right\}<\left\{{n \atop 2}\right\}<\cdots <\left\{{n \atop k_{n}}\right\}\geq \left\{{n \atop k_{n}+1}\right\}>\cdots >\left\{{n \atop n}\right\}.}
上記の値の表を見ると、最初のいくつかの値 は
k
n
{\displaystyle k_{n}}
0
,
1
,
1
,
2
,
2
,
3
,
3
,
4
,
4
,
4
,
5
,
…
{\displaystyle 0,1,1,2,2,3,3,4,4,4,5,\ldots }
大きい
ときは
n
{\displaystyle n}
k
n
∼
n
→
∞
n
log
n
,
{\displaystyle k_{n}{\underset {n\to \infty }{\sim }}{\frac {n}{\log n}},}
スターリング数の最大値は次のように近似できる。
log
{
n
k
n
}
=
n
log
n
−
n
log
log
n
−
n
+
O
(
n
log
log
n
/
log
n
)
.
{\displaystyle \log \left\{{n \atop k_{n}}\right\}=n\log n-n\log \log n-n+O(n\log \log n/\log n).}
[12]
アプリケーション
ポアソン分布のモーメント Xが ポアソン分布 に従う 確率変数 で 期待値 がλの 場合 、その n 次の モーメント は
E
(
X
n
)
=
∑
k
=
0
n
{
n
k
}
λ
k
.
{\displaystyle E(X^{n})=\sum _{k=0}^{n}\left\{{n \atop k}\right\}\lambda ^{k}.}
特に、 期待値が 1 であるポアソン分布の n 番目のモーメントは、サイズ nの 集合の分割 数とまったく同じです。つまり、 n 番目の ベル数 です(この事実は ドビンスキーの公式 です)。
ランダム順列の固定点のモーメント ランダム変数 Xを、サイズ m の有限集合の 一様分布 ランダム順列 の固定点の数とします 。すると、 X の n 次のモーメントは
E
(
X
n
)
=
∑
k
=
0
m
{
n
k
}
.
{\displaystyle E(X^{n})=\sum _{k=0}^{m}\left\{{n \atop k}\right\}.}
注意: 合計の上限は n ではなく m です。
言い換えれば、この 確率分布の n 番目のモーメントは、サイズ n の集合を m 個 以下の部分に分割する回数です。これは、 表記が少し異なりますが、
ランダム順列統計 に関する記事で証明されています。
押韻構成 第 2 種のスターリング数は、 n 行の詩の 押韻パターン の総数を表すことができます 。k 個の固有の押韻音節を使用した n 行 の可能な押韻パターンの数を示します 。たとえば、3 行の詩の場合、1 つの押韻 (aaa) のみを使用する押韻パターンが 1 つ、2 つの押韻 (aab、aba、abb) を使用する押韻パターンが 3 つ、3 つの押韻 (abc) を使用する押韻パターンが 1 つあります。
S
(
n
,
k
)
{\displaystyle S(n,k)}
バリエーション
r -第2種スターリング数 第二種のr-スターリング数は、 n 個のオブジェクトの集合を k 個の空でない分離した部分集合に 分割する回数を数える。 この場合、最初の r 個 の要素は異なる部分集合に含まれる。 [15] これらの数は再帰関係を満たす
。
{
n
k
}
r
{\displaystyle \left\{{n \atop k}\right\}_{r}}
{
n
k
}
r
=
k
{
n
−
1
k
}
r
+
{
n
−
1
k
−
1
}
r
{\displaystyle \left\{{n \atop k}\right\}_{r}=k\left\{{n-1 \atop k}\right\}_{r}+\left\{{n-1 \atop k-1}\right\}_{r}}
いくつかの組み合わせ的恒等式とこれらの数と文脈自由文法との関係については [16]を参照のこと。
第二種スターリング数 r 関連第二種スターリング数は、 n個 のオブジェクトの集合を k 個の部分集合に分割する方法の数であり 、各部分集合には少なくとも r 個の要素が含まれる。 [17] これは次のように表され 、再帰関係に従う。
S
r
(
n
,
k
)
{\displaystyle S_{r}(n,k)}
S
r
(
n
+
1
,
k
)
=
k
S
r
(
n
,
k
)
+
(
n
r
−
1
)
S
r
(
n
−
r
+
1
,
k
−
1
)
{\displaystyle S_{r}(n+1,k)=k\ S_{r}(n,k)+{\binom {n}{r-1}}S_{r}(n-r+1,k-1)}
2 関連の数値 ( OEIS のシーケンス A008299 ) は、他の場所では「ワード数」として、また マーラー多項式 の係数の大きさとして表示されます 。
第二種簡約スターリング数 整数 1, 2, ..., nで分割する n 個のオブジェクトを表します 。 で表される第 2 種の既約スターリング数を、整数 1, 2, ..., nを k 個 の空でない部分集合に 分割する方法の数として定義します。この場合、 各部分集合のすべての要素のペアワイズ距離は少なくとも d になります。つまり、与えられた部分集合内の任意の整数 i と j に対して、 が要求されます 。これらの数は次式を満たすことが示されています。
S
d
(
n
,
k
)
{\displaystyle S^{d}(n,k)}
|
i
−
j
|
≥
d
{\displaystyle |i-j|\geq d}
S
d
(
n
,
k
)
=
S
(
n
−
d
+
1
,
k
−
d
+
1
)
,
n
≥
k
≥
d
{\displaystyle S^{d}(n,k)=S(n-d+1,k-d+1),n\geq k\geq d}
（そのため「簡約」という名前が付けられている）。 [18] 定義と簡約式の両方から、 第二種のよく知られたスターリング数であることがわかる。
S
1
(
n
,
k
)
=
S
(
n
,
k
)
{\displaystyle S^{1}(n,k)=S(n,k)}
参照
参考文献
^ ロナルド・L・グラハム、ドナルド・E・クヌース、オーレン・パタシュニック（1988） 『具体的な数学 』、アディソン・ウェズレー、マサチューセッツ州リーディング。ISBN 0-201-14236-8 、 p.244。 ^ 「第二種のスターリング数、定理3.4.1」。 ^紛らわしいことに、組合せ論者が 階乗降 格に使用する表記法は 、階乗 昇格 の 特殊関数 で使用される表記法と一致しています。 ポッホハマー記号 を参照してください。 ^ スターリング数の変形による級数の変換、イマニュエル・マルクス、 アメリカ数学月刊誌 69 、#6 (1962年6月～7月)、pp. 530～532、 JSTOR 2311194。 ^ Antonio Salmeri、Introduzione alla teoria dei係数i fattoriali、 Giornale di Matematiche di Battaglini 90 (1962)、44–54ページ。 ^ ab Knuth, DE (1992)、「表記に関する2つの注意」、 Amer. Math. Monthly 、 99 (5): 403–422、 arXiv : math/9205211 、 Bibcode :1992math......5211K、 doi :10.2307/2325085、 JSTOR 2325085、 S2CID 119584305 ^ Donald E. Knuth, Fundamental Algorithms 、マサチューセッツ州レディング：Addison–Wesley、1968年。 ^ p. 66、Donald E. Knuth、 「Fundamental Algorithms 」、第3版、マサチューセッツ州レディング：Addison–Wesley、1997年。 ^ Jovan Karamata、「Théorèmes sur la sommabilité exponentielle et d'autres sommabilités s'y rattachant」、 Mathematica (Cluj) 9 (1935)、pp、164–178。 ^ Sprugnoli, Renzo (1994)、「Riordan配列と組み合わせ和」 (PDF) 、 離散数学 、 132 (1–3): 267–290、 doi : 10.1016/0012-365X(92)00570-H 、 MR 1297386 ^ Chan, O-Yeat; Manna, Dante (2010)、「第二種のスターリング数の合同性」 (PDF) 、 実験数学の宝石 、現代数学、第517巻、プロビデンス、ロードアイランド州：アメリカ数学協会、pp. 97–111、 doi ：10.1090/conm/517/10135、 MR 2731094 ^ ab Rennie, BC; Dobson, AJ (1969). 「第二種のスターリング数について」. Journal of Combinatorial Theory . 7 (2): 116–121. doi : 10.1016/S0021-9800(69)80045-1 . ISSN 0021-9800. ^ LC Hsu 、「ゼロのn次差の漸近展開に関するノート」、AMS Vol.19 NO.2 1948、pp. 273--277 ^ NM Temme、「スターリング数の漸近的推定」、応用数学研究 89:233-243 (1993)、Elsevier Science Publishing。 ^ Broder, A. (1984). r-スターリング数. 離散数学 49, 241-259 ^ Triana, J. (2022). 文脈自由文法による第2種のr-スターリング数。オートマトン、言語、組合せ論ジャーナル27(4), 323-333 ^ L. Comtet, Advanced Combinatorics 、Reidel、1974年、222ページ。 ^ A. MohrとTD Porter、 「スターリング数を含む彩色多項式の応用 」、Journal of Combinatorial Mathematics and Combinatorial Computing 70 (2009)、57–64。
Boyadzhiev, Khristo (2012). 「第二種スターリング数との接近遭遇」. 数学雑誌 . 85 (4): 252–266. arXiv : 1806.09468 . doi :10.4169/math.mag.85.4.252. S2CID 115176876. 。
![{\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2:=\left[\left(\left(nk\right)\ \And \ \left(\left(k-1\right)\,\mathrm {div} \,2\right)\right)=0\right];}](https://wikimedia.org/api/rest_v1/media/math/render/svg/130bd9c11974efed18b1cb95b5113109a2da7a0a)
![{\displaystyle \left[b\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/813105d450b3e25e8f985010eac1eeb8f95ccf17)
Wikiversity のパーティション関連数三角形に関する学習教材