中山诗题
lkjzyd20
·
·
题解
中山诗题
求
\begin{aligned}
\cfrac{1}{2^{n+m}}\sum^{n}_{a=0}\sum^{m}_{b=0}\sum^{a+b}_{i=0}2i\dbinom{a}{i}\dbinom{b}{i}
\end{aligned}
我们提取出 2^{-(n+m-1)}，根据 oi-wiki 二项式推论第十条则有
\begin{aligned}
\sum^{n}_{a=0}\sum^{m}_{b=0}\sum^{a+b}_{i=0}i\dbinom{a}{i}\dbinom{b}{i}
&=\sum^{n}_{a=0}\sum^{m}_{b=0}\sum^{\min(a,b)}_{i=1}i\dbinom{a}{i}\dbinom{b}{i}\\
&=\sum^{\min(n,m)}_{i=1}i \left( \sum^{n}_{a=0}\dbinom{a}{i}\right)\left(\sum^{m}_{b=0}\dbinom{b}{i}\right)
\\
&=\sum^{n}_{i=1}i \dbinom{n+1}{i+1}\dbinom{m+1}{i+1}
\end{aligned}
我们令 j=i+1,i=j-1，则有
\begin{aligned}
\sum^{n}_{i=1}i \dbinom{n+1}{i+1}\dbinom{m+1}{i+1}
&=\sum^{n+1}_{j=2}(j-1) \dbinom{n+1}{j}\dbinom{m+1}{j}\\
&=\sum^{n+1}_{j=0}(j-1) \dbinom{n+1}{j}\dbinom{m+1}{j}+1\\
&=\sum^{n+1}_{j=1}j \dbinom{n+1}{j}\dbinom{m+1}{j}-\sum^{n+1}_{j=0}\dbinom{n+1}{j}\dbinom{m+1}{j}+1\\
\end{aligned}
根据 oi-wiki 范德蒙德卷积第四条，和 oi-wiki 二项式推论第三条，
\begin{aligned}
\sum^{n+1}_{j=0}\dbinom{n+1}{j}\dbinom{m+1}{j}
&=\dbinom{n+m+2}{n+1}\\
&=\dbinom{n+m+1}{n+1}+\dbinom{n+m+1}{n}
\end{aligned}
根据 oi-wiki 二项式推论第二条，我们有
\begin{aligned}
j \dbinom{n+1}{j}=(n+1) \dbinom{n}{j-1}
\end{aligned}
令 k=j-1,j=k+1，和 oi-wiki 范德蒙德卷积第四条
\begin{aligned}
\sum^{n+1}_{j=1}j \dbinom{n+1}{j}\dbinom{m+1}{j}
&=(n+1)\sum^{n+1}_{j=1}\dbinom{n}{j-1}\dbinom{m+1}{j}\\
&=(n+1)\sum^{n}_{k=0}\dbinom{n}{k}\dbinom{m+1}{k+1}\\
&=(n+1)\dbinom{n+m+1}{n+1}
\end{aligned}
则
\begin{aligned}
Ans&=
(n+1)\dbinom{n+m+1}{n+1}-\left(\dbinom{n+m+1}{n+1}+\dbinom{n+m+1}{n}\right)+1\\
&=n\dbinom{n+m+1}{n}-\dbinom{n+m+1}{n}+1
\end{aligned}