スターリング数
第2種スターリング数 { n k } {\displaystyle \{{\textstyle {n \atop k}}\}} は、組合せ数学において、番号づけされた n {\displaystyle n} 個の要素をグループ k {\displaystyle k} 個に分割する組み合わせの数を与える。分割する要素は番号付けされているので個別に区別できるが、グループは順序を特に区別しないものとする。選択された要素を ( 0 , 2 , 3 ) {\displaystyle (0,2,3)} と書いた場合、 ( 0 , 3 , 2 ) {\displaystyle (0,3,2)} のように要素を置換した列も同一であるとみなす。分割されたグループに含まれる要素の数は均等である必要はなく、1個の要素しか含まないグループがあってもよいとする。要素4個をグループ2個に分割するには、要素が1個と3個のグループに分割する場合と、要素が2個と2個のグループに分割する組み合わせが挙げられる。前者の分割法では、要素4個から単独グループをなす要素1個を選ぶ組み合わせ、すなわち、4通りだけが存在する。後者の分割法では、要素4個から一方のグループを構成する2個を選ぶ組み合わせを考えればよい。その組み合わせは6通りあるのだが、分割される双方のグループが要素2個で構成されることから、グループ間に対称性がある。その対称性から2の自由度がある。その自由度を補正すると、後者の分割法は3通りの組み合わせがあることになる。したがって、要素 0, 1, 2, 3 をグループ2個に分割する組み合わせは、全部で以下の7通りがある。
第2種スターリング数 (en:Stirling numbers of the second kind) { n k } {\displaystyle \{{\textstyle {n \atop k}}\}} は、 x n {\displaystyle x^{n}} を下降階乗冪 x k _ ≡ x ( x − 1 ) ( x − 2 ) ⋯ ( x − k + 1 ) {\displaystyle x^{\underline {k}}\equiv x\,(x-1)(x-2)\cdots (x-k+1)} の級数:
x n = ∑ k = 0 n { n k } x k _ {\displaystyle x^{n}=\textstyle \sum \limits _{k=0}^{n}\displaystyle \left\{{n \atop k}\right\}\,x^{\underline {k}}}
で展開したときの展開係数として定義される。この定義では、 0 ≤ k ≤ n {\displaystyle 0\leq k\leq n} である。便宜上、 { 0 0 } = 1 {\displaystyle \{{\textstyle {0 \atop 0}}\}=1} と定義する。第2種スターリング数は