容斥原理

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

容斥原理 设 `S` 为有限集, `A_1, A_2, cdots, A_n` 为 `S` 的子集, 则 `|uuu_(i=1)^n A_i|` `= 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, 2, cdots, n}`, `bar A_i = S - A_i`, `nnn_(j in O/) = S`, 上述等式取补集后, 可用更加紧凑的记号写成 `|nnn_(i=1)^n bar A_i|` `= sum_(C sube N) (-1)^|C| |nnn_(j in C) A_j|`.

归纳证明. `n = 1, 2` 的情形已经成立. 设 `n-1` 时命题成立, 下证 `|uuu_(i=1)^n A_i|` `= sum_(O/ != C sube N) (-1)^(|C|-1) |nnn_(j in C) A_j|`. 由引理, 左边 `= |(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_(O/ != C sube N-1) (-1)^(|C|-1) |nnn_(j in C) A_j| + |A_n|`
`+ sum_(O/ != C sube N-1) (-1)^|C| |nnn_(j in C) (A_j nn A_n)|`
`=` 右边.

记 `a_k` 为每 `k` 个集合的交集的基数之和, `b_k` 为那些恰好属于 `k` 个集合的元素的个数, `k = 1, cdots, n`. 于是 `a_k := sum_(C sube N, |C| = k) |nnn_(j in C) A_j|`,
`b_k := |uuu_(C sube N, |C| = k) nnn_(j in C) A_j| - |uuu_(C sube N, |C| = k+1) nnn_(j in C) A_j|`. `a_k` 中的一些元素被重复计算了, 事实上 `a_1 = (1;1) b_1 + (2;1) b_2 + cdots + (n;1) b_n`,
`a_2 = (2;2) b_2 + (3;2) b_3 + cdots + (n;2) b_n`,
`cdots`
`a_n = (n;n) b_n`. 利用组合恒等式 `sum_(k=0)^n (-1)^k (n;k) = 0`, 两边交错求和即得 `sum_(k=1)^n (-1)^(k-1) a_k = sum_(k=1)^n b_k`.

容斥原理还可用 Möbius 反演导出, 参见下节.

容斥原理 (对称情形) 在容斥原理中, 如果假设 `A_1, cdots, A_n` 中任意 `k` 个的交的基数都只和 `k` 有关, `k = 1, cdots, n`, 记 `S_0 := S`, `S_k := nnn_(i=1)^k A_i`, 则 `|nnn_(k=1)^n bar A_k| = sum_(k=0)^n (-1)^k (n;k) |S_k|`.

    错排问题 有 `n` 封信和 `n` 只对应的信封, 有黑暗中随意将每封信装进一个信封, 设恰好每封信都装错信封的装法有 `D_n` 种.
  1. 求 `D_n` 和 `lim_(n to oo) D_n//n!` (每封信都装错的概率的极限).
  2. 证明递推公式 `D_n = (n-1)(D_(n-1) + D_(n-2))`.
  3. 证明指数型生成函数 `sum_(n ge 0) D_n/n! x^n = -"e"^-x/(x-1)`.
    4. `n` 0 1 2 3 4 5 6 7 8 9
    `D_n` 1 0 1 2 9 44 265 1854 14833 133496

以集合 `A_k` 记所有使第 `k` 封信装进对的信封的安排, `S_k := nnn_(i=1)^k A_i`, 则 `|S_k| = (n-k)!`. 于是 `D_n = |nnn_(k=1)^n bar A_k|` `= sum_(k=0)^n (-1)^k (n;k) (n-k)!` `= sum_(k=0)^n (-1)^k (n!)/(k!)`. 所求极限为 `lim_(n to oo) sum_(k=0)^n (-1)^k 1/(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 to j` 表示第 `i` 封信被装入了第 `j` 个信封. 考虑任意一个 `n`-错排, `n gt 1`, 假设 `i to n to j`.
  1. 若 `i != j`, 将映射改为 `i to j`, 然后去掉第 `n` 封信, 就得到剩下 `n-1` 封信的一个错排; 反过来考虑 `n-1` 封信的一个错排, 任选 `1 le i le n-1`, 设 `i to j`, 加入第 `n` 封信, 将映射修改为 `i to n to j`, 就得到一个 `n`-错排, 满足 `i != j`.
  2. 若 `i = j`, 该错排实际交换了第 `i` 和第 `n` 封信. 将这两封信去掉就得到剩下 `n-2` 封信的一个错排; 反过来考虑 `n-2` 封信的一个错排, 加入两封信, 任选 `1 le i le n-1`, 让第 `n` 封信与第 `i` 封信对换. 如果 `i lt n-1`, 设原先 `k to i to j`, 将映射改为 `k to n-1 to j`, 就得到一个 `n`-错排, 满足 `i to n to i`.
    3. 以上两种情况, `i` 都有 `n-1` 种取法, 因此将它们相加, 乘以 `n-1` 就得到递推公式.

