似乎是一个比较简单的题目。

Problem

一个正交平面网格，只能向上/向右走，求从 (0, 0) 到 $(n, n)$ 期望与直线 $y = x$ 相交多少次。

Solution

答案为 $\frac{4^n}{ \binom{2n}{n} }$ 。

很容易得到表达式为 $\frac{\sum_{k = 0}^n { \binom{2k}{k} }{ \binom{2n - 2k}{n - k} }}{ \binom{2n}{n}}$ 。我们只需化简这个求和式即可。

第一种方法，看着式子很自然想到卷积，于是考虑母函数。$\binom{2k}{k}$ 的母函数为 $f(x) = \frac{1}{\sqrt{1 - 4x} }$ 。于是卷积为 $f^2(x) = \frac{1}{1 - 4x}$ ，展开后的第 $n$ 项为 $4^n$ 。

第二种方法，强力进行二项式处理。由于 $\binom{2k}{k} = \binom{-\frac{1}{2}}{k} (-4)^k$ 所以有

$$\sum_{k = 0}^n \binom{2k }{ k}\binom{2n - 2k }{ n - k} = \sum_{k = 0}^n {-\frac{1}{2} }{ k} \binom{-\frac{1}{2} }{ n - k} (-4)^n = (-4)^n \binom{-1 }{ n} = 4^n$$

如果像证明 Catalan 通项公式那样搞一个映射也是可以的吧……