当前位置：文档之家 › 组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列

组合数学课件--第三章第二节 棋盘多项式和有限制条件的排列

  • 格式：ppt
  • 大小：430.50 KB
  • 文档页数：40

下载文档原格式

  / 40

合集下载

排列、组合、二项式定理精选教学PPT课件

排列、组合、二项式定理精选教学PPT课件

当我们爱自己的孩子的时候，可曾想过，我们把爱孩子的十分之一去爱母亲，她就足矣，往往这一点也做不到，说句心里话，我们欠母亲的无法补偿，更无法用语言表达。 我有这两位母亲，虽然我的人生很不幸，但我有她们给我的无私的爱，我永远是幸福的，她们对我的爱我永存心里。在美国西雅图的一所著名教堂里，有一位德高望重的牧师――戴尔·泰勒。有一天，他向教会学校一个班的学生们先讲了下面这个故事。 那年冬天，猎人带着猎狗去打猎。猎人一枪击中了一只兔子的后腿，受伤的兔子拼命地逃生，猎狗在其后穷追不舍。可是追了一阵子，兔子跑得越来越远了。猎狗知道实在是追不上了，只好悻悻地回到猎人身边。猎人气急败坏地说：“你真没用，连一只受伤的兔子都追不
数有多少？
5×5=25
练习2
1.某段铁路上有12个车站，共需准备多少种普通客票？
P122
2.某段铁路上有12个车站，问有多少种不同的票价？
C122
3.用3，5，7，9四个数字，一共可组成多少个没有重 复数字的正整数
P41 P42 P43 P44
练习3
1.在(1+x)10的展开式中，二项式系数最大为 C150 ；
名称
排列
组合
一个~ ~~数
从n个不同元素中取出m个元 素，按一定的顺序排成一列
所有排列的个数
从n个不同元素中取出m个元 素，把它并成一组
所有组合的个数
符号
种数 公式 关系
性质
Pnm
C
m n
Pnm
Pnm
n(n 1) (n m
n! (n m)! Pnn n!

1)
0!
1
排列、组合、二项式定理
知识结构网络图：
排列与组合
二项式定理
高中数学排列组合PPT课件

高中数学排列组合PPT课件


34 24 23 341413
3
4
1 24 1 2 3
从 4 个不同的元素a,b,c,d 中取出 3 个 ,然后按照一定 的顺序排成一列,共有多少 种不同的排列方法 ?
241412 231312
由此可写出所有的三位数 : 123,124,132,134,142,143, 213,214,231,234,241,243, 312,314,321,324,341,342, 412,413,421,423,431,432,
5、为了使写出的所有排列情况既不重复也不遗漏， 最好采用“树形图”。
2、排列数
从n个不同元素中取出mm n个元素的所有
不同排列的个数叫做从 n个不同元素中取出m
个元素的
排列数
,
用符号A
m n
表示.
A是英文字arrangement排列的第一个字母.
上面的问题1,是求从3个不同元素中取出2个元素
的排列数,
第1步,确定百位上的数字,在1,2,3,4这4个数字中任 取1个,有4种方法; 第2步,确定十位上的数字,当百位上的数字确定后, 十位上的数字只能从余下的 3 个数字中去取,有 3 种方法;
第3步,确定个位上的数字,当百位、十位上的数
字确定后,个位上的数字只能从余下的 2 个数字
中去取,有 2种方法; 根据分步乘法计数原理, 从1,2,3,4这4个不同的数
思考 你能归纳一下排列的特 征吗?
根据排列的定义,两个排列相同,当且仅当两个排 列的元素完全相同,且元素的排列顺序也相 同.例 如在问题 2中,123与134的元素不完全相同 ,它们 是不同的排列;123与132虽然元素完全相同, 但元 素的排列顺序不同,它们也是不同的排列.
高中数学排列与组合课件

高中数学排列与组合课件

