小札 Combinatorics 2

对于 Newton Expansion，式子本身的证明其实无甚可翻新的花样，但是题还是很有意思的。比如 codeforces - 1332E Height All the Same 这个。

首先给出几个性质：每个 cell 上的数字奇偶性才是需要关注的；如果 \(n\times m\) 为奇数，永远有解；如果 \(n\times m\) 为偶数，当 \(\sum\sum a_{i,j}\bmod2\) 为偶数时有解。应该都不需要证明。

奇数的答案不赘，我们可以写出偶数的答案式子：\(\displaystyle\sum_{i=0}^{\lfloor\frac{nm}{2}\rfloor}a^{2i}b^{nm-2i}\binom{nm}{2i}\)，\(a,b\) 分别是 \([l,r]\) 中偶 / 奇的数量。然后你注意这个式子长得很像 Newton Expansion 的形式，容易构造出答案为 \(\frac{(a+b)^{nm}+(a+b)^{nm}}{2}\)。

我们来看几个一般的组合恒等式。

1. \(\displaystyle\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}\)；
2. \(\displaystyle\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\)；
3. \(\displaystyle\sum_{k=0}^nk\binom{n}{k}=n2^{n-1}\)；
4. \(\displaystyle\sum_{k=0}^{n}k^2\binom{n}{k}=n(n+1)2^{n-2}\)；
5. \(\displaystyle\sum_{l=0}^n\binom{l}{k}=\binom{n+1}{k+1}\Longrightarrow\sum_{k=0}^n\binom{r+k}{k}=\binom{r+n+1}{r+1}=\binom{r+n+1}{n}\)；
6. \(\displaystyle\binom{n}{k}=(-1)^k\binom{k-n-1}{k}\)；
7. \(\displaystyle\sum_{k=0}^m(-1)^k\binom{n}{k}=(-1)^m\binom{n-1}{m}\)；
8. \(\displaystyle\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}\)；
9. \(\displaystyle\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}\)；（Vandermonde Convolution）

我们一个一个的来看。

1. 这个我无法找到除了代数解释以外的方法来诠释它的含义；
2. 经典的 Pascal's Formula，组合意义即钦定一个物品不选。适用场景很多，经常反过来用；
3. 带权变下项求和，考虑这样的组合意义：在 \(n\) 个物品中选出 \(k\) 个，再从这 \(k\) 个物品中选出一个组成 1-tuples 的方案数。对应到 r.h.s.，反过来钦定 1-tuples，然后计算系数。
4. 同理，组合意义即在 \(n\) 个物品中选出 \(k\) 个，再从这 \(k\) 个物品中可重地选出两个物品组成无序 2-tuples 的方案数。对应到 r.h.s.，反过来钦定 2-tuples，再考虑系数。需要分类讨论，当选出的物品不相同，为 \(n(n-1)2^{n-2}\)，当相同时，为 \(n^22^{n-1}\)，加在一起即 \(n(3n-1)2^{n-2}\)。
5. 变上项求和，考虑 \(n+1\) 个物品，每次钦定第 \(1,2,\dots,n+1\) 个不选，左右两式即相等，例题 codechef - CSEQ Count Sequences。
6. 这个式子我理解不能，但是运算有封闭性，再算一次可以变回去。
7. 用式 6，得 \(\displaystyle \sum_{k=0}^m(-1)^k\binom{n}{k}=\sum_{k=0}^m\binom{k-n-1}{k}=\sum_{k=0}^m\binom{k-n-1}{}\) ??。
8. 组合意义：\(\{a_{n}\}\) 的 \(r\)-subsets 的 \(k\)-subsets 数，r.h.s. 即在 \(\{a_n\}\) 中选出 \(k\)-subsets，再在 \({a_n}\setminus k\text{-subsets}\) 中选 \(r-k\)-subsets。
9. l.h.s. 和 r.h.s. 的意义都是 \(\{a_{m+n}\}\) 的 \(r\)-subsets 数。

来看一些题。

• 「acmhdu - 5794」A Simple Chess link：首先注意到这个走路的方式就是象棋马走日，然后做一个像 codeforces - 559C Gerald and Giant Chess 一样的 dp，有些细节需要注意。
• 「codeforces - 839D」Winter is here link：数数日门题。考虑反过来算每种 \(\gcd\) 的贡献次数。