Question

由 $10$ 个字母组成、且每个字母都是 A 或 B 的字符串共有 $2^{10} = 1024$ 个。求其中不含超过 $3$ 个连续相同字母的字符串个数。

There are $2^{10} = 1024$ possible $10$ -letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than $3$ adjacent letters that are identical.

答案

答案：548

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

难度评级：2890

解答：

条件说明每一段最长连续相同字母的长度至多为 $3$ 。令 $s_n$ 表示以 A 开头的有效 $n$ 位字符串个数；由对称性，答案为 $2s_{10}$ 。去掉第一段（长度为 $1$ 、 $2$ ，或 $3$ ）后，剩下的是一个以 B 开头的更短有效字符串，所以 $s_n = s_{n-1} + s_{n-2} + s_{n-3}.$

从 $s_1 = 1$ 、 $s_2 = 2$ 、 $s_3 = 4$ ，开始，序列依次为 $7, 13, 24, 44, 81, 149, 274$ ，所以 $s_{10} = 274$ 。

有效字符串数为 $2 \cdot 274 = 548$ 。

The condition says every maximal run of identical letters has length at most $3.$ Let $s_n$ count the valid strings of length $n$ whose first letter is A; by symmetry the answer is $2s_{10}.$ Removing the first run (of length $1,$ $2,$ or $3$ ) leaves a valid shorter string beginning with B, so $s_n = s_{n-1} + s_{n-2} + s_{n-3}.$

Starting from $s_1 = 1,$ $s_2 = 2,$ $s_3 = 4,$ the sequence runs $7, 13, 24, 44, 81, 149, 274,$ so $s_{10} = 274.$

The number of valid strings is $2 \cdot 274 = 548.$

2015 AIME II 第 12 题

答案：548

难度评级：2890

解答：

其他年份的第 12 题