P(n,m)=n!/(n-m)!，其中n!表示n的阶乘，即 n×(n-1)×...×3×2×1。
3
排列的性质
P(n,m)=P(n,n-m)，P(n,m)=P(n-1,m-1)+P(n1,m)。
排列的计算方法及应用
计算方法
根据排列的公式，将具体的n和m 代入公式进行计算。
应用
排列在组合数学、概率论、统计 学等领域有广泛的应用，如排列 组合问题、概率计算等。
高中数学排列与组合 课件
汇报人： 202X-01-05
目录
• 排列与组合的基本概念 • 排列的计算方法 • 组合的计算方法 • 排列与组合的综合应用 • 练习题与答案解析
01 排列与组合的基本概念
排列的定义与性质
排列的定义：从n个不同元素中取出m个元素（m≤n ），按照一定的顺序排成一列，称为从n个元素中取
02
区别
排列考虑元素的顺序，而组合不考虑元素的顺序。
03
应用场景
在实际问题中，需要根据具体情境选择使用排列或组合 来描述和解决问题。
02 排列的计算方法
排列的公式与性质
1 2
排列的定义
从n个不同元素中取出m个元素（m≤n），按照 一定的顺序排成一列，称为从n个不同元素中取 出m个元素的排列。
排列的公式
进阶练习题2
题目内容涉及排列与组合与其他数学知识的结合，如概率论 、统计学等。答案解析：详细解释了如何将其他数学领域的 知识与排列与组合相结合，以解决更为复杂的实际问题。
综合练习题
综合练习题1
题目内容涉及排列与组合的多个知识点，要求考生具备较高的数学综合能力。答 案解析：详细解释了如何综合运用排列与组合的多个知识点解决实际问题，并提 供了多种解题思路。
排列组合问题17种方法ppt课件

排列组合问题17种方法ppt课件


C
6 9
一
二
三
四
五
六
七
班
班
班
班
班
班
班
30
将n个相同的元素分成m份（n，m为正整数）,每份至少一个元素,可以用m-1块隔板，插入n个元素 排成一排的n-1个空隙中，所有分法数为
C m 1 n 1
31
练习题
1. 10个相同的球装5个盒中,每盒至少一 有多少装法？
C4 9
2 .x+y+z+w=100求这个方程组的自然数解 的组数
A
5 5
A A A
2 4
1 4
5 5
一般地,元素分成多排的排列问题,可归结为一排考虑,再分段研究.
前排
后排
20
练习题
有两排座位，前排11个座位，后排12个座位，现安排2人就座规定前排中间的3个座位不能坐，并 且这2人不左右相邻，那么不同排法的种数是______
346
21
重排问题求幂策略
把6名实习生分配到7个车间实习,共有 多少种不同的分法
解:完成此事共分六步:把第一名实习生分配 到车间有 种分法.
7
把第二名实习生分配
到车间也有7种分法，
依此类推,由分步计
7 6 数原理共有 种不同的排法
允许重复的排列问题的特点是以元素为研究 对象，元素不受位置的约束，可以逐一安排 各个元素的位置，一般地n不同的元素没有限 制地安排在m个位置上的排列数为 种
一个盒子装1个 （6）每个盒子至少1个
25
练习题 一个班有6名战士,其中正副班长各1人 现从中选4人完成四种不同的任务,每人 完成一种任务,且正副班长有且只有1人 参加,则不同的选法有________ 种 192
高中数学第三章排列组合与二项式定理3.1.2.1排列与排列数课件新人教B版选择性必修第二册

高中数学第三章排列组合与二项式定理3.1.2.1排列与排列数课件新人教B版选择性必修第二册


