Frosti

二项式反演与容斥原理

Mon Dec 23 2024
5 minutes
大数学照亮世界 数学 组合数学
997 words

0.二项式反演#

鬼知道发现它的人怎么分析出来的

直接记结论吧。

fn=∑i=0nCnigi⇔gn=∑i=0n(−1)n−iCnifif _ n = \sum _ {i = 0} ^ n C _ n ^ i g _ i \Leftrightarrow g _ n = \sum _ {i = 0} ^ n (-1) ^ {n - i} C _ n ^ i f _ i

还有个更通用的结论

fn=∑k=nmCkngk⇔gn=∑k=nm(−1)k−nCknfkf _ n = \sum _ {k = n} ^ m C _ k ^ n g _ k \Leftrightarrow g _ n = \sum _ {k = n} ^ m (-1) ^ {k - n} C _ k ^ n f _ k
证明
gn=∑i=0n(−1)n−iCni∑j=0iCijgj=∑i=0n(−1)n−i∑j=0iCniCijgj=∑i=0n∑j=0i(−1)n−iCnjCn−in−jgj=∑j=0nCnjgj∑i=0n−j(−1)iCn−ji=∑j=0nCnjgj[n−j=0]\begin {aligned} g _ n &= \sum _ {i = 0} ^ n (-1) ^ {n - i} C _ n ^ i\sum _ {j = 0} ^ iC _ i ^ j g _ j &= \sum _ {i = 0} ^ n (-1) ^ {n - i} \sum _ {j = 0} ^ i C _ n ^ i C _ i ^ j g _ j &= \sum _ {i = 0} ^ n \sum _ {j = 0} ^ i (-1) ^ {n - i} C _ n ^ j C _ {n - i} ^ {n - j} g _ j\\ &= \sum _ {j = 0} ^ n C _ n ^ j g _ j\sum _ {i = 0} ^ {n - j} (-1) ^ i C _ {n - j} ^ i &= \sum _ {j = 0} ^ n C _ n ^ j g _ j [n - j = 0] \end {aligned}

所以，当且仅当 j=nj = n 时，Cnjgj[j=n]≠0=gnC _ n ^ j g _ j[j = n] \neq 0 = g _ n，得证。

1.容斥原理#

∣⋃i=1nSi∣=∑i=1n(−1)i+1∑∣T∣=i∣⋂S∈TS∣| \bigcup _ {i = 1} ^ n S _ i| = \sum _ {i = 1} ^ n (-1) ^ {i + 1} \sum _ {|T| = i}|\bigcap _ {S \in T} S|
证明

采用数学归纳法，当 n=1n=1 时，原式显然成立。当 n=2n = 2 时，可以通过 Venn 图得出 ∣S1∪S2∣=∣S1∣+∣S2∣+∣S1∩S2∣|S _ 1 \cup S _ 2| = |S _ 1| + |S _ 2| + |S _ 1 \cap S _ 2|

又因为 ∪\cup 和 ∩\cap 均有结合律，且互相有分配律。

所以有:

S4←S1∪S2,∣S4∣=∣S1∣+∣S2∣+∣S1∩S2∣S1∪S2∪S3=S4∪S3∣S1∪S2∪S3∣=∣S4∣+∣S3∣+∣S4∩S3∣=∣S1∣+∣S2∣−∣S1∩S2∣+∣(S1∩S3)∪(S2∩S2)∣=∣S1∣+∣S2∣+∣S3∣−∣S1∩S2∣−∣S2∩S3∣−∣S1∩S3∣+∣S1∩S2∩S3∣S _ 4 \gets S _ 1 \cup S _ 2,|S _ 4| = |S _ 1| + |S _ 2| + |S _ 1 \cap S _ 2| S _ 1 \cup S _ 2 \cup S _ 3 = S _ 4 \cup S _ 3 \begin{aligned} |S _ 1 \cup S _ 2 \cup S _ 3| &= |S _ 4| + |S _ 3| + |S _ 4 \cap S _ 3| &= |S _ 1| + |S _ 2| - |S _ 1 \cap S _ 2| + |(S _ 1 \cap S _ 3) \cup (S _ 2 \cap S _ 2)| &= |S _ 1| + |S _ 2| + |S _ 3| - |S _ 1 \cap S _ 2| - |S _ 2 \cap S _ 3| - |S _ 1 \cap S _ 3| &+ |S _ 1 \cap S _ 2 \cap S _ 3| \end{aligned}

所以，n=1,2,3n = 1,2,3 时，结论成立，进而可以归纳出∀n≥1\forall n \ge 1，结论均成立。

2.习题#

P10986 2023#

知识点：容斥原理

首先，可以想到把 20232023 看作一个数，这样，方案数就是 10n−4m×Cn−3mm10 ^ {n - 4m} \times C _ {n - 3m} ^ m，不是板中板吗？一交，10pts。

为什么呢？因为剩下随便乱填的数是 可以凑出 20232023 的，方案数可能会多。

然后，我们可以把这个“恰好”给改成“至少”，就非常好做。

设 g(x)g(x) 表示恰好有 xx 个 20232023 的方案数，f(x)f(x) 为至少有 xx 个 20232023 的方案数。则 f(x)=∑i=xn4Cixg(i)=Cn−3xx×10n−4xf(x) = \sum _ {i = x} ^ {\frac{n}{4}} C _ i ^ x g(i) = C _ {n - 3x} ^ x \times 10 ^ {n - 4x}，意思是从 ii 个中选择 xx 个，使这些为 20232023，并且最大只有 n4\frac{n}{4} 个。

然后这个就是上面的二项式反演的第二种形式，那直接丢反演，得到 g(x)=∑i=xn(−1)i−xCixf(i)g(x) = \sum _ {i = x} ^ n (-1) ^ {i - x} C _ i ^ x f(i)，则 g(m)=∑i=mn4(−1)i−mCimf(i)=∑i=mn4(−1)i−mCim10n−4mCn−3mmg(m) = \sum _ {i = m} ^ {\frac{n}{4}} (-1) ^ {i - m} C _ i ^ m f(i) = \sum _ {i = m} ^ {\frac{n}{4}} (-1) ^ {i - m} C _ i ^ m 10 ^ {n - 4m} C _ {n - 3m} ^ m，就 AC 了。

3.总结#

我觉得这个东西难就难在可以和 DP 深度融合，我最差的就是 DP，其实有些在 恰好 与 至少/之多 之间转换的可以用子集反演来做，但是这就不是这篇该讲的了。