一、递推方程示例 1

编码系统使用 $8$ 进制数字 , 对信息编码 , $8$ 进制数字只能取值 $0,1,2,3,4,5,6,7$ ,

只有当某个编码含有 偶数个 $7$ 时 , 该编码才是有效的 ,

求 $n$ 位的编码中有效的编码个数 ?

分析 :

$n$ 位长的编码 , 可以 由 $n-1$ 位长的编码 , 后面加上 一位 $8$ 进制数字 构成 ;

对于每个 $n-1$ 位长的编码 , 后面加上一位数字 , 使得最终的编码 满足 有效编码的要求 , 即含有偶数个 $7$ , 就可以得到一个有效的 $n$ 位长的编码 ;

1 . 设 $n$ 位长的有效编码个数是 $a_n$ 个 ;

则有 $n-1$ 位长的有效编码个数是 $a_{n-1}$ 个 ;

现在考虑 $n$ 位长的编码 与 $n-1$ 位长的编码之间的关联关系 ;

( 1 ) 偶数个 $7$ : 假定当前已经有一个 $n-1$ 位长的 $8$ 进制编码串 , 恰好含有偶数个 $7$ , 即该编码已经满足有效编码的要求 , 在加上一位数字 :

• 不可以加的数字 : 不能加 $7$ , 加了 $7$ 之后 , 就会变成 奇数个 $7$ , 成为无效编码 ;
• 可以加的数字 : 只能加 $0,1,2,3,4,5,6$ 数字 , 这里有 $7$ 种方式 ;

由一个 $n-1$ 位长的 , 满足要求的编码 , 有 $7$ 种方式生成一个 $n$ 位长的编码 ;

( 2 ) 奇数个 $7$ : 假定当前已经有一个 $n-1$ 位长的 $8$ 进制编码串 , 恰好含有奇数个 $7$ , 即该编码不满足有效编码的要求 , 在加上一位数字 :

• 不可以加的数字 : 不能加 $0,1,2,3,4,5,6$ 数字 , 加了以后 , 最终结果还是有奇数个 $7$ , 不满足有效编码的要求 ;
• 可以加的数字 : 只能加 $7$ , 加了 $7$ 之后 , 就会变成 偶数个 $7$ , 成为有效编码 ;

由一个 $n-1$ 位长的 , 不满足要求的编码 , 有 $1$ 种方式生成一个 $n$ 位长的编码 ;

3 . 总个数 $8^{n-1}$ :

$n-1$ 位长的编码的总数是 $8^{n-1}$ 个 , 每个位置都有 $8$ 种可能的选择 , 有 $n-1$ 个位置 ;

又可以表述成 : $n-1$ 位长的包括 , 奇数个 $7$ , 偶数个 $7$ , 的编码总数是 $8^{n-1}$

编码中如果没有 $7$ , 是 $0$ 个 $7$ , 算偶数个 $7$ ;

4 . $n-1$ 位编码的有效个数 $a_{n-1}$ :

$n-1$ 位中 , 偶数个 $7$ 的个数 , 就是有效编码的个数 , 即上述假设的

“设 $n$ 位长的有效编码个数是 $a_n$ 个” , 则有

"$n-1$ 位长的有效编码个数是 $a_{n-1}$ 个"

5 . $n-1$ 位编码的无效个数 $8^{n-1}-a_{n-1}$ :

$n-1$ 位长的包括 奇数个 $7$ , 偶数个 $7$ 的 编码总数是 $8^{n-1}$

$n-1$ 位中 , 偶数个 $7$ 的个数 , 就是 有效编码的个数 , 即上述假设的 $a_{n-1}$

则 $n-1$ 位中 , 奇数个 $7$ 的个数 , 就是无效编码的个数 , 即上述 总个数减去有效编码个数 , 结果是 :

$$8^{n-1}-a_{n-1}$$

6 . 分析第 $n$ 项与 $n-1$ 项之间的关系 , 即 $n$ 位有效编码个数 与 $n-1$ 位有效编码个数 :

有效编码个数对应的添加方法数 : $n-1$ 位编码的有效个数 $a_{n-1}$ , 含有偶数个 $7$ , 每个有效编码 , 添加一位数字 , 组成 $n$ 位有效编码 , 有 $7$ 种对应的添加方式 , 即添加 $0,1,2,3,4,5,6$ 数字 , 七种方式 ; 方法数是 $7a_{n-1}$

无效编码个数对应的添加方法数 : $n-1$ 位编码的无效个数 $8^{n-1}-a_{n-1}$ , 还有奇数个 $7$ , 每个无效编码 , 只能添加一个数字 $7$ , 组成 $n$ 位有效编码 , 只有一种方法 ; 方法数是 $8^{n-1}-a_{n-1}$

因此这里可以写出 $n$ 位编码的有效个数 $a_n$ 与 $n-1$ 位编码有效个数 $a_{n-1}$ 的关系 :

$a_n$ $=$ $7a_{n-1}$ $+$ $8^{n-1}-a_{n-1}$

化简后得到 :

$a_n$ $=$ $6a_{n-1}$ $+$ $8^{n-1}$

7 . 初值讨论

如果只有 $1$ 位编码 , 肯定不能是 $7$ , 这样就含有奇数个 ( $1$ 个 ) $7$ , 是无效编码 ;

只能是 $0,1,2,3,4,5,6$ 这 $7$ 种 , 因此有 $1$ 位编码时 , 有效编码个数是 $7$ 个 ,

产生 递推方程初值 $a_1=7$

8 . 最终得到的递推方程 :

递推方程 : $a_n$ $=$ $6a_{n-1}$ $+$ $8^{n-1}$

初值 : $a_1=7$

解上述递推方程的通项公式 : $a_n=\frac{6^n+8^n}{2}$

二、递推方程示例小结

该问题是一个具体的计数问题 , 上述问题并不是简单的计数 ,

该计数带参数 $n$ ,

这种类型的计数 , 可以看成一个 数列计数结果 ,

如果可以找到该数列 , 后项 , 前项 , 的依赖关系 ,

并且知道 初值 ,

就可以 解出该数列的通项公式 ,

该通项公式就恰好对应该计数结果 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/109210674