3.5A！××33××22×1＝15.
4．由 1,2,3 这三个数字组成的三位数分别是 _1_2_3_,_1_3_2_,2_1_3_,_2_3_1_,3_1_2_,_3_2_1______． 解析：用树形图表示为
由“树形图”可知组成的三位数为 123,132,213,231,312,321， 共 6 个．
[基础自测]
1．判断(正确的打“√”，错误的打“×”) (1) 两 个 排 列 的 对 象 相 同 ， 则 这 两 个 排 列 是 相 同 的 排 列．( ) × 因为相同的两个排列不仅对象相同，而且对象的排列顺 序相同．
(2)从六名学生中选三名学生参加数学、物理、化学竞赛， 共有多少种选法属于排列问题．( )
2．由 1 知 A24 ＝4×3 ＝12，A34 ＝4×3×2 ＝24，你能否 得出 A2n的意义和 A2n的值？
[提示] A2n的意义：假定有排好顺序的 2 个空位，从 n 个对 象 a1，a2，…，an 中任取 2 个对象去填空，一个空位填一个对象， 每一种填法就得到一个排列；反过来，任一个排列总可以由这样
题型三 排列数公式的推导及应用
状元随笔 1.两个同学从写有数字 1,2,3,4 的卡片中选取卡
片进行组数字游戏．从这 4 个数字中选出 2 个或 3 个分别能构成 多少个无重复数字的两位数或三位数？
[提示] 从这 4 个数字中选出 2 个能构成 A24 ＝4×3 ＝12 个无重复数字的两位数；若选出 3 个能构成 A34 ＝4×3×2 ＝24 个无重复数字的三位数．
题型一 排列的概念
例 1 判断下列问题是否为排列问题． (1)北京、上海、天津三个民航站之间的直达航线的飞机票 的价格(假设来回的票价相同)； (2)选 2 个小组分别去植树和种菜； (3)选 2 个小组去种菜； (4)选 10 人组成一个学习小组； (5)选 3 个人分别担任班长、学习委员、生活委员； (6)某班 40 名学生在假期相互通信．
3.1中职数学《排列与组合》ppt课件1(详细)

3.1中职数学《排列与组合》ppt课件1(详细)

2 A1 A ． 9 9 9 (9 8) 648
巩 固 知 识 典 型 例 题
分析 象例4这样，“首先考虑特殊 因为百位上的 元素或特殊位置，然后再考虑一般 数字不能为0， 元素或位置，分步骤来研究问题” 所以分成两步考 是本章中经常使用的方法． 虑问题．第一步 先排百位上的数 字；第二步从剩 余的数字中任取 2个数排列．
有 两 种 公 式 可 以 计 算
n! m A 即 n （n m)!
例2 计算A
A． 2 解：A5 5 4 20
2 和 5
4 4
A4 ！ 4 3 2 1 24． 4 4
分析 选出3本不同 的书，分别送给 甲、乙、丙3位 同学，书的不同 排序，结果是不 同的.因此选法的 种数是从5个不 同元素中取3个 元素的排列数．
m n
想一想：用1，2，3，4，5这五个数字，组成没 有重复数字的三位数， 其中偶数有多少个？
解：A A 5 4 2 40
自 我 反 思 目 标 检 测
2 5 1 2
百 十 个
A
2 5
1 2、4 2
A
想一想：用0~9这10个数字，组成没有重复数字 的三位数?
解：A A 5 4 2 40
巩 固 知 识 典 型 例 题
例3 小华准备从7本世界名著中任选3本，分别送给甲、乙、丙
3位同学，每人1本，共有多少种选法？ 解 不同的送法的种数是
A3 ． 7 7 6 5 210
即共有210种不同送法．
例4 用0，1，2，3，4，5可以组成多少个没有 重复数字的3位数？
解 所求三位数的个数为
第三章 概率与统计
3.1 排列与组合
基础模块中，曾经学习了两个计数原理． 一般地，完成一件事，有n类方式．第1类方式有 k1 种方法， 第2类方式有 k 2 种方法，……，第n类方式有kn 种方法，那么完 成这件事的方法共有
排列组合的ppt课件免费

排列组合的ppt课件免费


题目2：从7个不同元素 中取出4个元素的组合数 ，其中某特定元素可以 不被取出。
答案1：$A_{7}^{4} A_{6}^{3} = 7 times 6 times 5 times 4 - 6 times 5 times 4 = 336$
答案2：$C_{7}^{4} C_{6}^{3} = frac{7 times 6 times 5 times 4}{4 times 3 times 2 times 1} - frac{6 times 5 times 4}{3 times 2 times 1} = 28$
排列组合问题的变种与拓展
排列组合问题的变种
如“带限制的不同元素的排列组合” 、“重复元素的排列组合”等，需要 进一步拓展学生的思路。
拓展方法
通过变种问题的解析，引导学生深入 思考排列组合问题，并掌握其变化规 律，为解决更复杂的问题打下基础。
04
CATALOGUE
排列组合的数学原理
排列组合的数学原理简介
数学教育的核心
排列组合是数学教育中的 重要内容，对于培养学生 的数学素养和解决问题的 能力具有重要意义。
解决排列组合问题的方法与技能
乘法原理
加法原理
乘法原理是解决排列组合问题的基础，通 过将各个独立事件的产生概率相乘，可以 计算出复合事件的产生概率。
加法原理用于计算具有互斥性的事件的概 率，通过将各个互斥事件的产生概率相加 ，可以得到总的产生概率。
解析方法
通过实例演示和讲授，帮助学生理解排列组合的基本概念和计算方法，同时引导 学生思考如何解决实际问题。
实际问题的排列组合解决方案
实际问题的排列组合
如“安排会议”、“排定演出节目单”、“安排生产计划” 等，需要结合具体情境进行分析。
高中数学排列组合常用方法与技巧精讲 PPT课件 图文

