资源描述
二、组合 与排列不同，组合是研究无次序的选取问题。 定义：从 n个不同元素中无次序地选取 k个，叫做从 n个元素中选 k个的一个 组合。记 或 其中 中 C是 Combination的第一个字母， 而 是 Andreas Von Ettingelausen(17961876)发明的 排列与组合的关系： （ 1） 由（ 1）可推出组合数的两个基本恒等式： (i) (ii) 另外，还约定： 当 kn及 k-6,y-6,z-6也就是相当于 x+50, y+50, z+50. 即原方程化为 (x+5)+(y+5)+(z+5)=16 所以原问题化为 u + v + w=16 即 （个） 例 在 1与 106之间，有多少个整数的各位数字之和等于 9？ 解： 只要将问题设想为将 9个无区别的球随意放入 6个不同的 盒子。即 3CC 131 113 1 53CCC 218161816 1163 2 0 0 2CC 5149 1-69 鸽笼原理或抽屉原理 （ 简介 ） 我们在讨论重排列时 ， 如将问题化为：设盒子是有区别的 ， 每个盒子的容量不限 ， 而且球数 k盒数 n， 现计算无空盒出现 的情况数目 。 假设要用 n-1块隔板 ， 将排成一行的 k个球隔成 n段 ， 但任意 两块隔板不能相邻 ， 否则就要出现空盒 ， 同理隔板也不能出现 在两端 。 所以相当于要自 k个球之间的 k-1个间隔中选出 n-1个 来放置隔板 ， 如图 。 O|OO|O|OOO|O|O|OOO|OO|O 所以是一个组合问题 ， 知有 种不同情况 。 例 x + y + z + w=23， 有多少正整数解 ？ 解：与前面例子相似 ， 但 x、 y、 z、 w不能等 0。 即 知 有 个正整数解 。 例 高三有 8个班协商组成年级篮球队 ， 共需 10名队员 ， 每班 至少出 1名 。 问有多少种组成方式 ？ 解：设有 10个无区别的球与 8个不同的盒子 ， 不能出现空盒 ， 即 1n 1kC 1540CC 32214 123 36CCC 297918 110 补充例子 某市有 n所中学，第 i所中学派出 ci名学生 (1 ci 39， 1in)来到体育 馆看球赛，全部学生总数为 ，看台上每一横排有 199个座位， 要求同一学校的学生必须坐在同一横排，问体育馆最少要安排多少横排才 能保证全部学生都能坐下？ 解：首先证明，只要安排 12个横排即可满足。 由于 ci只有有限个， ci的有限和也是有限个，选取其中最接近 199的有限 和，设为 ci1 + ci2 + + ci k ，即使 x1=199-(ci1 + ci2 + + ci k) min 让这 些学生坐在第一排，则 x1便是第一排中的空位数。于是对 j i1， ， ik 的所有 j均应有 cj x1+1（否则第一排又可排下一个 cj）。我们可断言必然 有 x1 32。事实上，反证之，若 x1 33，则对所有其余 cj，应有 cj 34， 从中任取 5个学校，不妨设为 c1， c2， c3， c4， c5则有 5x39=195 c1+c2+c3+c4+c5 5x34=170 =199-( c1+c2+c3+c4+c5 ) 199-170=2932 此与 x1的最小性矛盾。 1 9 9 9cn 1i i 从所有其余的 cj中选取 cj1+cj2+ +cj t 使其最接近 199，让这些学生坐在 第二排。 令 x2=199 ( cj1+cj2+ +cj t ) 同理可证 x2 32 对于第 3排、第 4排、 、第 i排依次如此去做。 当安排好第 i 排后，令 x i 表示第 i 排的空位数，则只要剩下的学校不少 于 5所，便一定有 x i 32，推理同前。 如果在安排完 11排后，学生已坐完，则问题得证。 如果还未坐完，则可分为两种情况： 一是余下学校不足 5所，由于 4x39199，则其余学生可坐第 12排； 如果余下的学校不少于 5所，则仍有 x11 32，这样前 11排至少坐 11 x (199-32)=1837个学生，余下的学生不多于 162个，自然可坐在第 12 排上。 例 将边长为 n的一个正方形分成 n x n个个单位正方形，相当于画成一个围 棋盘，棋盘中当然能数出许多矩形来。按惯例，称矩形的短边为宽，长边 为长，并把正方形也算作矩形。证明：棋盘中有 23个宽 n-1的矩形， 33个宽 n-2的矩形， ， n3个宽 1的矩形，并由此导出公式 证： 数轴上以整数为端点，含于区间 0， n中且长度是 n-k的区间共有 k+1个，它们是 0， n-k， 1， n-k+1， ， k， n 。 因此，棋盘中以横向为宽，纵向为长，且宽 n-k，长 n-l (l k)的矩形有 (k+1)(l+1)个。对 l 求和，即知棋盘中以横向为宽，纵向为长，且宽 n-k的 矩形共有 同理，以纵向为宽，横向为长且宽为 n-k的矩形也有 个。注意 到其中长宽均为 n-k的正方形有 (k+1)2个，它们同时被计了上述两个数字， 所以棋盘中宽为 n-k的矩 形共有 (k+1)2(k+2)-(k+1)2=(k+1)3 k=1,2, ,n-1 22333 1)(nn 4 1n21 2)(k1)(k 2 1 1 ) )(kk21 ) ( 1(k 1)1 ) ( l(k 2 k 0l 2)(k1)(k21 2 另一方面，棋盘中任意两条横向直线和任意两条纵向直线都可以界得一个 矩形。于是由乘法原理知棋盘中共有 个矩形。综合两方面得： *例 n个人参加同一会议，其中每两个互不认识者都恰好有两个共同的熟 人，每两个熟人却都没有共同的认识者。证明：每一个与会者都有相同数 目的熟人。 解：设与会者甲有 m位熟人 a1， a2， ， am，由于他们都同甲熟悉，所以 他们互不认识。（ 为什么？）（因为其中任一个与甲为熟人，故没有共同 熟人，所以他们互不认识） 既然他们都互不认识，所以他们中每两个人 (ai ， aj)除甲外都还有另一个共同的熟人，这些熟人当然都不认识甲 （为什 么？因为如果有人认识甲，则甲的熟人为 m+1，不是 m了） 。另外，对于 不同的 (ai ， aj)，另一熟人也互不相同。于是 2 1n2 1n CC 22 2 2 1n 2 1n 333 1)(nn 4 1 2 1) n(nCCn21 知与会者中不认识甲的人不会少于 。但另一方面，每个不认识甲的人 同甲一道都有两个共同的熟人，这些人既然都认识甲，所以都在 a1， a2， ， am之列，而且对于不同的不认识甲的人。这两个共同的熟人 (ai ， aj)也不会全然相同 （为什么？如果有相同，则甲与不认识者就有多于 2个共同熟人） 。因此可得，不认识甲的人不会多于 个。综上所述得， 与会者中恰有 个不认识甲的人。这样一来，参加的总人数 n便应满足 等式 考察这个关于 m的正整数二次方程，发现它只有唯一的正数根。所以对于 每个与会者，他的熟人数目 m为常数。 （负值舍去） 唯一 2mC 2mC 2mC 1)m ( m21m1Cm1n 2m 2 11)(n81 m 2 1)8( n11 m 01)2( nmm01)(n 2 m 2 m 22
展开阅读全文