三道裸题
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
三道题都写出来了
打表万岁但是题解的证明真的一点都看不懂,wtcl