10第1章组合分析 例如，n=8,r=3时，可以选两个就能隔开： 000100000 代表向黄1=3=3=2.由于一共有（仁二）种选搭可能，因此就可以得到 以下命题： 命题6.1共有(？二)个不同的正整数向量，2，.，)满足 x1+x2+.+zr=n x4>0,i=1,.,r 为了得到非负整数解（而不是正整数解）个数，注意到x1+x2+.十xr=n 的非负整数解个数与劝+2+.+，=n+r的正整数解个数是相同的（令 =x+1,i=1,.,r小.因此，利用命题6.1，可得到如下命题： 命题62共有(（十”)）个不同的非负整数向量，)满足 x1+2+.+xr=n (6.1) 例6a方程x1+x2=3共有多少组不同的非负整数解？ 解一共有（生2）=4组解：031,22,3.0 ■ 13 例6b有2万美元可投资到4个项目上，每份投资必须是1000美元的整数倍， 如果要求2万美元全部投资，一共有多少种可行的投资方法？如果不要求将钱全部 投资呢？其证明留作习题 解：令x,i=1,2,3,4分别表示4个项目的投资额，因此，4个项目的投资额就 是方程1+x2+x3+x4=20 x:≥0的非负整数解.因此，根据命题62，一共 有()=171种可能的投资方式如果并不需要将钱全部投资，那么假设%表示 剩余资金，那么一个投资策略就对应了如下方程的一个非负整数解： 1+x2+x3+x4+x5=20x4≥0 因此，根据命题6.2，存在(24=10626种投资策略。 ◆ 例6c在(x1+x2+.+x)”的辰开式中，一共有多少项？ 晚 其中，求和针对所有满足n1+.+nr=n的非负整数(n1,.,nr.因此，根据命
小结11 题62，一共有(，)项 ◆ 例6d再来讨论例4c,有n个天线，其中m个是不可分辨的失效天线，另n-m 个也是不可分辨但却有效的.现在要求求出排成一排且没有连续两个失效天线的可 能排列数.设想m个失效的天线排成一排，现找出放n一m个有效天线的位置.如 果是排成了如下方式： x10x20.Em0xn+1 其中1≥0是放在最左边的有效天线数：>0，i=2,.,m,是放在第i个失效 天线和第i一1个失效天线之间的有效天线的个数；xm+1≥0是放在最右边的有效 天线数.这样的配置意味着任两个失效天线之间都至少有一个有效天线，因此，满 足条件的可能数是下列方程向量解的个数： x1+.+m+1=n-m1≥0，xm+1≥0，xi>0,i=2,.,m 14 令1=x1+1,班=，i=2,.,m,m+1=xm+1+1,可以看出它等同于以下方 程的正整数向量解个数： +2+.+m+1=n-m+2 由命题61知，一共有(（仁一m+)种这样的配置方式，这与例4c的结果一致 现在来考虑每两个失效天线之间至少有两个有效天线这种情况的排列数.根 据上述同样的理由，结果为如下方程的解的个数： 1+.+xm+1=n-mc1≥0，xm+1≥0，xi≥2，i=2,.,m 令1=x1+1,班=-1，i=2,.,m,m+1=xm+1+1,可以看出它等同于以下 方程的正整数向量解的个数： 1+.+m+1=n-2m+3 因此，由命题6.1，可知一共有(-2m+2)种配置方式 ■ m 小结 计数基本法则阐述了如下事实：如果一个试验分成两个阶段，第一个阶段有 种可能结果，每种结果又对应于第二个阶段的m种可能结果，那么该试验一共有 nm种可能结果. n个元素的排列一共有n!=n(n-1).3·2·1种可能排列方式.特别地， 0!=1. (份)=a-m
12第1章组合分析 其中0≤i≤n,否则等于0.此式表明了从n个元素中选取i个元素的可能数，因 其在二项式定理中的突出地位，它也常称为二项式条数，我们有 (e+n=∑(0）xy-i 对于任意和为n的非负整数，.，nr, n! 它等于n个元素分成互不重叠的r部分，其中各个部分的元素个数分别是1,2，.， 15可n,的分法数. 习题 1.(a)前2位为字母而后5位为数字的汽车稗照一共多少种？ (b)在上述条件下，如果不允许字母和数字重复，又有多少种？ 2.掷一枚骰子4次，一共有多少种结果？比如说，如果第一次为3，第二次为4，第三次为 3,第四次为1，那么结果就是“3,4,3,1” 3.20种不同的工作分派给20个工人，每个工人一种工作，间有多少种分派方式？ 4.约翰、吉姆、杰伊和杰克组成一个有4种乐器的乐队，如果每个人都会演奏这4种乐 器，问可以有多少种不同的组合？如果约瀚和吉姆会演奏这4种乐器，而杰伊和杰克分 别只会弹钢琴及打鼓，那么又有多少种不同组合？ 5.一直以来，美国和加拿大的电话区号由3位数组成，第一位是2~9之间的任一数字 第二位是0或者1；第三位是1~9之间的任一数字问一共有多少种可能的区号？以4 开头的区号一一共有多少种可能？ 6.有个熟知的童谣： 我出发去圣一艾弗斯 路上碰见一个人， 带着他7个老婆 每个老婆挎着了个包 每个包里装着7只猫 每只猫生了7只小猫咪， 数数看，我到底看到了多少只小猫咪？ 7.(a)3个男孩和3个女孩坐在一排，一共有几种坐法？ (b)如果男孩和女孩分别坐在一起，一共有几种坐法？ (c)如果只要求男孩坐在一起，一共有几种坐法？ (d)如果相邻的座位上必须坐异性，一共有几种坐法？ 8。以下单词的字母可以有多少种排列方式？ (a)Fluke;(b)Propose;(c)Mississippi;(d)Arrange
习题13 9.一个孩子有12块积木，其中6块黑色、4块红色、1块白色和1块蓝色.孩子想把这些 10.大楼农糖一尖南多纱种挂法如果 (a)没什么限制： (b)A和B必须坐在一起； (©)一共4个男人，4个女人，且任何两个男人不能坐在一起，任何两个女人也不能坐在 一起；(d)共有5个男人，且他们必须坐在一起： ()有4对夫妇，每对夫妇必 须坐在一起 11.3本小说、2本数学书和1本化学书，把它们摆放到书柜里，一共有多少种摆放方法？如果 ()书可以以任何顺序摆放；(b)数学书必须放一起，小说必须放一起： (©)小说必须放一起，其他书无所谓. 16 12.某个班级有30名学生，有5个不同的奖项（成缵奖、组织奖等等）要领发，一共有多少 种不同的领奖方式？如果 (a)一个学生可以得多个奖项.(b)每个学生最多只能得1个奖项. 13.有20个人，每人都要与其他人握一次手，一共要握多少次手？ 14.从一副牌的52张中任意抽取5张， 一止右 15. 个舞蹈班 少种抽法？ 有22个学生，10女12男，要挑选5男5女然后配对，一共有多少种配法？ 16。某学生从6本数学书、7本科学书和4本经济学书里卖掉2本，有多少种选择？如果 (a)两本书同一科目：(b)两本书不同科目. 17.共有7件不同的礼物分给10个孩子，如果每个孩子最多只能拿1件礼物，一共有多少 种分法3 18.有5名共和党人，6名民主党人和4名无党派人土，要从中分别选取2名共和党人、2 名民主党员和3名无党派人士组成一个七人委员会，一共有多少种选法？ 19.从8女6男里选择3女3男组成委员会，一共有多少种选法？如果 (a)其中有两个男人不愿同时进入委员会： (b)其中有两个女人不愿同时进入委员会： ()其中有一男一女不愿同时进入委员会， 20.某人有8个朋友，他打算邀请其中5人参加茶会， (a)如果有某两人长期不和，不能同时参加茶会，他有多少种邀请方案？ (b)如果有某两人只能同时被邀请，一共有多少种邀请方案？ 21.如下图，从标有A的地方出发，每一步只能向上或者向右移动，问移动到B一共有多少 种移动方式？ 提示：从A到B需向右4步，向上3步
14第1章组合分析 □22.在习题21中，如果要求必须经过标有圆圈的点（如下图），一共有多少种移动方式？ P9 23.。某从事睡梦研究的心理学实验室有3间房间，每间房里有2张床现要安排3对双胞胎 进行睡梦实验研究，要求每对双胞胎必须安排在同一间房的不同床上，一共有多少安排 方法？ 24.展开(3x2+y5 25.桥牌比赛中有四个选手参加，每人分到13张牌，一共有多少种分法？ 26.展开(x1+2x2+33) 27.12个人分成各含3、4和5人的委员会一共有多少种方法？ 28.8个老师分配到4个学校，一共有多少种分法？如果要求每个学校必须接收2个老师 呢？ 29.一共10个举重选手参加比赛，其中3名美国选手、4名俄罗斯选手、2名中国选手和 1名加拿大选手，如果成绩只记录每个选手的国籍，一共有多少种可能结果？如果美国 手有1名在总成绩前三名，另两名在总成绩的最后三名中，那么一共有多少种可能结 果 30.有分别来自俄国、法国、英国和美国等10个国家的代表坐在一排，如果法国和英国代 表坐在一起，俄国和美国代表不坐在一起，一共有多少种坐法？ 31.8块相同的黑板分给4所学校，一共有多少种分法？如果要求每所学校至少分到1块黑 板呢？ 32.电梯载着8个人（不包括电梯工）自底层启动，到顶层6楼后，乘客已全部下完.如果 电梯工只注意到每层楼出去的人数，那么他能看到多少种离开电梯的方式？如果8个 乘客中有5个男人和3个女人，而电梯工又只注意了出去人的性别问题的答案又是多 33.有2万美元要投资到4个项目上，每份投资必须是1000美元的整数倍，且每个项目如 果有投资的话，最少投资额分别为2000,2000,3000和4000美元，一共有多少种可行的 投资方法，如果： 18 (a)每个项目都要投资。 (b)至少投资其中3个项目 理论习题 1.证明推广计数法则. 2.进行两个试验，第一个试验有m个结果，对应其第i个结果，第二个试验有个结果， 1=1,2,.,m.问这两个试验一共多少结果？