学长の问题之4

· · 个人记录

Description：

我们考虑这样一个方格表（仅展示前几个格子）

让某个格子内的数值等于在这个格子左和上的所有格子内的数的和，(0,0)位置设置为1。比如，在(2,2)中，26=1+1+2+1+3+8+2+8。

然后拿过数竞省一 差点进省队吊打CMO狂虐TST爆切IMO的 fxb学长问怎么求(m,n)位置的数的通项公式。

Solution

由于这是学长拷问我们的一道题，所以不可能告诉我们答案滴，所以以下纯属自己瞎yy，如有错误，那很正常。

记在(m,n)的数为a_{m,n}，容易发现a_{0,n}=2^{n-1}，经过数竞的奇技淫巧操作后也容易发现a_{1,n}=(n+2)2^{n-1}，然后我们就不会了，就寄掉了。

然而数竞中的奇技淫巧实在是太多了。

一个显而易见的递推式:

a_{m,n}=2a_{m-1,n}+2a_{m,n-1}-2a_{m-1,n-1}

然后从行方向考虑行通项（列通项同理）

设a_{m,0},a_{m,1},a_{m,2},a_{m,3}……为数列\{x_n\}

a_{m+1,0},a_{m+1,1},a_{m+1,2},a_{m+1,3}……$为数列$\{y_n\}

设\{x_n\}的生成函数为f(x)，\{y_n\}的生成函数为g(x)

由递推式a_{m,n}=2a_{m-1,n}+2a_{m,n-1}-2a_{m-1,n-1}也即y_n=2x_n+2y_{n-1}-2x_{n-1}以及生成函数基本操作，得到

2xg(x)+2(xf(x)-f(x))=g(x)

也即

g(x)=2\frac{1-x}{1-2x}f(x)

注意到第1行的生成函数为

\frac{1-x}{(1-2x)^2}

所以第m行的生成函数为

\frac{2^{m-1}(1-x)^m}{(1-2x)^{m+1}}

展开

2^{m-1}\frac{(1-x)^m}{(1-2x)^{m+1}}=2^{m-1}[\sum\limits^m_{k=0}C_m^k(-x)^k][\sum\limits^\infty_{k=0}C^k_{m+k}2^kx^k]

我们知道，这时a_{m,n}就是这个生成函数中x^n的系数啦，也即

a_{m,n}=2^{m-1}\sum\limits^n_{k=0}(-1)^kC_m^kC^m_{m+n-k}

好吧我想这个柿子不用化简了吧，虽然应该是能化简的