Question

一名邮递员给榆树街东侧的十九户人家送信。邮递员注意到，同一天没有相邻的两户同时收到信，但同一天也从不会有连续超过两户没有收到信。共有多少种不同的送信模式？

A mail carrier delivers mail to the nineteen houses on the east side of Elm Street. The carrier notices that no two adjacent houses ever get mail on the same day, but that there are never more than two houses in a row that get no mail on the same day. How many different patterns of mail delivery are possible?

答案

答案：351

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

难度评级：2760

解答：

用 $1$ 表示某户收到信， $0$ 表示没有收到信。有效模式是长度为 $19$ 的二元串，其中没有连续两个 $1$ ，也没有连续三个 $0$ 。令 $A_n$ 、 $B_n$ 、 $C_n$ 分别表示长度为 $n$ 的有效串中，以 $1$ 结尾、恰好以一个 $0$ 结尾、恰好以两个 $0$ 结尾的数量。一个 $1$ 可以接在任一种以 $0$ 结尾的串后，一个单独的 $0$ 可以接在 $1$ 后，第二个 $0$ 可以接在一个 $0$ 后： $\begin{aligned} A_n &= B_{n-1} + C_{n-1}, \\ B_n &= A_{n-1}, \\ C_n &= B_{n-1}. \end{aligned}$

从 $A_1 = B_1 = 1$ 、 $C_1 = 0$ 开始迭代，总数 $A_n + B_n + C_n$ 依次为 $2$ ， $3$ ， $4$ ， $5$ ， $7$ ， $9$ ， $12$ ， $16$ ， $21$ ， $28$ ， $37$ ， $49$ ， $65$ ， $86$ ， $114$ ， $151$ ， $200$ ， $265$ ， $351$ 。

当 $n = 19$ 时，数量为 $351$ 。

Write $1$ for a house that gets mail and $0$ for one that does not. Valid patterns are binary strings of length $19$ with no two consecutive $1$ s and no three consecutive $0$ s. Let $A_n,$ $B_n,$ $C_n$ count valid length- $n$ strings ending in $1,$ in exactly one $0,$ and in exactly two $0$ s. A $1$ may follow either kind of $0$ -ending, a single $0$ may follow a $1,$ and a second $0$ may follow a single $0:$ $\begin{aligned} A_n &= B_{n-1} + C_{n-1}, \\ B_n &= A_{n-1}, \\ C_n &= B_{n-1}. \end{aligned}$

Starting from $A_1 = B_1 = 1,$ $C_1 = 0$ and iterating, the totals $A_n + B_n + C_n$ run $2,$ $3,$ $4,$ $5,$ $7,$ $9,$ $12,$ $16,$ $21,$ $28,$ $37,$ $49,$ $65,$ $86,$ $114,$ $151,$ $200,$ $265,$ $351.$

For $n = 19$ the count is $351.$

2001 AIME I 第 14 题

答案：351

难度评级：2760

解答：

其他年份的第 14 题