• 記法

第二種スターリング数

定義

$0\leq K \leq N$ とする。第一種スターリング数 $S_1(N,K)$ は以下で定義される。

$S_1(N,K) = [x^K]\prod_{i=0}^{N-1} (x+i)$

つまり、$\prod_{i=0}^{N-1} (x+i) = \sum_{k=0}^{N} S_1(N,k) x^k$ を満たす。

（上昇階乗冪をべき乗の線形和で表したもの）

• 参考: 上昇階乗冪
• 参考: 二項係数との対応

特殊な場合の計算例

• $S_1(0, 0) = 1$
• $S_1(N, 0) = 0$ ($N\geq 1$)
• $S_1(N, 1) = (N-1)!$
• $S_1(N,2) = (N-1)! H_{N-1}$
• $S_1(N, N-1) = N(N-1)/2$
• $S_1(N, N) = 1$

組合せ論的な意味

• 置換 $\sigma \in S(N)$ が $K$ 個の(互いに交わらない)巡回置換の積で表されるような置換の数が $S_1(N,K)$

  • 説明

  互換の積で表したときの最小の互換の数が $N-K$ 個であるような置換の数とも言える

• $1,\ldots,N$ の順列で、record highs（左から見た最大値の更新）がちょうど $K$ 個あるものの数が $S_1(N,K)$。

  例えば、$(3, 1, 4, 1, 5, 9, 2, 6)$ の record highs は $(3, 4, 5, 9)$である。

  • 説明