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

韩曙亮

发布于 2023-03-28 18:28:06

1K0

发布于 2023-03-28 18:28:06

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、递推方程示例 1

编码系统使用

进制数字 , 对信息编码 ,

进制数字只能取值

0,1,2,3,4,5,6,7

只有当某个编码含有偶数个

时 , 该编码才是有效的 ,

求

位的编码中有效的编码个数 ?

分析 :

位长的编码 , 可以由

n-1

位长的编码 , 后面加上一位

进制数字构成 ;

对于每个

n-1

位长的编码 , 后面加上一位数字 , 使得最终的编码满足有效编码的要求 , 即含有偶数个

, 就可以得到一个有效的

位长的编码 ;

1 . 设

位长的有效编码个数是

a_n

个 ;

则有

n-1

位长的有效编码个数是

a_{n-1}

个 ;

现在考虑

位长的编码与

n-1

位长的编码之间的关联关系 ;

( 1 ) 偶数个

: 假定当前已经有一个

n-1

位长的

进制编码串 , 恰好含有偶数个

, 即该编码已经满足有效编码的要求 , 在加上一位数字 :

不可以加的数字 : 不能加

, 加了

之后 , 就会变成奇数个

, 成为无效编码 ;

可以加的数字 : 只能加

0,1,2,3,4,5,6

数字 , 这里有

种方式 ;

由一个

n-1

位长的 , 满足要求的编码 , 有

种方式生成一个

位长的编码 ;

( 2 ) 奇数个

: 假定当前已经有一个

n-1

位长的

进制编码串 , 恰好含有奇数个

, 即该编码不满足有效编码的要求 , 在加上一位数字 :

不可以加的数字 : 不能加

0,1,2,3,4,5,6

数字 , 加了以后 , 最终结果还是有奇数个

, 不满足有效编码的要求 ;

可以加的数字 : 只能加

, 加了

之后 , 就会变成偶数个

, 成为有效编码 ;

由一个

n-1

位长的 , 不满足要求的编码 , 有

种方式生成一个

位长的编码 ;

3 . 总个数

8^{n-1}

n-1

位长的编码的总数是

8^{n-1}

个 , 每个位置都有

种可能的选择 , 有

n-1

个位置 ;

又可以表述成 :

n-1

位长的包括 , 奇数个

, 偶数个

, 的编码总数是

8^{n-1}

编码中如果没有

, 是

个

, 算偶数个

;

4 .

n-1

位编码的有效个数

a_{n-1}

n-1

位中 , 偶数个

的个数 , 就是有效编码的个数 , 即上述假设的

“设

位长的有效编码个数是

a_n

个” , 则有

n-1

位长的有效编码个数是

a_{n-1}

个"

5 .

n-1

位编码的无效个数

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

n-1

位长的包括奇数个

, 偶数个

的编码总数是

8^{n-1}

n-1

位中 , 偶数个

的个数 , 就是有效编码的个数 , 即上述假设的

a_{n-1}

则

n-1

位中 , 奇数个

的个数 , 就是无效编码的个数 , 即上述总个数减去有效编码个数 , 结果是 :

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

6 . 分析第

项与

n-1

项之间的关系 , 即

位有效编码个数与

n-1

位有效编码个数 :

有效编码个数对应的添加方法数 :

n-1

位编码的有效个数

a_{n-1}

, 含有偶数个

, 每个有效编码 , 添加一位数字 , 组成

位有效编码 , 有

种对应的添加方式 , 即添加

0,1,2,3,4,5,6

数字 , 七种方式 ; 方法数是

7a_{n-1}

无效编码个数对应的添加方法数 :

n-1

位编码的无效个数

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

, 还有奇数个

, 每个无效编码 , 只能添加一个数字

, 组成

位有效编码 , 只有一种方法 ; 方法数是

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

因此这里可以写出

位编码的有效个数

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 . 初值讨论

如果只有

位编码 , 肯定不能是

, 这样就含有奇数个 (

个 )

, 是无效编码 ;

只能是

0,1,2,3,4,5,6

这

种 , 因此有

位编码时 , 有效编码个数是

个 ,

产生递推方程初值

a_1 = 7

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

递推方程 :

a_n

6a_{n-1}

8^{n-1}

初值 :

a_1 = 7

解上述递推方程的通项公式 :

a_n = \cfrac{6^n + 8^n}{2}

二、递推方程示例小结

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

该计数带参数

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

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

并且知道初值 ,

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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-21，如有侵权请联系 cloudcommunity@tencent.com 删除

编码

数学

系统

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编码

数学

系统

登录后参与评论

0 条评论

热度