组合数学(4)

1P13练习题9一间屋子内有10个人，他们中没有人年龄超过60岁，但又至少不低于1岁。证明，总能找到两组人（两组不含相同的人），各组人的年龄和是相同。题中的数10能换成更小的吗？解：从10个人中任意选0到10人为一组，则共有：1021010.......2101100102种选择方法，由于必须分成两组，去掉其中的：共有：1022种，又因为每个人的年龄可以是1到60中的任意一个，年龄和可能的分布共：60×10=600种，因此，相当于1022个物体放在600个盒子，由鸽巢原理，至少有两组分配在同一盒子中，在同一个盒子中的两组的年龄和必然相等；若将人数降为9人，共有29-2=510种，分配给60×9=540个盒子，不能得到题意的要求。210100103第三章排列与组合3.2集合的排列定义:设n元集S={a1,a2,…,an}，从S中取出r个不同元素按次序排列，称为S的一个r-排列，其个数称为r-排列数，记作P(n,r)或。当n=r时，S的r-排列又称S的全排列，其个数P(n,n)又称全排列数。r-排列就是将r个元素有序摆放。rnp4例：如果集合S={a,b,c}，则S的3个1-排列是a,b,cP(3,1)=3S的6个2-排列是:ab,ac,ba,bc,ca,cbP(3,2)=6S的6个3-排列是:abc,acb,bac,bca,cab,cbaP(3,3)=6S没有4-排列及其以上的排列,因为S中最多只有3个元素。排列的特征在于排出的字符串一定有顺序之分。5定理3.2.1对于正整数n和r，若r≤n，则P(n,r)＝n×(n－1)×…×(n－r＋1)即:我们定义n!（读作n的阶乘）为：n!=n×(n－1)×…×2×1并约定0!=1)!(!),(rnnrnp)1()(110knknrkrk6例1字母ABCDEF的排列中有多少个包含子串DEF?解：为了保证DEF出现在子串中，这三个字母必须连在一起且保持这个顺序,可以将DEF看成一个字符。剩余的字母A,B和C可以放置在任意的位置。可以把构造包含子串DEF的ABCDEF的排列看作四个标号DEF,A,B,C的排列.由全排列定义，7四个对象有4！个排列。于是包含子串DEF的ABCDEF的排列数为4！=24。DEFABC例2:ABCDEF的包含字母DEF不间隔任意顺序的排列有多少个？8我们可以通过两步来解决这个问题：选择字母DEF为一个子字符串，构造DEF的一个任意顺序的排列。由全排列定义，第一步有3！=6种方法，根据例1，第二步可以有24种方法。根据乘法原理，ABCDEF的包含字母DEF的任意顺序的排列数为：6×24=1449例3:七个男人和五个女人坐一排开会，如果不允许两个女人坐在一起(可能是因为她们开会喜欢说话)，有多少种方法？解:我们可以用两步将男人和女人排列起来：先排列男人，再排列女人。男人有7！=5040种排法，一旦我们已经排好男人，因为不能有两个女人站在一起，女人有八个可能的位置可以站：10_M1_M2_M3_M4_M5_M6_M7_（这样就保证了女人不相邻）因此女人有P(8,5)=8×7×6×5×4=6720种排列方法。根据乘法原理，七个男人和五个女人坐一排开会，如果不能有两个女人站在一起，共有：5040×6270=33868800种方法。11例4有多少取自{1,2,…,9}的各位互异的7位数使得5和6不以任何顺序相继出现？[解法一]{1,2,…,9}的7-排列中满足要求的可被分成4类：1）5，6均不出现。即{1,2,3,4,7,8,9}的7-排序P(7,7)122）5出现6不出现。即5有7个位置，其余是{1,2,3,4,7,8,9}的6-排列7×P(7,6)3）5不出现6出现。即5有7个位置，其余是{1,2,3,4,7,8,9}的6-排列7×P(7,6)134）5与6同时出现，但是a）第1位等于5。此时6有5个位置，其余是{1,2,3,4,7,8,9}的5-排列:5×P(7，5)b）第7位等于5。此时6有5个位置，其余是{1,2,3,4,7,8,9}的5-排列:5×P(7，5)c）5出现在首尾之外的位置上。14此时，5有5个位置可选。对于每种5的选择，6仅有4个位置可选。其余5位是{1,2,3,4,7,8,9}的5-排列。于是5×4×P(7，5)综上所述，结论为P(7,7)＋7×P(7,6)×2＋5×P(7,5)×2＋5×4×P(7,5)＝15120015[解法二]令T是{1,2,….,9}的所有7-排序的集合。现对T构造划分S和,其中S是满足要求的7位数的集合，而T=S∪T=S+所以S=T－而T＝P(9,7);＝2×6×P(7,5)故S＝P(9,7)－2×6×P(7,5)＝1512005,6作为相连子串有:56或65之分,共有6个位置放。SSSSS16以上我们讨论的是线性排列。例如{1，2，3，4，5，6}的两个6-排列：561234与234561是两个不同的排列。但是，如果我们把每个排列各自的首尾相接起来，所形成的两个“环”就没有什么不同。此时，1我们称它们属于同26一个循环排列。35他们是右图：417上述循环排列可以从下列线性排列得到：123456234561345612456123561234612345其中的每一个通过将第一元素看成接在最后一个元素后面的元素产生。这样，要想求得循环排列的数目，我们只要用6去除线性排列的数目即可。故上述元素的循环排列数为：6!/6=5!=12018定理3.3.2n个元素的集合的循环r-排列的个数是特别地，n个元素的循环排列的个数是(n-1)!例5：10个人要围坐一圆桌，其中有两人不愿意彼此挨着座。共有多少种循环座位按排方法？[解法一]将这两个人挨着座，看成一个元素，共9个元素的循环排列有：9!/9=8!种；这两个人挨着座又有左右之分，总共应该有:2×8!种;题意的安排为：10!/10－2×8!=7×8!！)(!),(rnrnrrnp19[解法二]我们把不愿意彼此挨着座的两人设为：A,B。假设A固定位置不动，B就不能排在A的左右，A的左边只能余下的8个人，同时A的右边只能再余下的7个人,其他7个位置的安排可以是：7!种满足题意的排法共：8×7×7!=7×8!A.。DC非B...非B20例6将12个不同的记号记在旋转的圆鼓上的方法有：12!/12=11!种例7用20个不同的珠子穿成一条项链，能够做成多少不同的项链？解：20个珠子共有20！种不同的排列。由于是做成项链，属于循环排列，项链数目最多为：20！/20=19！；又由于项链可以翻转而珠子的排列未改动，因此项链的总数是：19！/221生成n!个全排列的错位置排法当n=1，排列方式只有一种，就是1。当n=2时，先将唯一的1-排列1写出两次，并错位置以2，即得两个2排列如下：1221当n=3时,先将两个2-排列分别写出3次,共6次22并错位置以3，即得3!=6个3排列如下：123132312321231213当n=4时,先将6个3排列分别写出4次,并错位置以4,即得4!=24个4排列.(请仿上法自己写出)23与彩票选号一样,从1---33中243.2集合的组合定义:设n元集S={a1,a2,…,an}，从S中无序选择取出r个不同元素作为S的一个子集，称为S的一个r-组合，其个数称为r-组合数，记作C(n,r)或=例：S={a,b,c,d},那么S的3-组合是：{a,b,c},{a,b,d},{a,c,d},{b,c,d};组合数rnCrn43425组合数中显然有下列结论：1.当r＞n时2.当r＞0时3.几个特殊的组合数00r0rn1nnnn110n10026定理3.3.1对于0≤r≤n有从而证明：由定义r-组合与r-排列的区别在于前者不计较元素的先后顺序，因此由每个r组合可以作出r！个不同的r-排列。即先完成组合再排列rnrrnP!),()!(!!!),(rnrnrrnPrn27于是若有C(n,r)种r组合，则有C(n,r)×r!种排列,因此C(n,r)×r!=P(n,r)。例8在平面上给出25个点，没有三点共线，问这些点能够成多少直线？能确定多少三角形？解：由于没有三点共线，25个点中任意2个点就能连成一条线，有：300224*25)!225(!2!2522528同理，25个点中任意3个点就能连成一三角形，有：例9从五个女生和六个男生中选出一个由两个女生和三个男生组成的委员会有多少种方法?解：两个女生可以有C(5,2)=10种选法,而三个男生可以有C(6,3)=20种选法。委员会可以有两步顺序构成:选择女生,选择男生。根据乘法原理,委员会总共可以有10×20=200种选法。!22!3!25)!325(!3!2532529例:从1—33这33个连续的自然数中任意选出7个数为彩票号码,共有C(33,7),大约四百多万组号码。这里面肯定包含了所有的奖项，包括5000000圆的大奖，但是我们不能花八百多万去夺取这个大奖；彩迷们都希望将大奖的范围尽可能缩的更小，这就给研究随机问题的数学家提出挑战。30例10用26个英文字母能构成多少个含有3个、4个或5个元音的长为8位的单词？其中，每个字母出现在单词中的次数不限。解对于含有3个元音8位单词,单词中任三位都可是元音，先调出元音位置共有C(8,3)个,26个英文字母共有5个元音字母，每个位置有5种可能共53种放置法，其余5位都是辅音有215种可能，从而具有3个元音的单词数为:31同理，含有4个元音的单词数为含有5从而，满足题设的单词共有:5353215)!38(!3!8215384444215)!48(!4!8215483535215)!58(!5!82155832例11恰好包含四个1的八位二进制串有多少个?解：在8个位置中给1任找4个位置，不关0,1的顺序共有例12一副52张的普通纸牌由梅花,方片,红心,黑桃四个花色的13种面额为A,2--10,J,Q,K的牌组成。354453215!3!5!8215!4!4!8215!5!3!8个702345678!4!4!84833(a)从52张普通牌中选五张牌(无序)有多少种选法?(b)五张牌为同一花色的有多少种选法?(c)五张牌中的三张为一个面额而另外两张为另一个面额的选法有多少种?解(a)答案是C(52,5)=2598960(b)要有同一花色的五张牌可以经过两步:选择花色,再从这种花色中选择五张牌。第一步有4种34方法而第二步有C(13,5)种方法。根据乘法原理，答案为4×C(13,5)=5148(c)要有3张为一个面额而另外两张为另一个面额的五张牌，可以经过四步来选取：选择第一种面额，再选择第二种面额，选择第一种面额的三张牌，选择第二种面额的两张牌。第一种面额有13种选法，选了第一种面额之后，第二种面额有12种选法。从第一种面额中选择不同花色的三张牌有35rnnrnC(4,3)种方法，而从第二种面额中选择不同花色的二张牌有C(4,2)种方法。根据乘法原理，答案为：13×12×C(4,3)×C(4,2)=3744推论：对于0≤r≤n有:证明很简单，请同学们自己完成36定理3.3.2n个元素的集合的所有组合的总数是即证明:因为S的r-组合的个数是:r＝0,1,2,…,n所以S的所有组合的总数是:nnnnnn2......210nnrrn20rn