为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

ch3-排列组合

2011-06-04 25页 pdf 990KB 34阅读

用户头像

is_763085

暂无简介

举报
ch3-排列组合 Chapter 3 排列与组合 §1. 重复排列 一. 引例与简介 1. 例1:在三元集{a,b,c}中取两个,则 (2). 元素允许重复的排列有9个: aa, bb, cc, ab, ac, ba, bc, ca, cb, (1). 元素不允许重复的排列有P(3,2)=6个: ab, ac, ba, bc, ca, cb 1 1 2 2 1 2. 1. { , , }, , , ( k k k i i S n a n a n a a a S n a   定义...
ch3-排列组合
Chapter 3 排列与组合 §1. 重复排列 一. 引例与简介 1. 例1:在三元集{a,b,c}中取两个,则 (2). 元素允许重复的排列有9个: aa, bb, cc, ab, ac, ba, bc, ca, cb, (1). 元素不允许重复的排列有P(3,2)=6个: ab, ac, ba, bc, ca, cb 1 1 2 2 1 2. 1. { , , }, , , ( k k k i i S n a n a n a a a S n a   定义 多重集 其中 为 中所有互不相同的元素, 1)称为元素 的重数.  重数无限制的重复排列计数问题  重数确定的重复排列计数问题  各元的重数分别限定于某些特定子集的重复排列 计数问题  圆周上的重复排列问题  一般图上的重复排列问题 3. 重复排列计数问题的类型 注:重复排列即从S中有序的取出r个元 1 21. 1. { , , } . k r S a a a r k      定理 多重集合 的 排列数为 Proof: r个位置中,每个位置都有k种选择,且不依 赖于前面已选择的项. 二. 关于重复排列的若干结论 例:P30. Ex. 22:  若允许相邻位置的数相同  若不允许相邻位置的数相同 1 1 2 21. { , , , }, . k k i r S n a n a n a n r S r k     2.推论 多重集 若 , 则 的 排列数为 1 1 2 2 1 1 21 3. . { , , , } ! , , . ! ! k k k kk S n a n a n a nn n n n n n nn n          定理2 多重集 的全排列 数为 记为 这里 Proof: 方法一:从n个位置中依次找出ni 个位置给ai 1 11 1 2 1 11 1 1 2 1 2 1 N ( )!( )!! !( )! !( )! !0! ! ! ! k k k k k n n nn n n nn n n n nn nn n n n n n n n n n n n                            方法二:先看n个元的全排列(视为两两不同),n! 再看重复元的内部排列. i in a个 互换位置对应的实为同一个排列 1 2 , . k nn n n nk           注:(1) 此即 的推广 即多项式系数 1 2{ , , , }kn M a a a(2)此即 元集 的有序划分的个数: 即一:将n元集M有序划分为k份,使得第i份恰含有ni个 元素的划分个数为多少? 即二:将n个不同的球放到k个不同的盒子里,使得第i 个盒中恰含有ni个球的放法数有多少? (3) 这里每个划分即相当于一个映射 ( )i if a j a j  被划分到第份 注:用列表法来表示X到Y的映射,则每一个映射即相 当于从k个元素中选取n个的一个重复排列. 1 2 1 2 { , , , }, { , , , }n kX x x x Y y y y 设集合 ①求X到Y的映射个数N1 ②求X到Y的恰有ni个元素映成yi的映射个数N2,这 里n=n1+n2+...+nk 解: N1即从k个元素中取n个的重数无限制的重复排列 个数 解: N2即k个元素的重数固定为n1,n2,...,nk的重复排 列个数 3. 排列与映射: 解:N3即从k个元素中取n个不同元素的排列个数. : 计数问题的基本思想方法即:建立适当的一 一对应关系,要求问题A的数,改求问题B的方 案数. ③求X到Y的单射个数N3 特别,若X,Y均为n元集,则从X到Y的一一映射 的个数为n! 三. 应用举例 例1:一个矩形有向道路区由n+1条自左向右的横道路 和m+1条自下向上的竖道路构成,则从左下角A点到右 上角B点的有向道路由多少条呢? 解:(1) 此即从A(0,0)到B(m,n) (2) 由A到B的一条有向路等价于m个横段与n个 竖段所成的一个重复排列 ( )! ! ! m n N m n  (3)故, 注:(1) 称为从(0,0)到(m,n)的非降路径数 (2) 推广到高维:在k维欧氏空间的类似有向道路区内, 从原点到点(n1,n2,...,nk)的有向道路条数即多项式系数 例2. 将20本不同的分送给王6本,李6本,张8本, 求不同的送法数. 注:(1) 此即{20本书}到{王,李,张}的映射,使得6个 元映到王,6个元映到李,8个元映到张的映射个数 (2) 若题为“将20本书分送给3人,使得其中两人得 6本,另一人得8本”呢? 例3. 将2n个人分成n组,使得每组2人,问有多少 种分法? 注: (1) 此即将2n个不同的球放到n个相同的盒子中, 使得每盒2球的放法数 (2) 注意盒子是否标号,有区别! (3) 思考:将n个不同的物体放到k个相同的盒子里, 使得第i个盒中恰含有ni个物体的放法数有多少? §2. 重复组合 一. 引例与简介 1. 例1:在三元集{a,b,c}中取两个,则 (2). 元素允许重复的组合有6个: aa, bb, cc, ab, ac, bc (1). 元素不允许重复的组合有C(3,2)=3个: ab, ac, bc 2. 定义1. 从多重集S中不计次序地选出r个元素,即 为S的r-组合.  重数无限制的重复组合计数问题  重数确定的重复组合计数问题  各元的重数分别限定于某些特定子集的重复组合 计数问题 3. 重复组合计数问题的类型 注:本节考虑重数无限制的重复组合问题 1 21. { , , , } 1 . kS a a a r k r r             定理1. 多重集合 的 重复组合数 为 1 2 Proof : (1) .k S r x x x r 集的 组合数等于如下不定方程的非负 整数解的个数: + + + = (2) {( 1) , 1}T k r   此不定方程的非负整数解的个数即为多重集 的全排列数. ( 1 ) (3) ( 1)! ! k r N k r     ! 二. 关于重复组合的若干结论 1 1 2 2. { , , , }, 1 . k k i S n a n a n a S r k r n r r           推论1 则 的 组合数 为 ,这里 注: (1) r-组合数与不定方程的非负整数解之间可形成 一一对应 1 (2) 1 . k r k r r r         即为 元集的 元子集的个数 (3) 集合S={1,2, …,k}的r重复组合与T={1,2,…,k+r-1} 的r非重复组合可形成一一对应 1 2 1 2 { 1, 2, , } 1 1 0 1 1 1 {1,2, , 1} r r S k r y y y k y y y r k r T k r r                          的 重复组合 即: 即: 的 元子集 对应如下: 1 22. . { , , } 1 ). 1 kM a a a r r r r k k            定理2 从多重集 中取 个 元,要求每个不同元至少出现一次,则其 组合数为 ,( 1 2 Proof : (1) .k r x x x r 此 组合数等于如下不定方程的正整数解 的个数: + + + = 1 2 (2) ky y y r k对应于不定方程 + + + = 的非负 整数解的个数. 3. 变形: 思考一:从k种不同的东西中(每种无限多),取出r个 东西的取法数是多少? 将r个相同的球放到k个不同的盒中的放法数呢? 思考二:从k种不同的东西中(每种无限多),取出r个, 且每种至少拿一个的取法数是多少? 将r个相同的球放到k个不同的盒中,且无空盒的放法 数呢? 4. 推广 将r个相同的球放到k个不同的盒子里,且每个盒中 至少有q个球(r≥kq)的放法数为多少? 1 2 3 4 1 2 3 4 20 3 1 0 5. x x x x x x x x    例1:求不定方程 + + + = 的整数解的个数, 其中 , , , 三. 应用举例 1 22 . nx x x k n k k        例 :求证不等式 + + + 的非负整数解的 个数为 思路: 在原不等式的非负整数解与n+k元集的k元(或 者n元)子集之间建立一一对应关系 1 2 1 1 2 1 2 Pr ( , , , ) ( 1, 2, , )n n oof x x x x x x x x x n        :(1)定义映射: (2)原不等式的非负整数解→ {1,2,…,n+k}的n项递增序列 注:n元集合中的r项递增序列与n元集合中的r元子集 是对应的. 0 1 . k j n j n k j k               习题:试证明等式: 1 2 1n nx x x x k     另解: 直接与等式 的非负整数解对应 例3:从集合M={1,2,…,n}中取出一个k元子集,使得 其中任意两数之差大于L,问这样的k元子集的个数有多 少? 注: 这样的k元子集称为L间歇的(或称L间隔k-组合) 1 2 1 { , , , }, k i i a a a a a L   解:(1) 取k元子集依次排列为 则 (3) 将符合条件的子集与不定方程的整数解对应 2 3 11 1 2 1 2 3 1,2 , , , , 1 k k k x x xx n a a a a a a a n 个数 (2) 设在 , 中, 的位置如下: 1 1 1 11, 1,( 1,2, , ),i i i k ka x a a x i k a x n        则: 1 2 1 1 1 0, ( 2, , ), 0 k i k x x x n k x x L i k x             注:这个带限制条件的组合问题可以看做是无重复组合 和重复组合计数公式的一个共同推广: (3) L=1时,即相应的k元组合中无相继数出现 1 2 1y ( 1) (4) 0( 1,2, , 1) k i y y n k k L y i k            此即 ( 1)n k L N k         故 (1) L=0时,即普通n元集的k元无重复组合 (2) L=-1时,即普通n元集的k元可重复组合 例4:将正整数n有序剖分成k个部分(即表成若干个正 整数之有序和)且允许重复的方案数是多少? 解:对应于不定方程的正整数解的个数问题 注:(1) 即正整数的有序剖分数 (2) 推广:将n有序剖分成k个部分,使得第i个分 部量至少是qi(这里i=1,…,k), 有多少种方案?
/
本文档为【ch3-排列组合】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索