Question

考虑只由 $A$ 和 $B$ 组成的序列，并且它满足：每一段连续的 $A$ 的长度都是偶数，每一段连续的 $B$ 的长度都是奇数。这样的序列例子有 $AA$ 、 $B$ ，和 $AABAA$ ，而 $BBAB$ 不是这样的序列。长度为 $14$ 的这种序列有多少个？

Consider sequences that consist entirely of $A$ 's and $B$ 's and that have the property that every run of consecutive $A$ 's has even length, and every run of consecutive $B$ 's has odd length. Examples of such sequences are $AA,$ $B,$ and $AABAA,$ while $BBAB$ is not such a sequence. How many such sequences have length $14?$

答案

答案：172

知识点：递推计数有限制的排列奇偶性

难度评级：2920

解答：

设 $a_n$ 和 $b_n$ 分别表示长度为 $n$ 、以 $A$ 开头和以 $B$ 开头的合法序列数。以 $A$ 开头的序列先是 $AA$ ，后面接一个长度为 $n - 2$ 的任意合法序列（可以为空），所以 $a_{n+2} = a_n + b_n$ ，其中空序列计为一个。以 $B$ 开头的序列要么先是单个 $B$ ，后面接以 $A$ 开头的序列；要么先是 $BB$ ，后面接以 $B$ 开头的序列，所以 $b_{n+2} = a_{n+1} + b_n$ 。

从 $(a_1, b_1) = (0, 1)$ 和 $(a_2, b_2) = (1, 0)$ 开始， $n = 3, 4, \ldots, 14$ 时的 $(a_n, b_n)$ 依次为 $\begin{aligned} &(1, 2),\ (1, 1),\ (3, 3),\ \\ &(2, 4),\ (6, 5),\ (6, 10),\ \\ &(11, 11),\ (16, 21),\ (22, 27),\ \\ &(37, 43),\ (49, 64),\ (80, 92). \end{aligned}$

长度为 $14$ 的合法序列数为 $80 + 92 = 172$ 。

Let $a_n$ and $b_n$ count valid sequences of length $n$ beginning with $A$ and with $B.$ A sequence beginning with $A$ starts with $AA$ followed by any valid sequence of length $n - 2$ (possibly empty), so $a_{n+2} = a_n + b_n,$ where the empty sequence counts once. A sequence beginning with $B$ starts either with a single $B$ followed by a sequence beginning with $A,$ or with $BB$ followed by a sequence beginning with $B,$ so $b_{n+2} = a_{n+1} + b_n.$

Starting from $(a_1, b_1) = (0, 1)$ and $(a_2, b_2) = (1, 0),$ the pairs $(a_n, b_n)$ for $n = 3, 4, \ldots, 14$ are $\begin{aligned} &(1, 2),\ (1, 1),\ (3, 3),\ \\ &(2, 4),\ (6, 5),\ (6, 10),\ \\ &(11, 11),\ (16, 21),\ (22, 27),\ \\ &(37, 43),\ (49, 64),\ (80, 92). \end{aligned}$

The number of valid sequences of length $14$ is $80 + 92 = 172.$

2008 AIME I 第 11 题

答案：172

难度评级：2920

解答：

其他年份的第 11 题