第五次作业

1. (2.63.)

[!QUESTION]
求 $n$ 位二进制数, 相邻两位不出现 11 的数的个数.

设 $f(n)$ 表示符合条件的 $n$ 位二进制数的个数.

初始条件:

• 当 $n=1$ 时, 可以是 0 或 1, 故 $f(1)=2$.
• 当 $n=2$ 时, 排除 11 后剩下 00, 01, 10, 故 $f(2)=3$.

递推关系:

对于 $n\ge 3$, 考虑最后一位:

• 若最后一位为 0, 前 $n-1$ 位可以是任意符合条件的数, 贡献 $f(n-1)$.
• 若最后一位为 1, 倒数第二位必须为 0, 前 $n-2$ 位可以是任意符合条件的数, 贡献 $f(n-2)$.

因此, 递推公式为:

$$f(n)=f(n-1)+f(n-2)$$

与斐波那契数列的关系:

通过观察初始值 $f(1)=2$, $f(2)=3$ 和递推关系, 可知 $f(n)$ 对应斐波那契数列的偏移项. 具体地:

$$f(n)=F(n+2)$$

其中 $F(k)$ 是斐波那契数列, 满足 $F(1)=1$, $F(2)=1$, $F(k)=F(k-1)+F(k-2)$.

最终答案:

所求的 $n$ 位二进制数的个数为斐波那契数列的第 $n+2$ 项, 即:

$$\boxed{{\displaystyle F(n+2)}}$$

2. (2.68.)

[!QUESTION]
在一个平面上画一个圆, 然后一条一条地画 $n$ 条与圆相交的直线. 当 $r$ 是大于 1 的奇数时, 第 $r$ 条直线只与前 $r-1$ 条直线之一在圆内相交. 当 $r$ 是偶数时, 第 $r$ 条直线与前 $r-1$ 条直线在圆内部相交. 如果无 3 条直线在园内共点, 这 $n$ 条直线把圆分割成多少个不重叠的部分?

当添加第 $r$ 条直线时, 这条直线在圆内的部分会被已有的交点分成多个段, 每个段对应分割一个新的区域. 因此, 新增的区域数目等于 $\text{交点数}+1$.

• 对于 $r=1$, 交点数目是 $0$, 所以贡献的是 $0+1=1$
• 当 $r$ 为奇数且 $r>1$ 时, 交点数目是 $1$, 所以贡献 $1+1=2$
• 当 $r$ 为偶数时, 交点数目是 $r-1$, 所以贡献 $(r-1)+1=r$

设 $n$ 条直线把圆分割成 $f(n)$ 个不重叠的部分, 则有递推关系:

$$f(n)=\{\begin{array}{ll}f(n-1)+n,& \text{even}\\ f(n-1)+2,& \text{odd},n>1\end{array}$$

初始条件为 $f(1)=2$. 递推关系的解为:

$$f(n)=\{\begin{array}{ll}\frac{1}{4}(n+1)(n+3),& \text{odd}\\ \frac{1}{4}n(n+6),& \text{even}\end{array}$$