问题及解答

只由三个字母 $a,b,c$ 组成的长度为 $n$ 的一些单词将在通信信道上传输, 传输中应满足条件:

    不得有两个 $a$ 连续出现在任一单词中.

确定通信信道允许传输的单词的个数.

换种表述方式,

信道中有一些单词在传输 $S=\{w_1,w_2,\ldots,w_m\}$. 其中每个单词(word) $w_i$ 的长度均为 $n$,  即形如

\[
w_i=z_{i_1}z_{i_2}\cdots z_{i_n},
\]

这里 $z_{i_j}\in\{a,b,c\}$, 并且要求 $z_{i_j}z_{i_{j+1}}\neq aa$, 对任意 $i,j$.

求 $|S|$.

记 $f(n)=|S|$.

例如: 当 $n=3$ 时, 单词形如 [x][x][x] ,  这里 x 可以取 a,b,c 之一, 因此总的情形有 $3^3=27$ 种. 但是要排除连续两个 $a$ 的情形. [a][a][x], [x][a][a],  这种类型的共有 2+2+1=5 种. 因此 $f(3)=27-5=22$.

易见, $f(2)=3^2-1=8$, $f(1)=3$.