2024 年四川预赛

解答

每一步满足

但不允许出现 $0$。下面按末项计数。

当长度为 $2m$ 时，对 $1\le j\le m$，末项为 $2j$ 或 $-(2j-1)$ 的数组数都等于

当长度为 $2m+1$ 时，对 $0\le j\le m$，末项为 $2j+1$ 的数组数等于

且当 $j\ge 1$ 时，末项为 $-2j$ 的数组数也等于 $d_{m,j}$。

下面补全归纳验证。约定下标超出范围时 $c_{m,j}=d_{m,j}=0$。由长度 $2m$ 的数组转移到长度 $2m+1$ 时，末项为 $2j+1$ 的数组分别来自末项 $2j$ 后作“加一”或末项 $-(2j+1)$ 后作“取相反数”；末项为 $-2j$ 的情形同理。因此相应计数均为

其中 $j=0$ 时只保留 $c_{m,1}$。由长度 $2m+1$ 转移到长度 $2m+2$ 时，末项为 $2j$ 或 $-(2j-1)$ 的计数均为

这两个等式正是帕斯卡公式；边界处导致 $0$ 的转移没有被计入。初始情形 $a_1=1$ 与（2）的 $m=0$ 一致，故（1）、（2）对所有 $m$ 成立。

若 $n=2m$，由（1）望远镜求和得总数

若 $n=2m+1$，由（2）得总数

两种情形合并为