容斥原理 设 `A, B` 为有限集, 则 `|A uu B| = |A| + |B| - |A nn B|`.

设 `A_1, A_2, cdots, A_n` 为 `n` 个有限集, `n in ZZ^+`. `N = {1, 2, cdots, n}`, 则 `|uuu_(i=1)^n A_i| = sum_(C sube N) (-1)^(|C|-1) |nnn_(j in C) A_j|` `= sum_(k=1)^n (-1)^(k-1) sum_(1 le i_1 lt cdots lt i_k le n) |nnn_(j=1)^k A_(i_j)|`. 即 `n` 个集合的并集的基数, 等于它们每个集合的基数之和, 减去每两个集合的交的基数之和, 加上每三个集合的交的基数之和, ..., 最后加上 `(-1)^(n-1)` 乘以所有集合的交集的基数.

`n = 1` 的情形是平凡的; `n = 2` 时, 即为容斥原理. 设 `n-1` 时命题成立, 则 `n` 的情形, 由容斥原理, 左边 `= |(uuu_(i=1)^(n-1) A_i) uu A_n|` `= |uuu_(i=1)^(n-1) A_i| + |A_n| - |uuu_(i=1)^(n-1) (A_i nn A_n)|` `= sum_(C sube N\\{n}) (-1)^(|C|-1) |nnn_(j in C) A_j| + |A_n|` `+ sum_(C sube N\\{n}) (-1)^|C| |nnn_(j in C) (A_j nn A_n)|` `=` 右边

设 `A_1, A_2, cdots, A_n` 为 `n` 个基数相等的有限集, `n in ZZ^+`. `S_0 supe uuu_(i=1)^n A_i`, `S_k = nnn_(i=1)^k A_i`, `bar S_k = S_0 \\ S_k`, `k = 1, 2, cdots, n`. 则 `|nnn_(k=1)^n bar S_k| = sum_(k=0)^n (-1)^k (n;k) |S_k|`.

易知 `A_1, A_2, cdots, A_n` 中任意 `k` 个集合的交的基数都等于 `|S_k|`, 而从 `n` 个集合中选出 `k` 个有 `(n;k)` 种选法, 所以 `|nnn_(k=1)^n bar S_k| = |S_0| - |uuu_(k=1)^n S_k|` `= |S_0| + sum_(k=1)^n (-1)^k (n;k) |S_k|`.

错排问题 有 `n` 封信和 `n` 只对应的信封, 有黑暗中随意将每封信装进一个信封, 设恰好每封信都装错信封的装法有 `D_n` 种.
1. 求 `D_n`;
2. 求 `n to oo` 时, 每封信都装错信封的概率.

以集合 `S_k` 记所有使得前 `k` 封信被装进对的信封的安排, 则 `|S_k| = (n-k)!`, `k = 1, 2, cdots, n`. 所求的数为 `|nnn_(k=1)^n bar S_k|` `= sum_(k=0)^n (-1)^k (n;k) (n-k)!` `= sum_(k=0)^n (-1)^k (n!)/(k!)`. `n to oo` 时, 所求概率为 `lim_(n to oo) 1/(n!) sum_(k=0)^n (-1)^k (n!)/(k!)` `= sum_(k=0)^oo (-1)^k/(k!) = "e"^-1`.

我们导出递推公式 `D_n = { 1, if n = 0; 0, if n = 1; (n-1)*(D_(n-2) + D_(n-1)), otherwise; :}` `n = 0` 时, 没有信封也没有信, 1 种装法是平凡的. `n = 1` 时, 只能把唯一的信装入唯一的信封, 必不会装错, 故有 0 种装法. 现用 `i mapsto j` 表示第 `i` 封信被装入了第 `j` 个信封. 考虑任意一个 `n`-错排, `n gt 1`, 假设 `j mapsto n`, `n mapsto i`.
1. 若 `i = j`, 该错排实际交换了第 `i` 和第 `n` 封信. 将这两封信去掉就得到剩下 `n-2` 封信的一个错排;
2. 若 `i != j`, 将第 `j` 封信改为装入第 `i` 个信封, 即 `j mapsto i`, 然后去掉第 `n` 封信, 就得到剩下 `n-1` 封信的一个错排.
以上两种情况, `i` 都有 `n-1` 种取法, 因此将它们相加, 乘以 `n-1` 就得到最终答案.

n 对夫妇问题 `n` 对夫妇坐成一横排, 问有几种坐法, 使得每一对夫妇的位置都不相邻.

以集合 `S_k` 记所有使得前 `k` 对夫妇坐在一起的排列, 则这 `k` 对夫妇两两 "合并", 后, 可以看作 `2n-k` 个人的全排列, 于是 `|S_k| = 2^k (2n - k)!`, `quad k = 1, 2, cdots, n`. 所求的数为 `|nnn_(k=1)^n bar S_k|` `= sum_(k=0)^n (n;k) (-2)^k (2n-k)!`.

[群友 我是蒟蒻的泰博定理] 设集合 `A` 有 `n` 个元素, 取 `A` 的子集满足真包含关系: `A_1 sub A_2 sub cdots sub A_k`, 这样的取法有几种? 换言之, `A` 的全体子集按包含关系组成的偏序中, 长度为 `k` 的链有几条?

1. [群友 我是某用户的零壹叁] 答案 `f(n, k)` 满足递推关系 `f(n, k) = { 2^n, if k = 1; n!, if k = n+1; (k+1) f(n-1, k) + (k-1) f(n-1, k-1), otherwise; :}` `k = 1` 时, 只要任取 `A` 的一个子集, 有 `2^n` 种取法; `k = n+1` 时, 相当于确定 `A` 的一个排列, 有 `n!` 种.
   其它情况, 取定 `a in A`. 满足题目条件的链中, 不含元素 `a` 的链有 `f(n-1, k)` 条. 含有元素 `a` 的链, 我们将 `a` 去掉, 剩余部分要么是 `n-1` 的集合上长为 `k` 的链, 要么是长为 `k-1` 的链, 这是因为去掉 `a` 的操作可能破坏相邻两个集合的真包含关系. 前者的取法有 `k f(n-1, k)` 种, 后者为 `(k-1) f(n-1, k-1)` 种.
   从递推式可以得到特殊情况 `f(n, 2) = 3^n - 2^n`, `f(n, n) = (n+3)/2 n!` 等等.
2. `f(n, k)` 的显式表达式为 `f(n, k) = sum_(j=0)^(k-1) (-1)^j (k-1;j) (k-j+1)^n`. 我们考虑允许相等的子集链 `A_1 sube A_2 sube cdots sube A_k`, 这给出集合 `A` 的划分 `A_1, A_2 - A_1, A_3 - A_2, cdots, A - A_k`, 且 `A` 的每个元素都可以自由进入到任一划分, 因此这样的链共有 `(k+1)^n` 条. 假如上面的链的 `k-1` 个 `sube` 符号中有 `j` 个取等, 则此链相当于一个长度为 `k-j` 的允许相等的子集链, 共有 `(k-j+1)^n` 条. 由容斥原理即得结论.
更详细的内容参见 oeis A038719.