计数问题

用户头像 发布于 10 小时前 17 次阅读 OI

计数问题+计数问题2

一些公式

吸收/提取恒等式：i⋅(i−1j−1)=j⋅(ji)i \cdot \binom{i-1}{j-1} = j \cdot \binom{j}{i}

上指标反转：(rk)=(−1)k(k−r−1k)\binom{r}{k} = (-1)^k \binom{k-r-1}{k}

范德蒙德卷积公式：∑k(rm+k)(sn−k)=(r+sm+n)\sum_k \binom{r}{m+k} \binom{s}{n-k} = \binom{r+s}{m+n}

上指标卷积公式：∑k=0n(ka)(n−kb)=(n+1a+b+1)\sum_{k=0}^n \binom{k}{a} \binom{n-k}{b} = \binom{n+1}{a+b+1}