第三次作业

1. (2.49.)

[!QUESTION]
求由 A, B, C, D 组成的允许重复的 $n$ 位排列中 AB 至少出现一次的排列数目.
由 A、B、C、D 组成的允许重复的 $n$ 位排列中，AB 至少出现一次的排列数目可通过补集思想与递推法求解。具体步骤如下：

1. 总排列数

总共有 $4^n$ 种允许重复的 $n$ 位排列.

2. 求不包含 AB 的排列数

设 $f(n)$ 为不包含连续子串 AB 的 $n$ 位排列数. 利用递推法分析:

• 递推关系
  将 $f(n)$ 分为两类: 以 A 结尾的排列数 $a(n)$ 和不以 A 结尾的排列数 $b(n)$, 即 $f(n)=a(n)+b(n)$.
  • 以 A 结尾: 前 $n-1$ 位可为任意不包含 AB 的排列, 故 $a(n)=f(n-1)$.
  • 不以 A 结尾: 第 $n$ 位可选 B、C、D, 共 3 种选择:
    • 若第 $n$ 位为 B, 则前 $n-1$ 位不能以 A 结尾, 数目为 $b(n-1)$.
    • 若为 C 或 D, 前 $n-1$ 位可为任意不包含 AB 的排列, 数目为 $2f(n-1)$.
  • 综上, $b(n)=b(n-1)+2f(n-1)$.
• 初始条件
  • $f(1)=4$ (单字符排列均合法).
  • $f(2)=15$ (总排列 $4^2=16$, 排除 AB 后剩余 15).
• 递推式化简
  联立 $a(n)$ 与 $b(n)$ 的递推关系，可得二阶线性递推:$$f(n)=4f(n-1)-f(n-2)(n\ge 3)$$

$$-\ast \ast \mathrm{通}\mathrm{项}\mathrm{公}\mathrm{式}\ast \ast \mathrm{解}\mathrm{特}\mathrm{征}\mathrm{方}\mathrm{程}\$r^2-4r+1=0\$，\mathrm{得}\mathrm{根}\$r=2\pm \sqrt{3}\$.\mathrm{通}\mathrm{项}\mathrm{为}:$$

f(n) = \frac{\sqrt{3}}{6} \left( (2+\sqrt{3})^{n+1} - (2-\sqrt{3})^{n+1} \right)

