给定整数 $n\geqslant 3$，称同时满足如下条件（i）与（ii）的有限数列为" $n-$ 数列"：
（i）该数列至少有 $3$ 项，且每一项的值属于集合 $\{1,2,\ldots,n\}$；
（ii）若该数列共 $m$ 项，依次为 $a_1 , a_2 , \ldots , a_m$，则对 $k=1,2,\ldots,m-2$，均有 $(a_{k+1}-a_{k})(a_{k+2}-a_{k})<0$．
求" $n$ -数列"的个数．
（i）该数列至少有 $3$ 项，且每一项的值属于集合 $\{1,2,\ldots,n\}$；
（ii）若该数列共 $m$ 项，依次为 $a_1 , a_2 , \ldots , a_m$，则对 $k=1,2,\ldots,m-2$，均有 $(a_{k+1}-a_{k})(a_{k+2}-a_{k})<0$．
求" $n$ -数列"的个数．
【难度】
【出处】
2016中国东南数学奥林匹克试题(高一)
【标注】
【答案】
略
【解析】
考虑任意一个 $m$ 项的" $n$ -数列" $S_0 : a_1 , a_2 , \ldots , a_m$，其中由条件（i）可知 $m\geqslant 3$．根据条件（ii），对 $k=1,2,\ldots,m-2$，有 $\min \left\{a_{k+1}, a_{k+2}\right\}<a_{k}<\max \left\{a_{k+1}, a_{k+2}\right\}$ ①
这表明 $a_k$ 不是 $S_0$ 中的最大项或最小项，因此 $a_m , a_{m-1}$ 必为 $S_0$ 中最大项与最小项的一个排列．
考虑 $S_0$ 去掉 $a_m$ 后的子数列 $S_1 : a_1 , a_2 , \ldots , a_{m-1}$．由于 $m-1\geqslant 2$，作类似的讨论可知，$a_{m-1} , a_{m-2}$ 是 $S_1$ 中最大项与最小项的一个排列．以此类推，最终可知对 $t=0,1,\ldots,m-2$ 时，$a_{m-t} , a_{m-t-1}$ 总是子数列 $S_t : a_1 , a_2 , \ldots , a_{m-t}$ 中最大项与最小项的一个排列．
因此有以下两种情况：
情况1：$a_m$ 是 $S_0$ 中的最大项．此时 $a_{m-1}$ 是 $S_0$ 中的最小项，
故也是 $S_1$ 中的最小项，从而 $a_{m-2}$ 只可能是 $S_1$ 中的最大项，以此类推得 $a_m > a_{m-2} > \ldots > a_1 > a_2 > a_4 > \cdots > a_{m-1}~~\text{(}m\text{为奇数)} $ ②
$a_m > a_{m-2} > \ldots > a_2 > a_1 > a_3 > \ldots > a_{m-1}~~\text{(}m\text{为偶数)}$ ③
情况2：$ a_m $ 是 $ S_0 $ 中的最小项．类似情况1得
$a_m < a_{m-2} < \ldots < a_1 < a_2 < a_4 < \ldots < a_{m-1}~~\text{(}m\text{为奇数)}$ ④
$a_m < a_{m-2} < \ldots < a_2 < a_1 < a_3 < \ldots < a_{m-1}~~\text{(}m\text{为偶数)}$ ⑤
反之，当 $ S_0 $ 满足 ②，③，④，⑤ 中的某个式子时，由 ① 可知 $ S_0 $ 必满足题目中的条件（ii）．
因此，集合 $ \{1,2,\ldots,n\} $ 的每个 $ m $（$ m\geqslant 3 $）元子集必对应两个" $ n $ -数列"，其中一个是满足 ② 或 ③ 的" $ n $ -数列"，另一个是满足 ④ 或 ⑤ 的" $ n $ -数列"．注意到 $ \{1,2,\ldots,n\} $ 的 $ m $（$ m\geqslant 3 $）元子集共有 $ 2^n - C_n^0 - C_n^1 - C_n^2 $ 个，故" $ n $ -数列"的个数为 $2\left(2^{n}-C_{n}^{0}-C_{n}^{1}-C_{n}^{2}\right)=2^{n+1}-n^{2}-n-2.$
这表明 $a_k$ 不是 $S_0$ 中的最大项或最小项，因此 $a_m , a_{m-1}$ 必为 $S_0$ 中最大项与最小项的一个排列．
考虑 $S_0$ 去掉 $a_m$ 后的子数列 $S_1 : a_1 , a_2 , \ldots , a_{m-1}$．由于 $m-1\geqslant 2$，作类似的讨论可知，$a_{m-1} , a_{m-2}$ 是 $S_1$ 中最大项与最小项的一个排列．以此类推，最终可知对 $t=0,1,\ldots,m-2$ 时，$a_{m-t} , a_{m-t-1}$ 总是子数列 $S_t : a_1 , a_2 , \ldots , a_{m-t}$ 中最大项与最小项的一个排列．
因此有以下两种情况：
情况1：$a_m$ 是 $S_0$ 中的最大项．此时 $a_{m-1}$ 是 $S_0$ 中的最小项，
故也是 $S_1$ 中的最小项，从而 $a_{m-2}$ 只可能是 $S_1$ 中的最大项，以此类推得 $a_m > a_{m-2} > \ldots > a_1 > a_2 > a_4 > \cdots > a_{m-1}~~\text{(}m\text{为奇数)} $ ②
$a_m > a_{m-2} > \ldots > a_2 > a_1 > a_3 > \ldots > a_{m-1}~~\text{(}m\text{为偶数)}$ ③
情况2：$ a_m $ 是 $ S_0 $ 中的最小项．类似情况1得
$a_m < a_{m-2} < \ldots < a_1 < a_2 < a_4 < \ldots < a_{m-1}~~\text{(}m\text{为奇数)}$ ④
$a_m < a_{m-2} < \ldots < a_2 < a_1 < a_3 < \ldots < a_{m-1}~~\text{(}m\text{为偶数)}$ ⑤
反之，当 $ S_0 $ 满足 ②，③，④，⑤ 中的某个式子时，由 ① 可知 $ S_0 $ 必满足题目中的条件（ii）．
因此，集合 $ \{1,2,\ldots,n\} $ 的每个 $ m $（$ m\geqslant 3 $）元子集必对应两个" $ n $ -数列"，其中一个是满足 ② 或 ③ 的" $ n $ -数列"，另一个是满足 ④ 或 ⑤ 的" $ n $ -数列"．注意到 $ \{1,2,\ldots,n\} $ 的 $ m $（$ m\geqslant 3 $）元子集共有 $ 2^n - C_n^0 - C_n^1 - C_n^2 $ 个，故" $ n $ -数列"的个数为 $2\left(2^{n}-C_{n}^{0}-C_{n}^{1}-C_{n}^{2}\right)=2^{n+1}-n^{2}-n-2.$
答案
解析
备注
