记录一些常见代数恒等式。
-
\[\sum_{i=1}^n [\gcd(i,n)=1]i=\dfrac{\varphi(n)\times n}{2} \]
左边的含义就是 \(n\) 以内与 \(n\) 互质的数的和，考虑这样一个结论：\(\gcd(a,b)=1 \iff \gcd(a,a-b)=1\)。所以 \(n\) 以内与 \(n\) 互质的数可以两两合成一个 \(n\)，于是和就是右边的式子了。
-
（库默尔定理）设 \(n,m\) 为正整数，\(p\) 为某个质数，则 \(\dbinom{n+m}{n}\) 所含 \(p\) 的幂次等于 \(n+m\) 在 \(p\) 进制下的进位次数。
首先一个经典的结论是阶乘所含质数的个数 \(V_p(n!)=\sum\limits_{i=1}^{\infty} [\frac{n}{p^i}]\)。那么组合数所含质数个数就是 \(V_p((n+m)!)-V_p(n!)-V_p(m!)\)，写出来的话就是 \(\sum\limits_{i=1}^{\infty} [\frac{n+m}{p^i}]-[\frac{n}{p^i}]-[\frac{m}{p^i}]\)，而如果我们放到 \(p\) 进制下去看后面的式子，会发现这代表把每个数字后面的 \(i\) 位去掉，那么如果存在 \(i\to i+1\) 的进位，作差之后式子的值就是 \(1\)。所以这个式子的和就是进位次数。
- 推论：
\[\binom{n}{m} \bmod 2 =[m\subseteq n] \] 其中 \([m\subseteq n]\) 表示 \(m\) 的二进制表示是 \(n\) 的子集。
-
\[\sum_{j=k}^i \binom{i}{j} {{j}\brace{k}}={{i+1}\brace {k+1}} \]
考虑组合意义，左边相当于从 \(i\) 个元素中选出 \(j\) 个，放入 \(k\) 个非空集合的方案数。考虑新建一个垃圾桶放入剩下没有选出的元素，那么就相当于将 \(i\) 个元素放入 \(k+1\) 个集合的方案数，不过垃圾桶可能为空，所以我们再加上一个占位的元素即可。所以答案就是 \({i+1}\brace k+1\)。
-
\[\begin{aligned} &\sum_{i=0}^n \binom{n}{i}=2^n\\&\sum_{i=0}^n i\times \binom{n}{i}=n2^{n-1}\\&\sum_{i=0}^n i^2\times \binom{n}{i}=n(n+1)2^{n-2}\\ \end{aligned} \]
证明是比较简单的，因为总可以把 \(k+1\) 次的情况拆出一个 \(m\) 然后变成 \(1\sim k\) 次的情况求解。
-
范德蒙德卷积：
\[\sum_{i=0}^n \binom{p}{i}\binom{q}{n-i}=\binom{p+q}n \]\[\sum_{i=0}^n \binom{i}{p}\binom{n-i}{q}=\binom{n+1}{p+q+1} \]考虑组合意义即可。
-
\[\sum_{i=n}^m \binom{m}{i} (-1)^{i-n}=\binom{m-1}{n-1} \]
给前面的和式补一个 \(-\binom{m-1}{n-1}\)，然后用组合数递推公式可以不断合并成 \(0\)，所以自然等于 \(\binom{m-1}{n-1}\)。
-
\[\sum_{i=1}^n d(i)=\sum_{i=1}^n \left\lfloor\dfrac ni \right\rfloor \]
把每个函数值拆成每个因子的贡献即可。