《高中数学课件 1.3重集的排列与组合》由会员分享，可在线阅读，更多相关《高中数学课件 1.3重集的排列与组合（16页珍藏版）》请在金锄头文库上搜索。
1、1.3 重集的排列与组合n1.3.1 重集的概念n1.3.2 重集的排列n1.3.3 重集的组合1.3.1 重集的概念n定义1.3.1 元素可以重复出现的集合称为重集(multiset)。元素a出现的次数叫做该元素的重数(repetition number)。n重集S表示为 Sn1a1, n2a2, nkak其中a1,a2,ak为S中k个不同类型的元素，ni(ni是正整数或)(i1,2,k)为ai的重数。1.3.1 重集的概念n重集S的r排列S的r个元素的有序摆放n重集S的全排列或排列n重集S的r组合S中r个元素的无序选择S的子重集(submultiset) 1.3.2 重集的排列n定理1.3
2、.1重集Sa1,a2,ak 的r排列的个数为krn证明 重集合S的r排列形为： 第一位 第二位第r位从k个元个元素 中任取一个从k个元素中任 取一个从k个元个元素 中任取一个1.3.2 重集的排列n定理1.3.2重集Sn1a1, n2a2, nkak，且S的元素个数为nn1n2nk，则S的全排列的个数为P(n; n1, n2, nk) 1.3.2 重集的排列n证明 重集S的全排列形为：一步，放好n1个a1 ，二步，放好n2个a2 ，三步，放好n3个a3 ， 第一位 第二位第n位1.3.2 重集的排列 P(n;n1, n2, nk)1.3.2 重集的排列n例1.3.1 某停车场有6个入口处，每个
3、入口处每次只能通过一辆汽车。有9辆汽车要开进停车场，试问有多少种入场方案？1.3.2 重集的排列n解 设9辆车分别标号为1,2,9排列123456789排列123456789则汽车的入场方案 一一对应重集S11,12,19,5的全排列故入场方案数为P(14;1,1,1,1,1,1,1,1,1,5)7264857601.3.2 重集的排列n例1.3.2 求关于x1, x2, x3, x4的方程x1x2x3x415的非负整数解的个数1.3.2 重集的排列解 该方程的非负整数解一一对应重集S151,30的全排列 ? ?1.3.2 重集的排列1.3.2 重集的排列n推广一般，关于x1, x2, xk的
4、方程x1x2 xkn的非负整数解 一一对应重集Sn1,(k1)0的全排列1.3.3 重集的排列n例1.3.5 设有16个字母，其中a,b,c,d各四个，从中任取10个，但每种字母至少取两个，能组成多少个不同的10排列？ 1.3.3 重集的排列n解 按题意4a,4b,4c,4d的10排列分两类(1)一个字母取4次，其余各取2次P(10;4,2,2,2)(2)两个字母各取3次，其余各取2次 P(10;3,3,2,2)4a,2b,2c,2d3a,3b,2c,2d1.3.3 重集的组合n定理1.3.3 重集Sa1,a2,ak 的r 组合的个数为n证明 重集Sa1,a2,ak的r组合重集x1a1, x2a2, xkak，其中x1x2xkr且xi(i1,2,k)非负整数方程x1x2xkr的非负整数解P(r+k-1;r,k-1)=
