Stirling数-1

393

第１種Stirling数

第１種Stirling数は、 $n$ 個の要素を $k$ 個の部分集合ではなく、サイクルに並べる場合の数を数える。例えば、 $4$ 要素の場合、

$[1, 2, 3] [4]$ $[1, 2, 4] [3]$ $[1, 3, 4] [2]$ $[2, 3, 4] [1]$
　 $[1, 3, 2] [4]$ $[1, 4, 2] [3]$ $[1, 4, 3] [2]$ $[2, 4, 3] [1]$
　 $[1, 2] [3, 4]$ $[1, 3] [2, 4]$ $[1, 4] [2, 3]$

の $11$ 通りのサイクルが存在することから、 $(\binom{4}{2}) = 11$ である。

以下が第 $1$ 種Stirling数の具体的数値である

$n$	$(\binom{n}{0})$	$(\binom{n}{1})$	$(\binom{n}{2})$	$(\binom{n}{3})$	$(\binom{n}{4})$	$(\binom{n}{5})$	$(\binom{n}{6})$	$(\binom{n}{7})$	$(\binom{n}{8})$	$(\binom{n}{9})$
$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$

第２種Stirling数

第２種Stirling数は、 $n$ 個の要素からなる集合を $k$ 個の空でない部分集合に分ける場合の数を表している。例えば $4$ 要素の集合について、

$[1, 2, 3] \cup [4]$ 　 $[1, 2, 4] \cup [3]$ 　 $[1, 3, 4] \cup [2]$
　 $[2, 3, 4] \cup [1]$ 　 $[1, 2] \cup [3, 4]$ 　 $[1, 3] \cup [2, 4]$ 　
　 $[1, 4] \cup [2, 3]$ 　　　　　

の $7$ 通りが考えられるので、 $(\binom{4}{2}) = 7$ である。

以下が第 $2 種$ Stirling数の具体的数値である

$n$	$(\binom{n}{0})$	$(\binom{n}{1})$	$(\binom{n}{2})$	$(\binom{n}{3})$	$(\binom{n}{4})$	$(\binom{n}{5})$	$(\binom{n}{6})$	$(\binom{n}{7})$	$(\binom{n}{8})$	$(\binom{n}{9})$
$0$	$1$
$1$	$0$	$1$
$2$	$0$	$1$	$1$
$3$	$0$	$1$	$3$	$1$
$4$	$0$	$1$	$7$	$6$	$1$
$5$	$0$	$1$	$15$	$25$	$10$	$1$
$6$	$0$	$1$	$31$	$90$	$65$	$15$	$1$
$7$	$0$	$1$	$63$	$301$	$350$	$140$	$21$	$1$
$8$	$0$	$1$	$127$	$966$	$1701$	$1050$	$266$	$28$	$1$
$9$	$0$	$1$	$255$	$3025$	$7770$	$6951$	$2646$	$462$	$36$	$1$

Stirling数についての基本的な式

以下では第１種と第２種の区別をつけるため、第 $n$ 種Stirling数を ${(\binom{n}{k})}_{n}$ と表記する。
例えば、 ${(\binom{4}{2})}_{1} = 11, {(\binom{4}{2})}_{2} = 7$ である。

漸化式

${(\binom{n}{k})}_{1} = (n - 1) {(\binom{n - 1}{k})}_{1} + {(\binom{n - 1}{k - 1})}_{1}$
${(\binom{n}{k})}_{2} = k {(\binom{n - 1}{k})}_{2} + {(\binom{n - 1}{k - 1})}_{2}$

特殊な数値の場合

${(\binom{n}{0})}_{1} = {(\binom{n}{0})}_{2} = [n = 0]$
${(\binom{n}{1})}_{1} = (n - 1)! [n > 0]$
${(\binom{n}{1})}_{2} = [n > 0]$
${(\binom{n}{2})}_{1} = (n - 1)! H_{n - 1} [n > 0]$
${(\binom{n}{2})}_{2} = 2^{n - 1} - 1 [n > 0]$
${(\binom{n}{n - 1})}_{1} = {(\binom{n}{n - 1})}_{2} = (\binom{n}{2})$
${(\binom{n}{n})}_{1} = {(\binom{n}{n})}_{2} = (\binom{n}{n}) = 1$
${(\binom{n}{k})}_{1} = {(\binom{n}{k})}_{2} = (\binom{n}{k}) (k > n)$

べき間の変換

$x^{n} = \sum_{k} {(\binom{n}{k})}_{2} x^{\underset{―}{k}} = \sum {(\binom{n}{k})}_{2} (- 1)^{n - k} x^{\bar{k}}$
$x^{\underset{―}{n}} = \sum_{k} {(\binom{n}{k})}_{1} (- 1)^{n - k} x^{k}$
$x^{\bar{n}} = \sum_{k} {(\binom{n}{k})}_{1} x^{k}$

反転公式

$\sum_{k} {(\binom{n}{k})}_{1} {(\binom{k}{m})}_{2} (- 1)^{n - k} = [m = n]$
$\sum_{k} {(\binom{n}{k})}_{2} {(\binom{k}{m})}_{1} (- 1)^{n - k} = [m = n]$