高中数学排列组合常用方法与技巧精讲 PPT课件 图文

结论2 捆绑法:要求某几个元素必须排在一起的问题, 可以用捆绑法来解决问题.即将需要相邻的元素合并为 一个元素,再与其它元素一起作排列,同时要注意合并元 素内部也可以作排列.
例3 在高二年级中的8个班,组织一个12个人的年级学 生分会,每班要求至少1人,名额分配方案有多少种?
分析 此题若直接去考虑的话,就会比较复杂.但如果我 们将其转换为等价的其他问题,就会显得比较清楚,方 法简单,结果容易理解.
种选A法74 .根据乘法原理,共有的不同坐法为
种A.88 A74
结论1 插空法:对于某两个元素或者几个元素要求不 相邻的问题,可以用插入法.即先排好没有限制条件的 元素,然后将有限制条件的元素按要求插入排好元素 的空档之中即可.
例2 5个男生3个女生排成一排,3个女生要排在一起, 有多少种不同的排法?
结论4 剩余法:在组合问题中,有多少取法,就有多少种 剩法,他们是一一对应的,因此,当求取法困难时,可转化 为求剩法.
例5 期中安排考试科目9门,语文要在数学之前考,有 多少种不同的安排顺序? 分析 对于任何一个排列问题,就其中的两个元素来讲的 话,他们的排列顺序只有两种情况,并且在整个排列中,他 们出现的机会是均等的,因此要求其中的某一种情况,能 够得到全体,那么问题就可以解决了.并且也避免了问题 的复杂性.
分析 此题若是直接去考虑的话,就要将问题分成好几 种情况,这样解题的话,容易造成各种情况遗漏或者重 复的情况.而如果从此问题相反的方面去考虑的话,不 但容易理解,而且在计算中也是非常的简便.这样就可 以简化计算过程.
解 43人中任抽5人的方法有C 453种,正副班长,团支部书
记都不在内的抽法有 种C 450,所以正副班长,团支部书记至
解数学不之加前任考何”限,与制“条数件学,整安个排排在法语有文之种A前99 ,“考语”文的安排排法在是
新教材高中数学第三章排列组合与二项式定理3-1-1-1基本计数原理课件新人教B版选择性必修第二册

新教材高中数学第三章排列组合与二项式定理3-1-1-1基本计数原理课件新人教B版选择性必修第二册

知识点二 分步乘法计数原理
完成一件事，如果需要分成 n 个步骤，且：做第一步有 m1 种不同的方法，做第二步有 m2 种不同的方法，……，做第 n 步 有 mn 种不同的方法．那么完成这件事共有 N＝_m_1_×__m_2_×__…__×__m_n_ 种不同的方法．
[基础自测]
1．下列说法不正确的是( ) A．在分类加法计数原理中，两类不同方案中的方法可以相 同． B．在分类加法计数原理中，每类方案中的方法都能完成这 件事． C．从甲地到乙地有两类交通方式：坐飞机和乘轮船，其中 飞机每天有 3 班，轮船有 4 班．若李先生从甲地去乙地，则不同 的交通方式共有 7 种． D．某校高一年级共 8 个班，高二年级共 6 个班，从中选一 个班级担任星期一早晨升旗任务，安排方法共有 14 种．
(3)正确，因为 x 从集合{2,3,7}中任取一个值共有 3 个不同的值， y 从集合{－3，－4,8}中任取一个值共有 3 个不同的值，且对应 x·y 的值各不相同，故 x·y 可表示 3×3＝9 个不同的值．
(4)错误，因为每个项目中的冠军都有 3 种可能的情况，根据分 步乘法计数原理共有 34 种不同的夺冠情况．
答案：B
4．从 A 地到 B 地，可乘汽车、火车、轮船三种交通工具， 如果一天内汽车发 3 次，火车发 4 次，轮船发 2 次，那么一天内 乘坐这三种交通工具的不同走法数为( )
A．1＋1＋1＝3 B．3＋4＋2＝9 C．3×4×2＝24 D．以上都不对
解析：分三类：第一类，乘汽车，从 3 次中选 1 次有 3 种走法； 第二类，乘火车，从 4 次中选 1 次有 4 种走法；第三类，乘轮船， 从 2 次中选 1 次有 2 种走法．所以，共有 3＋4＋2＝9 种不同的走 法．
Chap3-1容斥原理棋盘多项式和有限制条件的排列.

