对于这种网格图的操作,因为是加法操作,所以可以有结合律和交换律,也就是说操作顺序是无关紧要的。
所以从上到下,从左到右考虑所有操作。
对于第一个格子的\(1\),它一定要被减去1次,而且只能被减去1次,因为只有在它格子上操作才能影响到它,它不可能被其他格子的操作加上1。
此时第一个格子的操作考虑完了,考虑第二个格子,同样,它有且仅有一次操作,因为只有第一个格子能影响到它,但是第一个格子已经考虑完了。
……
然后会发现是下面的矩阵求和,每一行有\(a_i\)项。
\[\begin{matrix}
1 & 1 & 1 & 1 & 1 & 1 \\
1 & 2 & 3 & 4 & 5 & 6 \\
1 & 3 & 6 & 10 & 15 & 21 \\
1 & 4 & 10 & 20 & 35 & 56 \\
\end{matrix}
\]
会发现有递推式\(f_{i,j}=f_{i-1,j}+f_{i,j-1}\)。
这就想到组合数\(\binom{m}{n}=\binom{m-1}{n-1}+\binom{m}{n-1}\)。
让后你就发现这就是杨辉三角。
具体来说,矩阵是
\[\begin{matrix}
\binom{0}{0} & \binom{1}{1} & \binom{2}{2} & \binom{3}{3} \\
\binom{0}{1} & \binom{1}{2} & \binom{2}{3} \\
\binom{0}{2} & \binom{1}{3} \\
\binom{0}{3} \\
\end{matrix}
\]
\(0\le x \le n+1,0\le y\le a_x-1,f_{x,y}=\binom{y}{x+y}\)。
这个时候化简式子一般都是把某些常数换成合适的形式,然后用递推式化简。
因为递推式的下面的数一定要相同,所以这样化简:
\(\binom{0}{x}+\binom{1}{x+1}+\binom{2}{x+2}+...=\binom{0}{x+1}+\binom{1}{x+1}+...=\binom{1}{x+2}+...=\binom{a_x-1}{x+a_x}\)。
然后就做完了。