证明生成函数. 记 `f(x) = sum_(n ge 0) D_n/n! x^n`,
`f'(x) = sum_(n ge 0) D_(n+1)/n! x^n`,
`f''(x) = sum_(n ge 0) D_(n+2)/n! x^n`, 由递推公式 `D_(n+2) = (n+1)(D_n + D_(n+1))` 得到 `f'' = (x f)' + (x f')'`,
`f(0) = D_0 = 1`, `f'(0) = D_1 = 0`. 用 Wolfram 求解上述方程即可 (sympy.dsolve 只得到级数解).

错排可以用有向图表示, 其中每个连通分量都是一个圈.

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

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

长度为 `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` 条. 由容斥原理即得结论.
    3. 更详细的内容参见 oeis A038719.

*有限偏序集上的 Möbius 反演

[来自洛谷@Gorenstein]

本节讨论的是数论中经典 Möbius 反演在有限偏序集上的推广.

二元卷积与 Möbius 反演

有限偏序集上的二元函数及其卷积 设 `(X, le)` 为有限偏序集, `R_(le) = {(x, y): x le y}`. 记 `cc F(X)` 是全体二元函数 `f: R_(le) to RR` 的集合. 若 `(x, y) !in R_(le)`, 补充定义 `f(x, y) = 0`, 于是 `cc F(X) := { f: X xx X to RR: x le y "不成立" rArr f(x, y) = 0 }`. 例如, 下面两个函数都是 `cc F(X)` 的成员: `zeta(x, y) = {1, if x le y; 0, otherwise:}`,
`delta(x, y) = {1, if x = y; 0, otherwise:}`. 对任意 `f, g in cc F(X)`, 定义卷积如下: `(f ast g)(x, y) := sum_(z in X) f(x, z) g(z, y)` `= sum_(x le z le y) f(x, z) g(z, y)`. 当 `x le y` 不成立时, 上式右端为空和, 其等于零, 因此 `f ast g in cc F(X)`.

`cc F(X)` 的代数结构 `cc F(X)` 关于卷积运算构成含幺半群, 单位元是 `delta(x, y)`. 如果考虑函数自然的加法, 则 `cc F(X)` 成一环.

现考虑 `cc F(X)` 的单位群, 即全体乘法可逆元构成的群.

`f in cc F(X)` 可逆当且仅当 `AA x in X`, `f(x, x) != 0`. `f` 可逆时, 它的逆可以用下面的递归式计算: `g(x, y) := {f(y, y)^-1, if x = y; -f(y, y)^-1 sum_(x le z lt y) g(x, z) f(z, y), otherwise:}`

  1. 反设 `f` 可逆, 但 `EE x in X`, `f(x, x) = 0`, 则 `delta(x, x) = (f ast f^-1)(x, x)` `= f(x, x) f^-1(x, x)` `= 0`, 矛盾.
  2. 现在设 `AA x in X`, `f(x, x) != 0`. 定义 `g(x, y)` 如上, 则 `g in cc F(X)`, 且 `x = y` 时 `(g ast f)(x, y) = 1`; `x lt y` 时 `(g ast f)(x, y)`
    `= sum_(x le z lt y) g(x, z) f(z, y) + g(x, y) f(y, y)`
    `= sum_(x le z lt y) g(x, z) f(z, y) - sum_(x le z lt y) g(x, z) f(z, y)`
    `= 0`.     于是 `g ast f = delta`.
    Möbius 反演
  1. 设 `a, b in cc F(X)`. 若 `a ast b = delta`, 则对任意 `f, g: X to RR` 以下两式等价: `g(x) = sum_y a(x, y) f(y)`, `quad AA x in X`;
    `f(x) = sum_y b(x, y) g(y)`, `quad AA x in X`.     记 `X = {x_1, cdots, x_n}`, `a_(i j) := a(x_i, x_j)`, `b_(i j) := b(x_i, x_j)`, 则上式用矩阵写为 `(a_(i j)) = (b_(i j))^-1`.
  2. 由前一定理知道 `zeta(x, y)` 可逆, 记 `mu := zeta^-1`, 称为 Möbius 函数. 根据递归式, `mu(x, y) = { 1, if x = y; -sum_(x le z lt y) mu(x, z), otherwise :}`. 由 1. 知对任意 `f, g: X to RR` 以下两式等价: `g(x) = sum_(y le x) f(y)`, `quad AA x in X`;
    `f(x) = sum_(y le x) mu(y, x) g(y)`, `quad AA x in X`.
  1. 若 `g(y) = sum_z a(y, z) f(z)`, 则 `sum_y b(x, y) g(y)`
    `= sum_y b(x, y) sum_z a(y, z) f(z)`
    `= sum_z f(z) sum_y b(x, y) a(y, z)`
    `= sum_z f(z) delta(x, z)`
    `= f(x)`.     反之的证明类似.
  2. 由 1. 知以下两式等价: `g(x) = sum_y zeta(y, x) f(y)`, `quad AA x in X`;
    `f(x) = sum_y mu(y, x) g(y)`, `quad AA x in X`.     再由 `zeta, mu in cc F(X)` 即得结论.

经典 Möbius 反演