Chap3-1容斥原理棋盘多项式和有限制条件的排列.

500 500 A 166, B 100; 3 5 500 A B 33 15
被或5除尽的数的个数为
A
B A B A
B
166 100 33 233
3.1
容斥原理
例4 求由a,b,c,d四个字母构成的n位符号串中a,b,c 都至少出现一次的符号串数目。 解：令A、B、C分别为不出现a，b，c符号的集合。
3.1
容斥原理
例5 用26个英文字母作不允许重复的全排列，要求 排除dog，god，gum，depth，thing字样的出现，求 满足这些条件的排列数。 解：所有排列中，令 A1为出现dog的排列的全体；
A2为出现god 的排列的全体； A3为出现gum的排列的全体； A4为出现depth的排列的全体； A5为出现thing的排列的全体；
B C
-A CB
(2)
3.1
容斥原理
A∩B
U A B
A∩C
C
A∩B ∩C
B∩C
3.1
容斥原理
例2 一个学校只有三门课程：数学、物理、化 学。已知修这三门课的学生分别有170、130、 120人；同时修数学、物理的学生45人；同时修 数学、化学的20人；同时修物理化学的22人。 同时修三门的3人。假设每个学生至少修一门课， 问这学校共有多少学生？ 解：令A为修数学的学生集合； B 为修物理的学生集合； C 为修化学的学生集合；
An Aj Ak
U Ai Ai (1) n A1 A2
Aj - Ai An
(5)
容斥原理指的就是（4）和（5）式。 用来计算有限集合的并或交的元素个数。
3.1
容斥原理
组合数学课件--第三章第二节棋盘多项式和有限制条件的排列

组合数学课件--第三章第二节棋盘多项式和有限制条件的排列


解：
A B CD
G
L
W
Y
37
3.5 有禁区的排列
R(
) = xR( ) + R(
)
=x(1+x)(1+2x)+(1+2x)(1+3x+x2)
= 1+6x +10 x2 +4x3
按照定理3.3，相当于r1=6,r2=10,r3=4,代入公式：
N n r 1 ( ! n 1 ) ! r 2 ( n 2 ) .! .r n .
2.9 欧拉函数(n)
1
2.10 n对夫妻问题
3
*2.11 Mobius反演定理
×
2.12 鸽巢原理
4
2.13 鸽巢原理举例
4
2.14 鸽巢原理的推广
4
*2.15 Ramsey数
×
41
再见
利用公式 R (C )x(R C (i))R (C (e)) 化简棋盘多项式
R( ) =1+ x； R( )= xR( )+ R( ) =x+(1+x)=1+2x；
R( ) = x R( ) + R( )
=x(1+x)+1+x =1+2x+x2。
23
3.4 棋盘多项式和有限条件的排列
R( ) = x R( ) + R( )
i1
35
3.5 有禁区的排列
两个棋子落入禁区的方案数设为r2,而其余n2个棋子为无限制条件的排列，方案数是(n-2)!。
n
Ai Aj r2(n2)!
i1 ji
布n个棋子无一落入禁区的方案数应为：

高中数学(排列组合)课件PPT


