2010 年河北预赛 · 第 10 题

解答

设所求为 $c_n$。当 $n=1$ 时 $c_1=1$。对 $n\ge 2$，最后一项大于或小于之前全部项，故必为 $n$ 或一。删去它并将剩余数按大小标准化，得到一个长度 $n-1$ 的合法排列。反之，任一这样的短排列都可在末尾添上新的最小值或最大值，唯一得到两种合法长排列。因此 $c_n=2c_{n-1}$，所以