全序集的 Möbius 函数 设 `(X, le)` 是全序集, 其中 `X = {x_1, cdots, x_n}`, 且 `x_1 lt cdots lt x_n`. 由递归式 `mu(x_i, x_j) = { 1, if i = j; -sum_(k=i)^(j-1) mu(x_i, x_k), otherwise :}` 于是 `mu(x_i, x_j) = { 1, if j = i; -1, if j = i+1; 0, otherwise :}`

直积的 Möbius 函数 两个偏序集 `(X, le_X)`, `(Y, le_Y)` 的直积是偏序集 `(X xx Y, le)`, 其中 `(x_1, y_1) le (x_2, y_2)` `iff x_1 le_X x_2 and y_1 le_Y y_2`. 我们有: `mu((x_1, y_1), (x_2, y_2)) = mu_1(x_1, x_2) mu_2(y_1, y_2)`.

经典 Möbius 反演 正整数 `n` 的全体正因子按整除关系构成有限偏序集, 经典 Möbius 反演公式为 `g(n) = sum_(d | n) f(d)` `iff f(n) = sum_(d | n) mu(d, n) g(d)`. 下面具体计算 `mu(d, n)`.

  1. 先证 `d | n` 时, `mu(d, n) = mu(1, n//d)`, 即 `mu(d, k d) = mu(1, k)`, `quad AA k, d in ZZ^+`. `k = 1` 时显然成立. `k gt 1` 时假设等式对一切 `j lt k` 成立, 根据递归式有 `mu(d, k d)` `= -sum_(j | k, j != k) mu(d, j d)` `= -sum_(j | k, j != k) mu(1, j)` `= mu(1, k)`.
  2. 考虑素数幂 `p^a`, 根据全序集的 Möbius 函数, `mu(1, p^a) = { 1, if a = 0; -1, if a = 1; 0, otherwise :}`
  3. 根据唯一因子分解 `n = prod_(i=1)^r p_i^(a_i)` 和直积的 Möbius 函数, `mu(1, n) = prod_(i=1)^r mu(1, p_i^(a_i))` `= { 1, if n = 1; (-1)^r, if n = p_1 cdots p_r "是不同的素数之积"; 0, otherwise :}`
    4. 如果简记 `mu(n) = mu(1, n)`, 就得到经典的 Möbius 函数和经典 Möbius 反演 `g(n) = sum_(d | n) f(d)` `iff f(n) = sum_(d | n) mu(n//d) g(d)`.

子集反演

    子集反演与容斥原理
  1. 设 `S` 为有限集, 幂集 `P(S)` 按集合的包含关系构成有限偏序集, 相应的 Möbius 反演公式为 `g(X) = sum_(Y sube X) f(Y)` `iff f(X) = sum_(Y sube X) mu(Y, X) g(Y)`. 证明 `mu(Y, X) = (-1)^(|X|-|Y|)`.
  2. 运用子集反演公式证明容斥原理.
  1. 对 `n := |X|-|Y|` 作数学归纳. 显然 `mu(X, X) = 1`. `Y subne X` 时, 运用递归式, `mu(Y, X)` `= -sum_(Y sube Z subne X) mu(Y, Z)` `= -sum_(Y sube Z subne X) (-1)^(|Z|-|Y|)`
    `= -sum_(K subne X - Y) (-1)^|K|` `= -sum_(k=0)^(n-1) (n;k) (-1)^k` `= (-1)^n`.
  2. 设 `A_1, cdots, A_n` 是 `S` 的子集, `bar A_i := S - A_i`, `i = 1, cdots, n`. 令 `N = {1, cdots, n}`, 对 `AA X sube N` 定义 `f(X) := |nnn_(i in X) bar A_i nn nnn_(i !in X) A_i|`,
    `g(X) := sum_(Y sube X) f(X)` `= |nnn_(i !in X) A_i|`.     在子集反演公式中取 `X = N` 得到 `f(N) = sum_(Y sube N) (-1)^(n-|Y|) g(Y)`. 令 `C = N - Y` 有 `|nnn_(i in N) bar A_i|` `= sum_(C sube N) (-1)^|C| |nnn_(i in C) A_i|`.

二项式反演 在子集反演公式中, 若 `f, g` 的值只与集合大小有关, 而与具体集合的选择无关, 则得到: `g(n) = sum_(k=0)^n (n;k) f(k)` `iff f(n) = sum_(k=0)^n (-1)^(n-k) (n;k) g(k)`.

Möbius 变换 在子集反演公式中, 称 `g(X) = sum_(Y sube X) f(Y)` 为 `f` 的 Möbius 变换, `f` 为 `g` 的 Möbius 逆变换. 记作 `g = hat f`. 又定义集合卷积 `(f ast_uu g)(X) := sum_(A uu B = X) f(A) g(B)`. 则有公式 `widehat(f ast_uu g) = hat f hat g`. 此公式可类比于 `RR^n` 上函数的 Fourier 变换.

记 `h = f ast_uu g`, 直接计算 `hat h(X)` `= sum_(Y sube X) h(Y)`
`= sum_(Y sube X) sum_(A uu B = Y) f(A) g(B)`
`= sum_(A sube X) sum_(B sube X) f(A) g(B)`
`= {:hat f:}(X) {:hat g:}(X)`.