知识清单 知识点二 排列
3.排列数公式
Pnm
(n
n! m)!
n (n
1) (n
m 1)
4.全排列公式
Pnn n!
记住下列几个阶乘数：0!=1,1!=1,2!=2,3!=6,4!=24,5!=120,6!=720.
知识清单
知识点三 组合
1.组合 一般地，从n个不同的元素中任意取出m(m≤n)个元素为一组，称为从n个不 同的元素中任意取出m个元素的一个组合. 2.组合数 我们把从n个不同的元素中任意取出m(m≤n)个元素的所有组合的个数，称为
知识清单
知识点二 排列
1.排列 一般地，从n个不同的元素中任意取出m(m≤n)个元素，按照一定的顺序排成一 列，称为从n个不同的元素中任意取出m个元素的一个排列. 2.排列数 我们把从n个不同的元素中任意取出m(m≤n)个元素的所有排列的个数，称为从n
个不同的元素中任意取出m个元素的排列数，记作 Pnm.
例
典例精析
例
典例精析
例
巩固练习
过关练习
巩固练习
过关练习
巩固练习
过关练习
巩固练习
过关练习
同学们！再见！
课后一定要多练习哦！
从n个不同的元素中任意取出m个元素的组合数，记作 Cnm

知识清单 知识点三 组合
3.组合数公式
Cnm
Pnm Pmm
n! m!(n m!)
n(n 1) (n m 1) m (m 1) 21
4.组合数的性质
Cnm Cnnm
Cnr1 Cnr Cnr1
典例精析
例
典例精析
例
典例精析
例
典例精析
高中 数学

排列组合课件

不相邻问题
将需要排列的元素按照一定的顺序排 列，如果元素之间没有间隔，则它们 是相邻的。
复杂排列组合问题解析
排列组合的顺序性
在排列组合的过程中，需要考虑元素的顺序，不同的顺序会 产生不同的结果。
排列组合的可重复性
在排列组合的过程中，需要考虑元素的重复使用，不同的重 复方式也会产生不同的结果。
常见排列组合问题解析
排列特点
与元素的顺序有关，是"有序"的。
组合定义与特点
组合定义
从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个元素中取出m个元 素的一个组合。
组合特点
与元素的顺序无关，是"无序"的。
排列与组合的联系与区别
联系
都是从n个不同元素中取出m个元 素的不同方式。
区别
排列注重的是取出元素后，元素 的顺序是否相同；组合则不考虑 取出元素后的顺序。
排列组合课件总结
排列组合基础知识
排列组合课件应涵盖排列组合的 基本概念、公式和定理，帮助学
生建立正确的排列组合思维。
排列组合问题解析
通过典型例题的解析，让学生掌握 解决排列组合问题的方法和技巧， 提高解题能力。
排列组合应用实例
引入实际应用场景，让学生了解排 列组合在生活、科技、经济等领域 中的应用，增强学习的兴趣和动力 。
组合数公式广泛应用于组合数学、概率论、统计学等学科中，也是解 决实际问题的有力工具。
排列组合综合公式
排列组合综合公式定义
排列组合综合公式表示从n个不同元素中取出m个元素的所有排列和组合的个数，用符号 P(n,m)表示。
排列组合综合公式计算方法
排列组合综合公式可以表示为P(n,m)=A(n,m)+C(n,m)，即P(n,m)=n!/(n-m)!+C(n,m)。

Chap3-1容斥原理棋盘多项式和有限制条件的排列.


