【组合数学】递推方程 ( 递推方程示例 1 | 列出递推方程 )

2023-03-28 18:28:06 浏览数 (1)

文章目录

  • 一、递推方程示例 1
  • 二、递推方程示例小结

一、递推方程示例 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 = cfrac{6^n 8^n}{2}

二、递推方程示例小结

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

该计数带参数

n

,

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

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

并且知道 初值 ,

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

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

编码 数学 系统

0 人点赞