当前课程知识点:组合数学 > 小乒乓球的组合之旅 > 多样的组合 > 不相邻组合
刚才呢我们给大家介绍了可重组合
其实组合还有各种不同的花样
比如说我们有时候排队的时候
我们要求 要求隔着去取数
那么这样的问题呢
我们称之为不相邻组合
它的定义是这样的
比如说我要从集合A中
A中包含有n个元素
我要取出r个位置不相邻的元素进行组合
所谓位置的不相邻
也就是说相邻的两个数j和j+1
我们不同同时取出来
这个问题该怎么解释呢
比如说我们举一个例子
我们现在呢一共有6个元素
其中我要取出3个
它的可行的不相邻组合有哪些呢
可以是1 3 5
可以是2 4 6
但是1 2 5就不行
因为1和2是相邻元素
不符合不相邻的约束
那么它的组合数等于多少呢
刚才我们进行可重组合的时候
有了一点经验
我们可以用序号来进行处理
那么在不相邻组合中
是不是也可以借鉴它的思想呢
比如说我们有这样一个不相邻的组合
1 3 5 7 9
它的序号是多少
第一位仍然是0
那么最后面那一位呢
这里因为是5个数字
所以最后一位的序号是4
我怎么把这样一个不相邻的约束
最终想要构造出来一个
不可重的组合与它相对应呢
我们知道不相邻意味着什么
不相邻意味着它们之间的序号总要累加至少1
那么它既然是累加至少1上去的
如果我把它减掉前面的累加值
是不是就可以构造出一个新的组合呢
我们来尝试一下
我们发现在1 3 5 7 9
这样一个不相邻组合中
我们每一位都减掉它对应的序号
这时候生成了一个什么新的序列呢
1 3 5 7 9
变成了1 2 3 4 5
似乎构造出来一个新的序列
而且在这个序列中
我们会发现
好像仍然是一个组合
而且我们想知道它是不是一个无重组合呢
那么回头我们看一下
在这样一个序列中
比如说我们更广泛的说
我们要从1,2一直到n个元素中
取出r个不相邻进行组合
它的组合数是多少呢
我们首先构造出这r个不相邻的组合
它们表示为b1,b2一直到br
它们的序号分别对应的是从0 1 2
一直到r-1
根据刚才的分析
我们希望用当前的数字减掉它对应的序号
因此呢
构造出一个新的序列
也就是b1 b2-1一直到最后
最后一个数字br应该减掉它的序号r-1
因此是br-(r-1)
这样一个新的序列
它有多少个呢
它这当然也是r个数字
由于我们原来的不相邻组合
因为是一个增序排列
因此b1从小到大在1到n之间
这时候我们就会想了
那下面新构造出来的这样一个序列
它最大能到多少呢
最大的一个数字无非就是br-r+1嘛
而br是小于等于n的
因此下面构造一个序列
它的最大值无非就是n-r+1
最小是多少呢
自然就是b1的最小值
也就是1了
那么这r个数字它的范围就应该是
从1一直到n-r+1
那么这c序列是不是各个元素都不相等呢
我们来看一下它们中间的c1和c2
我们会发现c1等于b1
c2等于b2-1
因为是不相邻
所以呢 b1和b2之间的差值肯定要大于等于2
因此呢
c1等于b1
c2等于b2-1
那自然c2也至少应该比c1大1了
依次类推 所以我们可以分析出来
对于c序列来说
c1应该小于c2 c2小于c3
一直到最后一个cr
因此通过上面的序号进行相减
我们构造出来了一个
从1一直到n-r+1这样范围内的
r个数字的增序序列
因此它实际上不相邻组合
就应该对应于C(n-r+1,r)
那么具体的证明我们同样通过一一对应的方法
类似的给出不相邻组合对应的序列
在此呢 我就不一一介绍了
组合实际上有很多不同的意义
下面呢 我们来看一道题
我们大家都知道
其实对于组合来说 一个很重要的关键
就在于它能够加强你的安全系数
无论你的密码再怎么复杂
无论你的锁再怎么精密
它都存在一个关键的问题
也就是说谁去开锁
如果仅仅把这个锁交给一个人的话
这一个人如果出现问题
你就会全盘皆失
为了增加它的安全系数
我们往往需要通过组合的方式
才能保证安全系数牢不可破
我们来看这样一个例子
有一个秘密机构
它有一个安全锁
但这个安全锁怎么才能牢靠呢
它呢 是设计了有一个系统
这个系统中它要求有若干把钥匙
同时使用才可以打开这个锁
那这些钥匙该多少个人拿呢
关键人物一共有7个人
当然你要7个人全部到场也并不牢靠啊
所以呢 他们说这7个人中
至少4个人到场就可以把锁打开了
这就存在一个问题
这么复杂的一个安全机制
我应该至少准备多少把不同的锁呢
而所有的钥匙又分布在不同的人手中
那么每个人至少应该配多少把钥匙呢
这个问题看似非常复杂
但是我们再仔细分析一下
它说了必须四个人到场
那意味着什么呢
意味着7个人中
任何3个人组合在一起
它都会缺一把钥匙
至少缺一把钥匙
那意味着他们缺的钥匙还都不能相同
如果缺的钥匙相同的话
那有可能任意的四个人他们就会缺共同的钥匙
这就意味着任意三个人的组合
他们都一一对应一把独特的钥匙
那我的钥匙应该至少多少个呢
那就意味着我应该至少保证7个人中
每3个都能产生一个新的钥匙
那至少要多少把不同的钥匙
就是应该等于C(7,3)
对于第二问
它说了
那我每个人至少要拿多少把钥匙呢
这时候我们再想
他每一个人都要负责任
任何的其他三个人都要缺钥匙
而这缺的钥匙你都应该有
那意味着对于每三个人
我都应该有一个钥匙和它匹配
那这三个人来自于哪儿呢
来自于除了我之外的剩下6个人
也就是说从6个人中任意的3个人的组合
它都应该有一把钥匙在我手里
那我应该拿多少把钥匙呢
实际上是不是应该就是C(6,3)
这么多把钥匙拿给我
我才能保证任何6个人中
任何3个人组合我都可以配的上他们的钥匙
所以这个问题虽然看着非常复杂
但实际上经过仔细的分析
就可以得到很简单的组合模型
刚才呢我们给大家介绍了
各种不同门类的排列和组合
我们现在可以总结一下
其实最最基本的排列和组合
就是我们常说的无重排列和无重组合
那么它对应的实际上就是放球模型
比如说我从n个球中取出r个
如果考虑顺序的话
那么它就称为是无重排列
如果不考虑顺序
实际上它对应的就是无重组合
那么数字上
排列数对应的就是P(n,r)
对应于组合数就是C(n,r)
那么另外我们还要考虑有些元素是可以重复的
我们就介绍了可重排列和可重组合
可重组合实际上就是我们说到的
哦 要用梨 要用橙子组成苹果篮
这个时候因为是组合
我们是不管顺序的
但是在这里面
是允许重复的
因此呢 我们知道
通过分析我们算出来
如果从n种水果中取出r个来拼果篮的话
它的方式就应该是C(n+r-1,r)
对于可重排列呢
可重排列实际上一个典型的案例
就是我们的英语单词
如果用n个字母组成r个字符串的话
这时候它的顺序是相关的
同时呢 它的数字 字符是可以重复的
对于从n个字母中选出r位串
那么每一位它有n种选择
一共要选r位
因此可重排列就是n的r次方
最后我们来总结了有一个叫做多重全排列的
排列方式
这时候我们要求有不同的类型
比如说有r1个a 有r2个b
最后呢 我们要构成一个n位串
这时候因为是排列
我们是说它的顺序是相关的
而且这时候因为它是考虑可以重复的
那么怎么来考虑这个问题呢
我们会发现对于可重的东西
我们希望把它的重复度去掉
而这里r1个a意味着a的重复度是r1的阶乘
r2个b意味着b的重复度是r2的阶乘
因此 n个元素的全排列除以r1的阶乘
再除以r2的阶乘
就是可重全排列的个数
在这里我们会发现有两个名词
可重和多重
有什么区别呢
我们仔细分析一下
会发现实际上可重意味着
你的元素个数是无穷的
资源是无限的
比如说水果 梨 苹果
你可以任意次地去拿
但是在多重中
它意味着元素个数是有限的
比如说r1个a r2个b
那么多重 可重实际上对应的是不同的问题
这里我们就介绍了各种各样的排列和组合
其实 对应于黑板上的排列组合
这只是凤毛麟角
希望大家呢
通过练习去体会一下排列组合的精妙
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(1)
--采访武永卫老师
-第一周作业
--作业说明
--H
--U
--G
--作业讨论区说明
-第一周演示程序
--程序讨论区说明
--幻方生成器
--换方计数
--屏幕解锁方案数
--欧拉路计数
--共享程序
-加减乘除来计数
--计数的基本法则
-排列还是组合
--排列还是组合
--小乒乓球的组合之旅--排列还是组合
-各种各样的排列
--圆排列和项链排列
--圆排列和项链排列--习题
--多重排列
--多重排列--练习
-多样的组合
--可重组合
--不相邻组合
--小乒乓球的组合之旅--多样的组合
-钟声里的全排列
--钟声里的全排列
--钟声里的全排列
--字典序法
--SJT算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验