Stirling数-1
第１種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$通りのサイクルが存在することから、$\displaystyle\binom{4}{2}=11$である。
以下が第$1$種Stirling数の具体的数値である
| $n$ | $\displaystyle\binom{n}{0}$ | $\displaystyle\binom{n}{1}$ | $\displaystyle\binom{n}{2}$ | $\displaystyle\binom{n}{3}$ | $\displaystyle\binom{n}{4}$ | $\displaystyle\binom{n}{5}$ | $\displaystyle\binom{n}{6}$ | $\displaystyle\binom{n}{7}$ | $\displaystyle\binom{n}{8}$ | $\displaystyle\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$通りが考えられるので、$\displaystyle\binom{4}{2}=7$である。
以下が第$2種$Stirling数の具体的数値である
| $n$ | $\displaystyle\binom{n}{0}$ | $\displaystyle\binom{n}{1}$ | $\displaystyle\binom{n}{2}$ | $\displaystyle\binom{n}{3}$ | $\displaystyle\binom{n}{4}$ | $\displaystyle\binom{n}{5}$ | $\displaystyle\binom{n}{6}$ | $\displaystyle\binom{n}{7}$ | $\displaystyle\binom{n}{8}$ | $\displaystyle\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数を$\displaystyle\binom{n}{k}_n$と表記する。
例えば、$\displaystyle\binom{4}{2}_1=11,\displaystyle\binom{4}{2}_2=7$である。
漸化式
$$\displaystyle\binom{n}{k}_1=(n-1)\displaystyle\binom{n-1}{k}_1+\displaystyle\binom{n-1}{k-1}_1$$
$$\displaystyle\binom{n}{k}_2=k\displaystyle\binom{n-1}{k}_2+\displaystyle\binom{n-1}{k-1}_2$$
特殊な数値の場合
$$\displaystyle\binom{n}{0}_1=\displaystyle\binom{n}{0}_2=[n=0]$$
$$\displaystyle\binom{n}{1}_1=(n-1)![n>0]$$
$$\displaystyle\binom{n}{1}_2=[n>0]$$
$$\displaystyle\binom{n}{2}_1=(n-1)!H_{n-1}[n>0]$$
$$\displaystyle\binom{n}{2}_2=2^{n-1}-1[n>0]$$
$$\displaystyle\binom{n}{n-1}_1=\displaystyle\binom{n}{n-1}_2=\displaystyle\binom{n}{2}$$
$$\displaystyle\binom{n}{n}_1=\displaystyle\binom{n}{n}_2=\displaystyle\binom{n}{n}=1$$
$$\displaystyle\binom{n}{k}_1=\displaystyle\binom{n}{k}_2=\displaystyle\binom{n}{k}\,\,\,\,(k>n)$$
べき間の変換
$$x^n=\displaystyle\sum_k\displaystyle\binom{n}{k}_2x^{\underline{k}}=\sum\displaystyle\binom{n}{k}_2(-1)^{n-k}x^\bar{k}$$
$$x^{\underline{n}}=\sum_k\displaystyle\binom{n}{k}_1(-1)^{n-k}x^k$$
$$x^{\bar{n}}=\sum_k\displaystyle\binom{n}{k}_1x^k$$
反転公式
$$\sum_k\displaystyle\binom{n}{k}_1\displaystyle\binom{k}{m}_2(-1)^{n-k}=[m=n]$$
$$\sum_k\displaystyle\binom{n}{k}_2\displaystyle\binom{k}{m}_1(-1)^{n-k}=[m=n]$$
その他の公式については Stirling数-2 を参考。