当前课程知识点:组合数学 > 小乒乓球的组合之旅 > 各种各样的排列 > 多重排列
刚才呢我们给大家提到了
在排列中元素是可以重复的
那么有可能在某些情况下
元素的个数不仅可以重复
而且它的个数是有限的
那么一般我们称之为是多重排列
我们来看这样一道题目
请问乒乓 p i n g p a n g
这么多个字母一共有多少种不同的排列呢
大家一看这里面实际上是有重复的字母的
有多少个重复字母呢
其中p有两个 n有两个 g有两个
那么我们就会想这些重复元素
它的个数是有限的
我们现在并不知道对于多重排列该怎么做
但是我们知道对于所有元素不相同的
我们就会做了
那是不是可以把这种重复的元素
变成不一样呢
其实我们就会想 很简单啊
比如说我拿这个两个p分别标上是p1和p2
做出来相应的一个全排列之后
再除以它所有的标号冗余度
就可以得到原来可重排列的答案了
确实如此
我们把两个p分成了p1 p2
两个n n1 n2
两个g g1 g2
再加上一个i 一个a
这时候无非就是一个全排列嘛
那么它的全排列的个数相当于就是8的阶乘
它的重复度有多少呢
对于p来说
它的两个下标的重复度是2!
n 2! g 2!
因此我们就可以处理多重的全排列了
它的方案我们一般记为
Pn 中间用分号来表示
然后r1 r2分别表示各个元素的有限个数
这里面对于p i n g p a n g来说
它一共是8个元素进行全排列
其中前面有两个n 两个g 两个p
所以我们写成8 2 2 2 1 1
这样一个多重的全排列
我们通过计算就知道
如果打标号了之后
全排列个数是8的阶乘
再除以前面各个重复元素的下标冗余度
除以2! 2! 2!
最后就可以算出来多重全排列
就相当于是8!除以2!
2! 2!
就是p i n g p a n g这八个字母
所有的不同的全排列个数
刚才的思路其实呢
不仅仅能够处理英文字母的排列
它仍然可以处理各种各样的形式
尤其在多项式展开中
我们可以有一定的应用
对于一个更为普通的例子
我们给一个形式化的定义
什么叫做多重全排列呢
对于我们有若干个元素
r1个1 r2个2 一直到rt个t
这么多元素它们的个数之和为n
那么它的全排列就被记为P(n;r1,r2
一直到...,rt)
它的计算公式就等于n的全排列个数除以
r1阶乘 r2阶乘等等一直到rt阶乘
也就是相当于给可重的元素打上下标之后
用全排列个数除以下标方案数
那么我们用这个思路再来理解一下
二项式定理
二项式定理a+b的n次方
它的展开式中一个通项表示就是
a的k次方乘以b的n-k次方
那前面的系数有多少呢
它就相当于我有多少个可重排列
其中a有k个 b有n-k个
那自然我们可以给这k个a打上下标
给这n-k个b也打上下标
根据刚才的多重全排列
它的系数就应该等于n的阶乘全排列
除以a的标号方案数k阶乘
除以b的标号方案数n-k阶乘
我们从另外一个角度来理解了一下
二项式定理
那是不是可以展开一下
不仅仅是一两项的相加进行幂乘呢
也许我们可以除以a1加a2
一直加到at的n次方
它的通项系数会是多少呢
它的通项可以表示成a1的r1次方
乘以a2的r2次方
一直到at的rt次方
那同样这样的一个系数就表示
对应于有r1个a1 r2个a2
我们进行多重全排列能有多少不同的方案数
根据刚才的计算我们都知道
它们一共个数是n阶乘
所以是全排列n阶乘再除以r1的阶乘
r2的阶乘 一直到rt的阶乘
就可以算出来一个多项式的展开
它前面的系数等于什么
下面呢 我们来看一个游戏
这个游戏呢
大家在游戏厅其实都见过
那我们今天拿乒乓球来看一下
比如说我一共有6个轨道
分别对应着6个洞口
现在呢
我一共有9个乒乓球
这9个乒乓球分别编号是1到9
这9个乒乓球要进入不同的轨道
进入最终6个洞口
如果考虑它们先后顺序的话
请问它有多少种不同的入洞方案呢
这个问题看似非常复杂
好像排列数非常的多
那么我们来分析一下
其实这9个乒乓球根据顺序的不同
它被分到了6个区域内
6个区域该怎么表示更好呢
其实我们有一种非常有巧妙的方法
也就是隔板法
如果我们想要划分出6个区域
我们中间需要有5个隔板把整个空间
划分成6个区域
最终如果说9个球要分别
一 二 三 四的进入6个区域的话
就相当于
哎 已经有这6个区域了
我分别用一 二 三 四
填满它们中间的空间
也就像这样
这样的动画演示就告诉了我们
一个入洞的方案
那么这样的每一个解我们该如何表示呢
我们会发现实际上每一个隔板
它们都是一样的
剩下的其他的元素
它们分别是从1到9
似乎在这个排列里面
既有不可重的元素
也有可重的元素
刚才的多重全排列告诉我们了
如果有相同的元素
我们有一个有利的方法
就是给每一个相同元素打上下标
最后再除以它的标号方案数就好了
在这里也是一样啊
虽然这些门板都是一样的
我们可以给它打上不同的标号
同样我们就把问题转化成了一个全排列的问题
所以回头看
这道题其实求解起来非常方便
也就是对应于一开始是所有的元素
其中有5个门板再加上9个元素
一共14个不相同的元素
它们构成了一个14阶乘的一个全排列
而其中呢
我要除以门板对应的不同标号冗余度
也就是14的阶乘除以5个门板 5的阶乘
就是答案
这样做似乎告诉我们一个新的思路
对应于有一些分区域的题目
我们完全可以用隔板法得到一个
非常有效的方法
那有些同学说可能我对隔板法并不熟悉
有没有其他方法呢
那么同样我们也是把这几个区域划分出来
我们就看根据不同的步骤
我们能不能也得到同样的答案
对应于6个区域已经列在这里了
那么第一个球它有多少种区域呢
它要么落在1号区 要么落在6号区
它一共有6种可能性
当1号已经放好了之后
这时候我们再看
2号面对着这样的一个结果
还有多少种区域可以走呢
1在这里实际上也把一个区域划分成了
两个区域
所以对于2来说
它可以在1的前面
也可以在1的后面
那意味着在这样一个方案下
2 它的方案数多了
它一共有7种不同的位置可以走了
依次向下
对于1 2都列上去之后
3号的选择方法又多了一种
它有8个不同的区域
依此类推 直到最后一个球
最后一个球呢
它呢 一共有14种不同的区域可以落
因此它们的答案就是从一开始的6一直乘
累乘到14
也就相当于14的阶乘除以5的阶乘
和第一种方法的最终答案完全一致
所以我们会发现其实排列的概念
虽然非常简单
但是呢 有很多不同的技巧
比如说对于相邻和不相邻
我们需要用捆绑法来解决
而对于分区域的问题
我们通常会用隔板法来解决
当然并不只限于这两种不同的思路
希望大家呢
通过练习能够找到更多巧妙的方法
下面我们会通过组合的不同方式
给大家介绍多样的组合
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验