神秘 Trick
modfish_
·
·
个人记录
引入
\sum_{i=0}^n\binom{n}{i}i^2
考虑下式：
\begin{aligned}
&\sum_{i=0}^n\binom{n}{i}i^2\times p^i\\
=&p\frac{\partial}{\partial p}(p\frac{\partial}{\partial p}(\sum_{i=0}^n\binom{n}{i}p^i))\\
=&p\frac{\partial}{\partial p}(p\frac{\partial}{\partial p}((p+1)^n))\\
=&p\frac{\partial}{\partial p}(np(p+1)^{n-1})\\
=&n(p+1)^{n-1}p+n(n-1)(p+1)^{n-2}p^2\\
\end{aligned}
令 p=1：
n\times 2^{n-1}+n(n-1)\times 2^{n-2}=n(n+1)\times 2^{n-2}
令 p=-1：
0(n\ge 3)
关于 p=-1
咦，为什么对于 n\ge 3 都是 0？这也太神奇了。
不难找到组合意义：
有 2 个数 x,y\in [1,n]，要求 \forall k\in [1,n]，有 x=k 或 y=k。求方案数。
这多是一个愚蠢的问题，显然：
换一种算法：容斥，钦定其中 i 个数既不等于 x，也不等于 y 的方案：\displaystyle\binom{n}{i}\times (n-i)^2。
加上容斥系数，有：
\sum_{i=0}^n\binom{n}{i}(n-i)^i(-1)^i
换一种枚举方式，有：
(-1)^n\sum_{i=0}^n\binom{n}{i}i^2(-1)^i