三道裸题

T1.组合数问题[EasyVersion]

题目链接

二项式反演

令$g(n)=\binom{n}{l}$
$$ \begin{aligned} f(n)=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}g(k)\Leftrightarrow g(n)=\sum_{k=0}^{n}\binom{n}{k}f(k)=\binom{n}{l} \end{aligned} $$
显然，当且仅当$f(n)=\delta_{n,l}$时，等式成立。

差分

显然，我们要求的式子是某个函数$f(0)$的$n$阶差分：

$$ \Delta^n f(0)=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}f(k) $$
tips:多项式表示组合数

显然
$$ \begin{aligned} f(n)&=\binom{n}{l} =\sum_{k=0}^{l}\begin{bmatrix}l\\\k\end{bmatrix}\frac{1}{l!}n^k \end{aligned} $$

$$ [n^k]f(n)=\begin{bmatrix}l\\\k\end{bmatrix}\frac{1}{l!} $$
显然对于任意$n>l$,有$\Delta^n f(0)=0$

那么对于任意$n<l$，有
$$ \Delta^n f(0)=n![n^k]f(n)=0 $$
那么对于$n=l$，有
$$ \Delta^n f(0)=n![n^k]f(n)=1 $$
因此
$$ \Delta^n f(0)=\delta_{n,l} $$

T2.双色球

题目链接

分为两个步骤：

$1.$拿$k$个红球，贡献为$(-1)^k\binom{r}{k}$

$2.$拿$n-k$个蓝球，贡献为$\binom{r}{n-k}$

因此我们要求
$$ \sum_{k=0}^{n}(-1)^k\binom{r}{k}\binom{r}{n-k} $$

其显然是序列
$$ \langle a_n=(-1)^n\binom{r}{n}\rangle,\langle b_n=\binom{r}{n} \rangle $$
的卷积
分别构造其生成函数
$$ \begin{aligned} &A(x)=\sum_{k\ge0}a_kx^k = \sum_{k\ge0}\binom{r}{k}(-x)^k=(1-x)^r\\\ &B(x)=\sum_{k\ge0}b_kx^k=\sum_{k\ge0}\binom{r}{k}x^k=(1+x)^r\\\ \end{aligned} $$
其卷积

$$ $$

$$ A(x)B(x)=(1-x)^r(1+x)^r=(1-x^2)^r $$
$$ c_n=[x^n]A(x)B(x)=\[x^n\](1-x^2)^r $$
显然对于任意满足$2|n$的$n$有：

$$ c_n=(-1)^{n/2}\binom{r}{n/2} $$
对于$n$是奇数的情况，其和式值为$0$。

T3.组合数问题[HardVersion]

题目链接

类似于$T1$，我们使用差分解决。

令$f(k)=n\sum_{i=0}^{n}k^i$

显然
$$ ans=(-1)^n\sum_{k}\binom{n}{k}(-1)^kf(k)=\Delta^nf(0)\times(-1)^n=(-1)^nn!n $$