当前课程知识点:组合数学 >  小乒乓球的组合之旅 >  各种各样的排列 >  多重排列

返回《组合数学》慕课在线视频课程列表

多重排列在线视频

多重排列

下一节:可重组合

返回《组合数学》慕课在线视频列表

多重排列课程教案、知识点、字幕

刚才呢我们给大家提到了

在排列中元素是可以重复的

那么有可能在某些情况下

元素的个数不仅可以重复

而且它的个数是有限的

那么一般我们称之为是多重排列

我们来看这样一道题目

请问乒乓 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算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

多重排列笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。