利用(３)和(４)，可以把较复杂的棋盘逐步分解成 相对比较简单的棋盘，从而得到其棋盘多项式。
例: R (
*
) = xR(
)+R(
)
= x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3
R( *
) = x R(
) + R(
)
= 1+6x +10 x2 +4x3
3.2.
例
容斥原理—应用
∞
∞
= xR(Ci) + R(C e)
(3)
3.2.
例如：
容斥原理—应用
)=1+ x；
)= xR( )+ R( )= x+ (1+ x)=1+2x；
R(
R( R(
)= x R( ) + R( ) = x(1 + x )+1 + x =1+ 2x +x2
3.2.
容斥原理—应用
如果C由相互分离的C1，C2组成，即C1的任一格 子所在的行和列中都没有C2的格子。则有：
故答案是：16-3=13
3.1
容斥原理
对于求两个有限集合A和B的并的元素数目，我们有 定理1
A
B A B A
B
(1)
即具有性质A或B的元素的个数等于具有性质A的 元素个数和具有性质B的元素个数减去同时具有 性质A和B的元素个数。
3.1
容斥原理
U
A∩B
A
B
3.1
容斥原理
定理2
A
B
C ABC A C A B
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。


k
k 0
1 rk (C ) x k
k 1

1 [rk 1 (C( i ) ) rk (C( e ) )] x k
1 rk 1 (C(i ) ) x k rk (C( e ) ) x k
x rk 1 (C(i ) ) x k 1 1 rk (C( e ) ) x k
i 1 n i 1 j i n n
Ai A j Ah ...
i 1 j i h j
( 1) n A1 A2 ... An
n! r1(n 1 )!r2(n 2 )! ... (1) rn
n
35
3.5 有禁区的排列
A1 A2 ... An
A1 A2 ... An
例2 求a,b,c,d,e,f这6个字母的全 排列中不允许出现ab和de图像的排列数。
4
3.4 棋盘多项式和有限制条件的排列
(3)递推关系 既可解决限制元素出现次数的问题，也能解 决元素出现位置的问题 典型特征是：写出递推关系
甲 乙 R(C) =(1+x)(1+x)(1+3x+x2) =1+5x+8x2+5x3+x4 丙 丁
30
3.4 棋盘多项式和有限条件的排列
例3.5 一婚姻介绍所，登记有5名男性A，B， C，D，E和4名女性1，2，3，4，经了解：1不能与 B,C,D,E，2不能与A,D,E,3不能与A,B,C，4不能与 A,B,C,D求可能婚配的方案数。 解：
第3章 容斥原理与鸽巢原理
3.1 3.2 3.3 3.4 3.5 3.6 3.7 2.8 2.9 2.10 *2.11 2.12 2.13 2.14 *2.15 De Morgan定理 容斥原理 容斥原理举例 棋盘多项式与有限制的排列 有禁区的排列 广义的容斥原理 广义容斥原理的应用 第二类Stirling数的展开式 欧拉函数(n) n对夫妻问题 Mobius反演定理 鸽巢原理 鸽巢原理举例 鸽巢原理的推广 Ramsey数 1 1 1 2 2 3 3 1 1 3
甲 乙 丁
1 2 3 4
11
3.4 棋盘多项式和有限条件的排列
例4:甲乙丙丁4个人住店,有5个房间1,2,3, 4,5,甲不住1,2,3号房间,乙不住2,3,4房间,丙 不住1、4号房间,丁不住1,2,4号房间,求满足要 求的方案数。
甲 乙 丙 丁
1 2 3 4 5
12
3.4 棋盘多项式和有限条件的排列
5
3.4 棋盘多项式和有限制条件的排列
(4)棋盘多项式
解决无重复排列元素出现位置的问题 例3:甲乙丙丁4个人,有4项工作1,2,3,4,甲 干不了1,2,3号工作,乙干不了2,3,4号工作,丙干 不了1、4号工作,丁干不了1,2,4号工作,求满足 各人工作要求的方案数。
6
3.2 棋盘多项式和有限条件的排列 1、棋盘多项式的由来
2
3.4 棋盘多项式和有限制条件的排列
(1)指数型母函数 主要解决限制元素出现次数的排 列问题 例1 求1,3,5,7,9这5个数字组成的n位数 个数，要求其中3出现的次数为偶数，其它 数字出现的次数无限制。
3
3.4 棋盘多项式和有限制条件的排列
(2)、容斥原理：
既可解决限制元素出现次数的问题，也能 解决元素出现位置的问题 典型特征是：问题能够化为集合问题：
i
r1 ( n 1)!
34
3.5 有禁区的排列
两个棋子落入禁区的方案数设为r2,而其余n2个棋子为无限制条件的排列，方案数是(n-2)!。
A A
i 1 j i i
n
j
r2 (n 2)!
布n个棋子无一落入禁区的方案数应为：
A1 A2 ... An N Ai Ai A j
k 1 k 1
k 1

k 1
k 1

x rh (C(i ) ) x h rk (C( e ) ) x k xR(C(i ) ) R(C( e ) )
h 0 k 0
21


3.4 棋盘多项式和有限条件的排列
利用公式 R(C ) xR(C(i ) ) R(C( e ) ) 化简棋盘多项式 R( R( R( ) =1+ x； )= xR( )+ R( ) = x R( ) =x+(1+x)=1+2x； )
1 2 3 4
A B C D E
31
3.4 棋盘多项式和有限条件的排列
解：
1 2 3 4
A B C D E
R(C) =(1+x)(1+2x)(1+3x+x2) =1+6x+12x2+9x3+2x4
***
32
3.5 有禁区的排列
例6:设对于1,2,3,4的排列P=P1P2P3P4， 规定P1≠3，P２≠1，P３≠2，P4≠4。
25
3.4 棋盘多项式和有限条件的排列
在C上布k个棋子可分为C1上布i个，C2上布 k-i个,方案数是 ri (C1 )rk i (C2 )
R(C ) rk (C ) x k
k 0
R(C ) ( ri (C1 )rk i (C2 )) x
k 0 i 0

k
k
ri (C1 ) x i rj (C2 )x j
i 0 j 0


R(C1 ) R(C2 )
26
3.4 棋盘多项式和有限条件的排列
例：
R( ) = xR( )+R( )
= x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3
27
3.4 棋盘多项式和有限条件的排列
例：
R( ) = xR( ) + R( )
=x(1+x)(1+2x)+(1+2x)(1+3x+x2) = 1+6x +10 x2 +4x3
棋盘C
C(I)
C(e)
R(C) = 1+ 5x+6x2+2x3 R(C(i)) = 1+ 2x+x2 R(C(e)) = 1+ 4x+4x2+x3
20
3.4 棋盘多项式和有限条件的排列
公式2、 R(C ) xR(C(i ) ) R(C( e ) )
证明： (C ) rk (C ) x R
435 512
9
3.4 棋盘多项式和有限条件的排列
x x x x x
令rk(c)表示k只棋子布到棋盘C的不同的方 案数，规则是当一只棋子布到棋盘的某一格时， 则这个格子所在的行和列上的其他格子不再允许 布上别的棋子。
10
3.4 棋盘多项式和有限条件的排列
例3:甲乙丙丁4个人住店,有4个房间 1,2,3,4,甲不住1,2,3号房间,乙不住2,3,4房间, 丙不住1、4号房间,丁不住1,2,4号房间,求满足 要求的方案数。
37
3.5 有禁区的排列
例3.8 错排问题
x
将错排问题看做是有 禁区的排列，可看作禁区 是在对角线上的方格。
对角线棋盘的棋盘多 项式为：
R(C ) (1 x) n
x
x
x
x
· · ·
38
1 C (n,1) x C (n,2) x 2 ... C (n, n) x n
3.2 棋盘多项式和有限条件的排列
) + R(
=x(1+x)+1+x =1+2x+x2。
22
3.4 棋盘多项式和有限条件的排列
R(
) = x R(
) + R(
)
=x+1+2x+x2 =1+3x+x2。
23
3.4 棋盘多项式和有限条件的排列
R(
)
= x R(
) + R(
)
=x+(1+x)(1+2x) =1+4x+2x2。
24
3.4 棋盘多项式和有限条件的排列
设C(I)是棋盘C的某一指定格子所在的行与 列都去掉后所得的棋盘；
C(e)是仅去掉该格子后的棋盘。
棋盘C
C(I)
C(e)
16
3.4 棋盘多项式和有限条件的排列
公式1、rk(C)=rk－1(C(I))＋rk(C(e)) 例如:
棋盘C r2(C)= 6
C(I) r1(C(i))= 2
C(e)
r2(C(e))= 4
×
4 4 4
1
×
3.4 棋盘多项式和有限制条件的排列
一、有限制的排列
对有重复的排列或无重复的排列，可以对一 个或多个元素的出现次数进行限制，也可以对某 些元素出现的位置进行限制，这两种情况统称为 有限制条件的排列。
1、解决这些问题的工具有： (1)、指数型母函数：
(2)、容斥原理：
(3)、递推关系：
=x(1+x)(1+2x)+(1+2x)(1+3x+x2) = 1+6x +10 x2 +4x3 按照定理3.3，相当于r1=6,r2=10,r3=4,代入公式：
N n! r1(n 1 )!r2(n 2 )! ... rn
4!6 3!10 2!4 24 36 20 4 4
可以把棋盘C推广到任意形状，例如：