组合数学题目及答案.doc

组合数学例1: 将8个“车”放在88的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态?解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。 用一个排列a1,a2,a8 ，对应于一个安全状态，使ai表示第i行的ai列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!40320。例4：n 位客人在晚会上每人与他人握手d次，d 是奇数。证明n 偶数。 证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n位客人与他人握手 次数的总和 nd 是偶数 握手次数的2倍。根据奇偶 性质，已知d是奇数，那么n必定是偶数。例 从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数，其中一个是另一个的倍数。证 设n+1个数是a1, a2, , an+1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r1, r2, , rn+1。这n+1个数仍在1 , 2n中，且都是奇数。而1, 2n中只有n个奇数，故必有ri=rj= r, 则ai= 2i r, aj= 2j r。若aiaj，则ai是aj 的倍数。例5 设a1, a2, , am是正整数，则至少存在一对k和l, 0k h，使得 ah+1+ ak= 39 证 令Sj= ，j =1 , 2 , ,100。显然S1S2h SkSh=39 即 ah+1+ ah+2+ ak= 39 例：1) 求小于10000且的含1的正整数的个数 2) 求小于10000的含0的正整数的个数解：1) 小于10000的不含1的正整数可看做4位数, 但0000除外. 故有999916560个. 含1的有：99996560=3439个2) 上述方法不可直接套用来计算“含0”数的个数。 0019“含1”但“不含0”。 不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个 不含0小于10000的正整数有 9+92+93+94=(951)/(91)=7380个 含0小于10000的正整数有 99997380=2619个多重集(Multiset)：元素可以重复出现的集合。如： =a,a,a,b,c,c,d,d,d,d，也可简记为： M=3a, 1b, 2c, 4d 元素也可重复出现无穷次，如无穷个a记为：a例 1000到9999 之间有多少个奇数，其各位数字互不相同？答案：5887=2240 例 用数字1，1，1，3，8可以构造多少个不同的5位数？如果用1，1，1，3，3呢？答案： 54=20 (5,2)=10定义：设r为正整数，从n个不同的元素的集合S中，取r个元素按次序排成一行，称为S的一个r-排列。例 S=a,b,c，则S有 3个1-排列：a，b，c 6个2-排列：ab，ac，ba，bc，ca，cb 6个3-排列：abc，acb，bac，bca，cab，cban元素集的r-排列数记为P(n,r)。若rn，则P(n,r)=0。n元素集S的n-排列简称为S的排列或n个元素的排列（全排列）定义 n!=n(n-1) 21 0!=1 故 P(n,r )= n!/(n-r)! P(n,0)=1 P(n,n )= n!/0!=n!例 将26个英语字母按任意次序排成一行，不允 许a、e、i、o、u五个元音中任意两个相邻， 有多少种排法？答案： 21! P(22,5)例 从1,2, ,9 中任意取7个不同的数字排成一 行，不允许5和6相邻，可以组成多少个不同 的7位数？ 答案： P(9,7)-26P(7,5) = 151,200例 10个人围圆桌入座，其中两人希望不坐在一起，有多少种方案？答案：9！-28！例 5对夫妇出席一宴会，围一圆桌坐下，试问有几种不同的方案？若要求每对夫妇相邻又有多少种方案。答案：9 ！=362880 254 ！=3224=768例 20个不同颜色的珠子串成一条项链，可以串成多少种不同的项链？答案：19!/2设r为一非负整数，从具有n个不同元素的集合S中，取r个 元素而不考虑其次序，称为S的一个r-组合，即S的一 个r元素子集。例如：若S=a,b,c,d，则S有 1个0-组合：f 4个1-组合：a，b，c，d 6个2-组合：a,b，a,c，a,d，b,c，b,d，c,d 4个3-组合：a,b,c,a,b,d,a,c,d,b,c,d 1个4-组合：a,b,c,d例 设总共有15名同学选了数学课，但每次只有12名同学到课，教室里有25个座位，数学老师能看到学生们有多少种可能的座位坐 法？答案： C(15,12)P(25,12)例 如果每个单词可以有3个或4个元音，字母可以重复使用，用26个英文字母可以构造出多少个8个字母的单词？答案： C(8,3)53215 +C(8,4)54214 例 求不多于四位的三进制数的个数。解：这个问题相当于多重集0,1,2的4-排列问题，由定理3.4.1，所求的三进制数的个数N=34=81。例 用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？解 所求的标志数是多重集2红旗,3黄旗的排列数N, 由定理3.4.2得： N=5!/(2!3!)=10例 MISSISSIPPI这个单词里的所有字母可以组成多少不同的排列？答案：11!/(1!4!4!2!)定义 设S是多重集，S的含有r个元素的子多重集就叫做S的r-组合。例如：S=2a,1b,3c，S的2-组合有5个，它们是a,a,a,b,a,c,b,c,c,c定理3.5.1 设多重集S=a1, a2, ak，则S的r-组合数是C(r+k-1,r)。从k种元素中取允许重复的r-组合的典型模型是：取r个相同的球，放进k个不同的盒子里，而每个盒子中的球数不加限制，允许重复的组合数即其放法方案数。 该数为C(r+k-1,k-1) =C(r+k-1,r)从a,b,c 3种元素中取2个元素的多重组合，相当于将2个相同的球放人3个不同的盒中，每盒可多于一个球的方案。 多重组合与球放入盒子的方案的对照：例 从为数众多的一角币、二角币、五角币和一元币中选取六枚有多少种方法？解 这里有4种不同的币值,每种币都可无限重复,因此本问题是多重集S=1角,2角,5角,1元的6-组合，故从中选出6枚的方法种数为： C(4+6-1,6)=C(9,6)=84例 试问(x+y+z)4展开后有多少项？解：这个问题相当于从3种元素中取可重复4-组合，或4个相同的球放进3个不同的盒子里，其组合数为： C(3+4-1,4)=C(6,4)=15即：(x+y+z)4共15项。推论 设多重集S=n1a1,n2a2,nkak，且对一切i=1,2,k有nir，则S的r-组合数是C(r+k-1,r)。推论 设多重集S=a1, a2, ak，rk，则S中每个元素至少取一个的r-组合数为 C(r-k+k-1,k-1)=C(r-1,k-1)。推论 r个相同的球放到k个有标志的盒子中，不允许有空盒，共有C(r-1,k-1)种方案。例 有一电冰箱厂生产15种电冰箱，将其装入集装箱销往外地，每个集装箱可装18台电冰箱，要求每个集装箱内各种电冰箱至少一台，问可能有多少种不同的集装箱装法？答案：k=15,r=18 N=C(18-1,15-1)=C(17,14)=680例 设多重集 S=10a,10b,10c,10d ，要求每 种元素在组合中至少出现一次，求S的满足此条件的 10 组合的数目。解 方程x1+x2+x3+x4=10的正整数解的个数即为 所求。用变量代换 y1=x1-1，y2=x2-1，y3=x3-1，y4=x4-1， 变换成求 y1+y2+y3+y4=6的非负整数解的个 数。该数目为 C(6+4-1,6)=C(9,6)。例 设方程x1+x2+x3+x4=20，求满足x13, x21, x30, x45 的整数解的个数。 解 作变量代换 y1=x1-3，y2=x2-1，y3=x3，y4=x4-5，方程y1+y2+y3+y4=11的非负整数解的个数即为所求，该数为 C(11+4-1,11)=C(14