求证：

\[\sum_{i=0}^n\binom{2k}k\binom{2n-2k}{n-k}=4^n \]

首先，我们将 \(4^n\) 视为 \(2^{2n}\)，赋予其组合意义为长为 \(2n\) 的 \(0/1\) 串个数。

LHS 中组合数的结构指引我们将整个串分成两个部分，根据 \(\binom{2k}k\) 自然地想到第一部分可以是 \(0/1\) 个数相同的长度为 \(2k\) 的串，根据计数不重不漏的思想，再加一个限制，最后得到 最长的 \(0/1\) 个数相同的长度为 \(2k\) 的串，显然是 \(\binom{2k}k\)。

接下来是第二部分，根据第一部分的定义，第二部分的定义自然是任意一个前缀的 \(0/1\) 个数都不相同的长度为 \(2n-2k\) 的后缀，接下来就转化为证明满足任意前缀的 \(0/1\) 数量都不相同的长度为 \(2k\) 的串数为 \(\binom{2k}k\)。

先讲一种比较自然的双射解法。

不难想到将 \(0/1\) 串转化为向右 / 向上走，限制就转化为除起点外不能经过直线 \(y=x\)，这和 Catalan 数是相似的，所以用一样的方法计算就可以了。

还有一种更为高妙的解法：