UyHiP-2011-Aug

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

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 通项公式那样搞一个映射也是可以的吧……