第２種スターリング数

Stirling numbers of the second kind

第２種スターリング数 {n, k}
大きさnの集合を、その和集合が全体集合となるk個の互いに素な空でない部分集合に分割する方法の個数。

　{n, k} = {n-1, k-1} + k{n-1, k}

　{0, 0} = 1 ,　{n, 0} = 0 (n > 0)

　xⁿ = {n,0} + {n,1}x + {n,2}x(x-1) + {n,3}x(x-1)(x-2) + … + {n,n}x(x-1)(x-2)…(x-n+1)

第２種スターリング数を使えば、ある個数の頂点の着色が何通りになるか計算できます。たとえば、点が10個で4色以内では、

　{10, 1}+{10, 2}+{10, 3}+{10, 4} = 1+511+9330+34105 = 43947

で、43,947通りになります。