2023 互测 R2T1 序列的线性做法

发布时间 2023-11-20 10:51:48作者: yyyyxh

把原题做法 GF 的系数进行 OEIS,发现那个三角形就是 Catalan 数的 GF 复合上一个 \(xy(1-x)\) 的形式。

更为奇妙的是,OEIS 下面竟然给出了一个通项公式,\(T(n,k)=(-1)^{n-k}{k\choose n-k}C_k\),其中 \(C\) 是 Catalan 数列。

代入原题的式子,发现答案竟然就是:

\[\sum_{i=0}^n (-1)^{n-i} {i\choose n-i} {m+i\choose i} C_i \]

为什么这样呢?小编也不知道。