组合数学、容斥原理

@@基础概念 ：容斥原理又称排容原理，在组合数学里，其说明若 A1...An 为有限的集合，则如下图，其中 |A| 表示 A 的基数（一个集合元素的个数）。例如在两个集合的情况时，我们可以将 |A| 和 |B| 相加，再减去其交集的基数，而得到其并集的基数。 摘自维基百科

：有 n 个球排成一行，你有 k 种颜色，要求给每一个球染色，相邻两个球颜色不可以相同，并且每种颜色至少使用一次。

:和错排列问题相同，假设没有限制每种颜色至少使用一次，那么问题就很简单，答案就是 k(k-1)^n-1 。这些方案是由 恰好 使用了 i(i=0,1,2, ,k) 种颜色的方案组成的，那么设 fi 为恰好使用了 i 种颜色的方案数，可以得到

@@经典应用之斯特林数

:第一类Stirling数是 分正负 的，其绝对值是 n 个元素的项目分作 k 个环排列。常用的表示方法有 s(n,k) 等。

换一个比较生活化的说法，就是有 n 个人分为 k 组，每组内再按照特定的顺序围圈的分组方法的数目。例如 s(4,2) = 11 :

{A,B},{C,D}

{A,C},{B,D}

{A,D},{B,C}

{A},{B,C,D}

{A},{B,D,C}

{B},{A,C,D}

{B},{A,D,C}

{C},{A,B,D}

{C},{A,D,B}

{D},{A,B,C}

{D},{A,C,B}

给定 S(n,0)=1, S(1,1)=1 ，有 S(n,k) = S(n-1,k-1) + (n-1)S(n-1,k)

递推关系的说明 ：考虑第 n 个物品， n 可以单独构成一个非空循环排列，这样前 n-1 种物品构成 k-1 个非空循环排列，有 S(n-1,k-1) 中方法；也可以前 n-1 种物品构成 k 个非空循环排列，而第 n 个物品插入第 i 个物品的左边，这有 (n-1)S(n-1,k) 种方法。