4

Stirling数-1

330
0
$$$$

第1種Stirling数

第1種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$

第2種Stirling数

第2種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数についての基本的な式

以下では第1種と第2種の区別をつけるため、第$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 を参考。

投稿日:2021427

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

橋本環奈です。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中