ABC 被我轻松开贺了，贺完学习一下。

范德蒙德卷积公式：$\displaystyle\sum_{i=0}^k {n \choose i}{m\choose k-i}={n+m\choose k}$，组合意义显然。

一个简单变式是 $\displaystyle\sum_{i=0}^m {n \choose i}{m\choose i}={n+m\choose m}$。

推论是 $\displaystyle\sum_{u\ge0} {x \choose u}{y\choose u+1}={x+y\choose y-1}$。

考虑直接 ${y\choose u+1}={y-1\choose u+1}+{y-1\choose u}$，于是变为 $\displaystyle\sum_{u\ge0} {x \choose u}{y-1\choose u+1}+\displaystyle\sum_{u\ge0} {x \choose u}{y-1\choose u}$。

对于前项，令 $v=u+1$，变为 $\displaystyle\sum_{v\ge1} {x \choose v-1}{y-1\choose v}$。

等价于 $\displaystyle\sum_{v\ge1} ({x+1\choose v}-{x\choose v}){y-1\choose v}$

所以原式等于 $(\displaystyle\sum_{v\ge0}{x+1\choose v}{y-1\choose v})-(\displaystyle\sum_{v\ge0}{x\choose v}{y-1\choose v})+(\displaystyle\sum_{u\ge0}{x\choose u}{y-1\choose u})=\displaystyle\sum_{v\ge0}{x+1\choose v}{y-1\choose v}$。

由变式得 $x+y\choose y-1$。