$$\text{\#\#\#\#\#\# 3. 至少出现一次 AB 的排列数 所求数目为总排列数减去不包含 **AB** 的排列数:}$$

4^n - f(n) = 4^n - \frac{(2+\sqrt{3})^{n+1} - (2-\sqrt{3})^{n+1}}{2\sqrt{3}}

$$\text{\#\#\# 2. (2.51.) > [!QUESTION] > 试求由 a, b, c 这 3 个字符组成的 \$n\$ 位符号串中不出现 aa 图像的符号串的数目. 设由 `a`、`b`、`c` 组成的 \$n\$ 位符号串中不出现 `aa` 的数目为 \$h(n)\$. 我们通过递推法进行分析: \#\#\#\#\#\# 1. 状态定义 - \$f(n)\$: 长度为 \$n\$ 且不以 `a` 结尾的符号串数目. - \$g(n)\$: 长度为 \$n\$ 且以 `a` 结尾的符号串数目. - 总数为 \$h(n) = f(n) + g(n)\$. \#\#\#\#\#\# 2. 递推关系 **不以 `a` 结尾**: 末尾可为 `b` 或 `c`, 共 2 种选择. 前 \$n - 1\$ 位可以是任意合法串:}$$

f(n) = 2 \cdot h(n - 1)

$$\ast \ast \mathrm{以}‘a‘\mathrm{结}\mathrm{尾}\ast \ast :\mathrm{前}\$n-1\$\mathrm{位}\mathrm{必}\mathrm{须}\mathrm{不}\mathrm{以}‘a‘\mathrm{结}\mathrm{尾}(\mathrm{即}\mathrm{属}\mathrm{于}\$f(n-1)\$),\mathrm{末}\mathrm{尾}\mathrm{选}‘a‘:$$

g(n) = f(n-1)

$$\mathrm{综}\mathrm{上},\mathrm{总}\mathrm{数}\mathrm{为}:$$

h(n) = f(n) + g(n) = 2 h(n - 1) + f(n - 1)

$$\mathrm{代}\mathrm{入}\$f(n-1)=2h(n-2)\$,\mathrm{得}:$$

h(n) = 2h(n-1) + 2 h(n - 2)

$$\text{\#\#\#\#\#\# 3. 初始条件 - \$h(1) = 3\$ (`a`, `b`, `c`) - \$h(2) = 8\$ (总 9 种, 排除 `aa`) \#\#\#\#\#\# 4. 通项公式 通过特征方程 \$r^2 - 2 r - 2 = 0\$ 得根 \$r = 1 pm sqrt{3}\$, 通解为:}$$

h(n) = \frac{(3 + 2\sqrt{3})(1+\sqrt{3})^n + (3 - 2\sqrt{3})(1-\sqrt{3})^n}{6}

$$\text{\#\#\# 3. (2.52.) > [!QUESTION] > 证明 \$mathop{C}(n, n) + mathop{C}(n + 1, n) + dots + mathop{C}(n + m, n) = mathop{C}(n + m + 1, m)\$. 考虑从 \$n + m + 1\$ 个元素中选取 \$n + 1\$ 个元素的组合数 \$mathop{C}(n + m + 1, n + 1)\$. 假设这些元素按顺序排列, 最后一个被选中的元素的位置为 \$n + k + 1\$, 其中 \$k\$ 的取值为 \$0 leqslant k leqslant m\$. 此时: - 最后一个元素的位置为 \$n + k + 1\$, 其左边有 \$n + k\$ 个元素. - 需要从这 \$n + k\$ 个元素中选取 \$n\$ 个元素, 组合数为 \$mathop{C}(n + k, n)\$. 当 \$k\$ 从 \$0\$ 取到 \$m\$ 时, 所有可能的选法总和为:}$$

\sum_{k = 0}^m \mathop{C}(n + k, n) = \mathop{C}(n, n) + \mathop{C}(n + 1, n) + \dots + \mathop{C}(n + m, n)

$$\text{而总选法数显然等于 \$mathop{C}(n + m + 1, n + 1) = mathop{C}(n + m + 1, m)\$, 因此等式成立. \#\#\# 4. (2.58.) > [!QUESTION] > 在河内塔中 A 柱上共有 1 到 \$n\$ 编号的 \$n\$ 个盘, 现在要将偶数编号与奇数编号的盘分别套在 B 柱和 C 柱上, 试问共要作多少盘次的转移, 规则不变. \#\#\#\#\#\# 1. 问题分析 每个盘子的目标柱由编号奇偶性决定. 移动过程中需遵循河内塔规则: 每次只能移动一个盘子, 且大盘不能叠在小盘上. 需递归分解问题. \#\#\#\#\#\# 2. 递推关系推导 - 对于最大的盘子 \$n\$ (若为偶数), 需将其移到 B 柱. 为此, 先将前 \$n - 1\$ 个盘子移至 C 柱 (普通河内塔步数 \$2^{n - 1} - 1\$ 次), 移动盘子 \$n\$ 到 B 柱 (1 次), 此时 \$n - 1\$ 号盘子已经在 C 柱. - 再将前 \$n - 3\$ 个盘子移至 A 柱 (普通河内塔步数 \$2^{n - 3} - 1\$ 次), 移动盘子 \$n - 2\$ 到 B 柱 (1 次). - 此时前 \$n - 3\$ 个盘子在 A 柱, 重复上述过程. - 同理, 若 \$n\$ 为奇数, 需将前 \$n - 1\$ 个盘子移至 B 柱, 再处理. - 递推式为:}$$

\begin{gather*}
f(n) = f(n - 3) + (2^{n - 1} - 1) + 1 + (2^{n - 3} - 1) + 1 \
f(n) - \frac{5}{7} \cdot 2^n = f(n - 2) - \frac{5}{7} \cdot 2^{n - 3}
\end{gather*}

$$\mathrm{结}\mathrm{合}\mathrm{边}\mathrm{界}\mathrm{条}\mathrm{件}\$f(0)=0,f(1)=1,f(2)=2\$,\mathrm{解}\mathrm{得}\mathrm{通}\mathrm{项}\mathrm{公}\mathrm{式}:$$

f(n) =
\begin{dcases}
\frac{5}{7} \cdot 2^n - \frac{5}{7}, & n \equiv 0 \pmod{3} \
\frac{5}{7} \cdot 2^n - \frac{3}{7}, & n \equiv 1 \pmod{3} \
\frac{5}{7} \cdot 2^n - \frac{6}{7}, & n \equiv 2 \pmod{3}
\end{dcases}

$$$$