具有下列条件的 $n$ 位十进制数称为“$n$ 位和谐数”:
① 首位为 $1$;
② 不含 $1,2,3$ 外的其他数字;
③ 每个数字都至少和一个奇偶性相同的数字相邻.
则“$10$ 位和谐数”的个数为
【难度】
【出处】
【标注】
  • 方法
    >
    思考方式
    >
    递推与递归
  • 题型
    >
    组合数学
    >
    组合计数
【答案】
$2014$
【解析】
满足条件 ②③ 且前两位为 $11,13,31,33$ 的 $n$($n\geqslant 2$)位十进制数个数相同,记为 $a_n$;满足条件 ②③ 且前两位为 $22$ 的 $n$ 位十进制数的个数记为 $b_n$,则所求的“$10$ 位和谐数”的个数为 $2a_{10}$.
以 $11$ 开头的 $n$ 位“和谐数”,第三位可能为 $1,3,2$,其中第三位为 $1$,$3$ 的和谐数各有 $a_{n-1}$ 个;第三位为 $2$ 的和谐数第四位仍然为 $2$,共有 $b_{n-2}$ 个,所以有 $a_n=2a_{n-1}+b_{n-2}$;
再考虑以 $22$ 开头的 $n$ 位“和谐数”,第三位可能为 $1,3,2$,其中第三位为 $1,3$ 时第四位可以为 $1,3$,共有 $4a_{n-2}$ 个;第三位为 $2$ 时,共有 $b_{n-1}$ 个,于是有 $b_n=4a_{n-2}+b_{n-1}$.
根据题意,有 $a_2=b_2=1$,$a_3=2$,$b_3=1$,且有\[\begin{cases} a_n=2a_{n-1}+b_{n-2},\\ b_n=4a_{n-2}+b_{n-1},\end{cases}\]因此\[\begin{array}{c|ccccccccc}\hline
n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
a_n & 1 & 2 & 5 & 11 & 27 & 67 & 167 & 411 & 1007 \\ \hline
b_n & 1 & 1 & 5 & 13 & 33 & 77 & 185 & 453 & 1121 \\ \hline
\end{array}\]从而 $2a_{10}=2014$ 为所求.
题目 答案 解析 备注
0.107850s