1、组合数学第四版答案组合数学第四版答案【篇一：组合数学参考答案(卢开澄第四版)60页】1.1 题 从1，2，50中找两个数a，b，使其满足 （1）|a-b|=5； （2）|a-b|?5； 解：（1）：由|a-b|=5?a-b=5或者a-b=-5， 由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）（50，45），共有45对。 当a-b=-5时，两数的序列为（1，6），（2，7）（45，50）也有45对。 所以这样的序列有90对。 （2）：由题意知，|a-b|?5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0； 由上题知当|a-b|=5
2、时 有90对序列。 当|a-b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）（49，50），（50，49）这样的序列有49*2=98对。 当此类推当|a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对， 当|a-b|=0时有50对 所以总的序列数=90+98+96+94+92+50=520 1.2题 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生a和b之间正好有3个女生的排列是多少？ 所以总的排列数为上述6种情况之和。 1.3
3、题 m个男生，n个女生，排成一行，其中m,n都是正整数，若 (a)男生不相邻(m?n?1); (b)n个女生形成一个整体；(c)男生a和女生b排在一起； 分别讨论有多少种方案。 解：(a) 可以考虑插空的方法。 n个女生先排成一排，形成n+1个空。因为m?n?1正好m个男生可以插在n+1个空中，形成不相邻的关系。 则男生不相邻的排列个数为 pp n n ? n?1m (b) n个女生形成一个整体有n！种可能，把它看作一个整体和m个男生排在一起，则排列数有(m+1)!种可能。 因此，共有n!?(m?1)!种可能。 (c)男生a和女生b排在一起，因为男生和女生可以交换位置，因此有2！种可能， a、
4、b组合在一起和剩下的学生组成排列有(m+n-1)！ (这里实际上是m+n-2个学生和ab的组合形成的)种可能。共有组合数为2!?(m?n?1)! 1.4题 26个英文字母进行排列，求x和y之间有5个字母的排列数解：c（24，5）*13！ 1.5题 求3000到8000之间的奇整数的数目，而且没有相同的数字。 1.7题 试证：(n?1)(n?2)?(2n)被2n除尽。 n 证明：因(2n)!?2n!(2n?1)! (n?1)(n?2)?(2n)n!(n?1)(n?2)?(2n)(2n)! ?(2n?1)! nnn 2n!2n!2因为(2n-1)!是整数所以(n?1)(n?2)?(2n)能被2n除
5、尽。 18题 求10和20的公因数数目。 404040403010306030402030 解：因为10?2*5?2*5*520?2*5?2*2*5 4030 它们最大公因子为2*5转化为求 最大公因子 能除尽的整数个数，能除尽它的整数是 2a*5b,0?a?40,0?b?30 根据乘法法则，能除尽它的数个数为41*31=1271 2 1.9题 试证n的正除数的数目是奇数。 2 证明：设有0?a?n,n?b?n2, 则一定有表达式n?a?b， 则 可知符合范围的a和b必成对出现，所以为偶数。 22 又当a=b=n时，表达式n=a?b仍然成立。所以n的正除数的数目是偶数?1为奇数。 1.10题
6、证任一正整数n可唯一地表成如下形式: 证：对n用归纳法。 ,0aii,i1,2,。 40 30 由假设对n-k!,命题成立，设 ，其中akk-1,，命题成立。 再证表示的唯一性：设 , 不妨设ajbj,令j=maxi|aibi (aj?bj)?j!?(bi?ai)?i!?j!?i?i!?bi?ai?i!?(bi?ai)?i! 矛盾，命题成立。 1.11题 证明nc(n-1,r)= (r+1)c(n,r+1),并给予组合解释. 证：nc(n?1,r)?n (n?1)!(r?1)?n!(r?1)?n! ?(r?1)c(n,r?1) r!?(n?r?1)!(r?1)?r!?(n?r?1)!(r?1)
7、!?(n?r?1)! 所以左边等于右边 组合意义：等式左边：n个不同的球，先任取出1个，再从余下的n-1个中取r个； 等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。 所以两种方案数相同。 1.12题 证明等式： ?kc(n,k)?n2 k?1 n n?1 ?n?1?n?n?1?n?1?n?1?n?1 ?n?n?nc(n?1,0)?c(n?1,1)?l?c(n?1,n?1)?n2?右边 ? 证明： 等式左边?n? k?1?k?1?k?1?k?1?s?0?s? n 1.13题 有n个不同的整数，从中间取出两组来，要求第1组的最小数大于另一组的最大数。 解题思路：（取法由大到小
8、） 第1步：从n个数由大到小取一个数做为第一组，其它n-1个数为第二组， 组合数为：c（n,1）*c(n-1,1)+c(n-1,2)-+c(n-1,n-1) 第2步：从n个数由大到小取两个数做为第一组，其它n-2个数为第二组， 组合数为：c（n,2）*c(n-2,1)+c(n-2,2)-+c(n-2,n-2) 第n-2步：从n个数由大到小取n-2个数做为第一组，其它2个数为第二组，组合数为：c（n,n-2）*c(2,1) 第n-1步：从n个数由大到小取n-1个数做为第一组，其它1个数为第二组，组合数为：c（n,n-1）*c(1,1 总的组合数为：c(n,1)?c(n?1,1)?c(n?1,2)
9、?c(n?1,n?1)?c(n,2)?c(n?2,1)?c(n?2,2)?c(n?2,n?2) ?c(n,n?2)?c(2,1)?c(n,n?1)?c(1,1) 1.14 题 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案？ 解：第1步从特定引擎对面的3个中取1个有c(3,1)种取法， 第2步从特定引擎一边的2个中取1个有c(2,1)种取法， 第3步从特定引擎对面的2个中取1个有c(2,1)中取法，剩下的每边1个取法固定。 所以共有c(3,1)?c(2,1)?c(2,1)=12种方案。 1.15题 求1至1000000中0出现的次数。 解：当第一位为0时，后
10、面6位组成的数可以从1-100000，共100000个0； 当第二位为0时，当第一位取0-9时，后面5位可以取1-9999，此外当第一位取0时，后面5位还可以取为 10000，这样共有9999*10+1=99991个0； 同理第三位为0时，共有99901个0； 第四位为0时，共有99001个0；第五位为0时，共有90001个0； 第六位为0时，只有1个0； 这样总共的0数为：100000+99991+99901+99001+90001+1=488895。 1.16题n个相同的球放到r个不同的盒子里，且每个盒子里不空的放法。 解：如果用o表示球，用|表示分界线，就相当于用r-1个|把n个o分成r
11、份，要求是每份至少有一个球。如下图所示： 00|00000000|00000000|00000|000000 对于第一个分界线，它有n-1种选择，对于第二个分界线只有n-2个选择，(因为分界线不能相临，如果相临它们之间就没有了球，这不合要求)，依次第r-1个分界线只有n-(r-1)种选择。但是这样的分法中存在重复，重复度为(r-1)!,所以总得放法为：(n-1)*(n-2)*(n-r+1)/(r-1)!=c(n-1,r-1)。 1.18题 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？ 5 解：要求空盒不相邻，这样球的位置共有8种。而不同标志
12、的球的排列有p5?5!。所以共有8*5！种排列。 8a)1 111 b) 1 111 在a)中 剩下的一个球有四种位置，b)中剩下的一个球也有四种位置，两者合起来一共有8种 1.17题 n和r都是正整数，而且r?n，试证下列等式： (a)p?np rn n?1r?1 (b) ?1 pp r ?(n?r?1)p?r!?r(p ?1 ?1 (c) n?1r?1 p ? nn?r p n?1r ,r?n (d) p n?1r ? p?rp (e) n?1 ? p ?l? p r r?1 ) 解：(a) n (n?1)!n! pr?1?n?(n?r)!?(n?r)!? n?1 n p 等式成立。 nn
13、!n! 等式成立。 ?pr?1pr(n?r?1)!(n?r)! n?1nnn(n?1)!n! (c) ?pn?r(n?r?1)!(n?r)!pr等式成立。 n?rr (b) (n?r?1)?(n?r?1)? (d) n!n!n!(n?r?1)n!(n?1)!?n!?r?r?n!(n?1)! pr?rpr?1?(n?r)!?r?(n?r?1)!?(n?r?1)!?r?(n?r?1)!?(n?r?1)!?(n?1?r)!? n n p n?1r (e)利用(d)的结论可证明本题。 r!?r(p ?1 ? p n?1r?1 ?l? p r r?1 )? p ?p?rp?rp?rp?l?rp?rp?p
14、?rp?rp?l?rp?rp?p r r?1 r?1 r?1 rr r r?1r?1 r?2r?1 n?1r?1 n r?1 r?1r r?1r?1 r?2r?1 n?1r?1 ?1 r ?rp n ?rp n?1 ?l?rp r n?1r r?1 1.19题 n+m位由m个0，n个1组成的符号串，其中nm+1,试问不存在两个1相邻的符号串的数目。 解：m个0进行排列，留出m+1个空挡，任选n 个空挡放1，共有c(m+1,n)种方案. 1.21题 一个盒子里有7个无区别的白球，5个无区别的黑球，每次从中随机取走一个球，已知前面取走6个，其中3个是白的，试问取第6个球是白球的概率。 解：c（6,
15、2）*c(5,2)*c(5,3)/c(5,3)c(7,3)c(6,3)=3/14 1.20 题 甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志占5人，试问有多少中方案？ 解：1.甲单位出4个男同志，乙单位出1个男同志，从乙单位出2个女同志 c(10,4)*c(15,1)*c(10,2)=141750 2. .甲单位出3个男同志，乙单位出2个男同志，从甲单位出1个女同志,从乙单位出1个女同志。 c(10,3)*c(15,2)*c(4.1)*c(10,1)=504000 3. .甲单位出2个男同志，乙单位出3
16、个男同志，从甲单位出2个女同志. c(10,2)*c(15,3)*c(4,2)=122850 1+2+3即为所求，总的方案数为768600 1.22题 求图1-22中从o到p的路经数: (a) 路径必须经过a点; (b) 路径必须过道路ab; (c) 路径必须过a和c(d) 道路ab封锁(但a,b两点开放) 解: (a)分两步走o(0,0)a(3,2) a(3,2)p(8,5)，根据乘法法则: ?3?2?3?5? n?2?3?560 ? 3?2?4?3?(b)分两步走o(0,0)a(3,2), b(4,2)p(8,5)，根据乘法法则:n?350 ?2?3? ? 3?2?3?1?2?2? (c)
17、分三步走: o(0,0)a(3,2), a(3,2)c(6,3), c(6,3)p(8,5), 根据乘法法则: n? ?2?1?2?240 ?（d）ab封锁路径数加必经ab路径数即o(0,0)p(8,5)的所有路径数有加法法则可得： ?5?8?3?2?4?3? n? ?5?2?3?1287?350?937? 1.23题 令s=1,2,n+1,n2,t=(x,y,z)|x,y,zs, xz, yz, 试证 :|t|? ?n?1?n?1?2 k?2? k?1?2?3? n 证明：要确定x,y,z的取值，有两种方法， 2 2 2 ?k k?1 n 2 种可能。故|t|? ?k k?1 n 2 。 (
18、2)由xz, yz，可以分为三种情况： x=yz,x,y可看作一个元素，这种情况等价于从1,2,n+1中取2个进行组合，然后比较大小，小者为x(y),大者为z,其组合数为? ?n?1? ?； ?2? n?1? xyz,等价于从1,2,n+1中取3个进行组合，然后比较大小可得x,y,z,其组合数为?； ?3?n?1? yxz,等价于从1,2,n+1中取3个进行组合，然后比较大小可得x,y,z,其组合数为?。3?n?1?n?1?n?1? 所以满足题意的x,y,z的组合数为?n?1?+?n?1?+?2?。 ?3?3? ?2?3?2? ?n?1?n?1? 由于这两种方法是等价的，故可得|t|?k2?2
19、?。证毕。 k?1?2?3? n 1.24题 a=(a, b)|a, bz, 0a9,0b5 (a) 求x-y平面上以a作顶点的长方形的数目. (b) 求x-y平面上以a作顶点的正方形数目. 解(b)：如下图(b)，网格左边是b的取值，下面是a的取值。网格里是x-y平面上对应每个顶点a(a,b)所得的正方形的数目。 1.26题 s=1,2,，1000，a,bs,使ab0 mod 5,求数偶a,b的数目 解：根据题意，ab可以整除5，2*c（200，1）*1000=400000 1.25题 平面上有15个点p1,p2。15，其中p1p2p3p4p5共线，此外不存在3点共线的。(1)求至少过15个
20、点中两点的直线的数目 (2)求由15个点中3点组成的三角形的数目 解：1)由题意知：p1p2p3p4p5共线，此外不存在3点共线的，所以与这五点分别相连的其他的十点的直线数目为：5*10=50。另外十个点两两相连得直线数目为：c102=45 又因为p1p2p3p4p5共线，所以可算作一条至少2点相连的直线 所以至少过15个点中两点的直线的数目=50+45+1=96 2)有三种情况 a：没有p1p2p3p4p5这五个点的三角个数：c103=120 b：有这五个点的其中一个点：5*c102 225 c：有着五个点的两个点：10*c52=100 由15个点中3点组成的三角形的数目=425 故数目为c
21、(15,2)-c(5,2)+1 (b) c(5,0)c(10,3)+c(5,1)c(10,2)+c(5,2)c(10,1) 1.27 题 6位男宾，5位女宾围一圆桌而坐，（1）女宾不相邻有多少种方案？（2）所有女宾在一起有多少种方案？（3）一女宾a和两位男宾相邻又有多少种方案？ 解 ：（1）若5位女宾不相邻，先考虑6位男宾围圆桌而做的方案数，然后女宾插入 q（6，6）*6*5*4*3*2=86400（2）把5位女宾看成一个整体，然后插入 q（6，6）*6*p(5,5)=86400（3）c（5，1）*c（6，2）*q（8，8）=194000 c(5,1)*c(6,2)*c(5,2)*p(4,2)
22、*7！ 1.28题 k和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数。 解：若每个圆桌的的人数相等，则每个桌子有n个人。因为圆周排列的个数为因此本题的结果为 p r (kn)!(kn)! ?k。 n?n?nn 1.29 题 从n个对象中取个r做圆排列，求其方案数目。1=r=n 解：c(n,r)*q（r,r）=c(n,r)*(r-1)! 1.31题试证任意r个相邻数的连乘：(n?1)(n?2)?(n?r) 被r！除尽.【篇二：组合数学+卢开澄版+答案第四章】 x是群g的一个元素，存在一最小的正整数m，使xm=e，则称m为x m n m?n m ,等式右边x xx nmm?n ，?ab?
23、ba，即所有 的阶，试证： c=e,x,x2, ,xm-1 证： x是g的元素，g满足封闭性所以，xk是g中的元素 cg 再证c是群： xac, (xa)-1= xb=xm-a 4.3设g是阶为n 的有限群，则g的所有元素的阶都不超过n. 证明：设g是阶为n 的有限群，a是g中的任意元素，a的阶素为k， 则此题要证k?n 首先考察下列n+1个元素 a,a,a,a,.a. 234n?1 由群的运算的封闭性可知，这n+1个元素都属于g,，而g中仅有n 个元素，所 以由鸽巢原理可知，这n+1个元素中至少有两个元素是相同的，不妨设为 a i i ? a i i?j （1?j?n） j a ? a?a
24、j j 由群的性质3可知，a是单位元，即a=e，又由元素的阶数的定义可知，当a为k阶元素时a=e，且k是满足上诉等式的最小正整数，由此可证k?j?n k4.4 若g是阶为n的循环群，求群g的母元素的数目，即g的元素可表示a的幂： a,a2.an 所以群g中母元素的数目为n(1-1/p1)(1-1/pk)个. 4.5 证明循环群的子群也是循环群 证明：设h是g=a的子群，若h=e,显然h是循环群，否则取h中最小的正方幂元am，下面证明am是h的生成元,易见am?h，只要证明h中的任何元素都可以表成am的整数次方，由除法可知存在q和r,使得l=qm+r,其中0?r?m-1,因此有ar=al?qm，
25、因为am是h中最小的正方幂元，必有r=0,这就证明出 a l =amq?am证明完毕。 4.6 若h是g的子群，x和y是g的元素，试证xh?yh或为空，或xh?yh 4.7若h是g的子群,|h|=k,试证： |xh|=k 其中x?g. 证明：h是g的子群，x?g |xh|k 如果|xh|k,则必存在a,b?h,使得xa=xb, 因为且x?g所以存在逆元 x-1xa=x-1xb a=b |h|k 又|h|=k |xh|=k .4.8 有限群g的阶为n，h是g的子群，则h的阶必除尽g的阶。 答案：已知|g|=n, |h|=|g| m r 设g=a0,a1,a2.an?1， h=b0,b1,b2.b
26、n?1 因为h是g的子群，所以在h中的一个(bm)r一定在g中对应一个am使得 m (b)?a ， 所以有brm?am，则rm一定是m的倍数，所以则h的阶必除尽g的阶。 49 g是有限群，x是g的元素，则x的阶必除尽g的阶。解：证： 设|g|=g,则x,x2,x3,?,xg?1中必有相同元。设xk?xl, 1?k?l?g?1，则xl?k?e，1?l?k?g。 对于给定的x，存在最小的正整数r，使得xr?e。于是h?x,x2,x3,?,xr是g 的子群， 若h?g，则?a?h，显然，h?ha?，h?ha?2r。 若h?ha?g， 则 2r?g,r|gr(k?1)?g ，否则?b?h?ha，hb?
27、(h?ha)?。 于是h?ha?hb?g，r|g。证毕。 4.10 若x和y在群g作用下属于同一等价类，则x所属的等价类ex，y所属的等价类ey有 |ex| = |ey| 解：因为x和y在群g作用下属于同一等价类，所以x和y在群g作用下存在置换p1使x和y互相转变，即 ex = ey=x,y 所以|ex| = |ey|。置换群: 格式: (1)9 ,1个.(1)3(2)3,4个.(1) (4)2,2个.(1)(2)4,1个 =(36+24+4)/8=8 其中划横线为红色,其它为蓝色.共8种着色方案. 4.12：试用burnside引理解决n个人围一圆桌坐下的方案问题。 解： 图一c1 如图：
28、n个人围成一个圆桌的所有排列如上图所示。一共n!个。 旋转360/i，i=n,n-1,n-2,1； 得到n种置换 当且仅当i=1的置换（即顺时针旋转360/1度：p1=(c1)(c2)(cn!);） 时有1阶循环存在（因为只要圆桌转动，所有圆排列中元素的绝对位置都发生了变化，所以不可能有1阶循环存在）。 不同的等价类个数就是不同的圆排列个数，根据burnside引理， 所以一共有(n-1)!种排列。 4.13 对正六角形的6个顶点用5种颜色进行染色，试问有多少种不同的方案，旋转使之重合作为相同处理 解：首先对每个顶点进行编号，分别为1，2，3，4，5，6，根据旋转的角度不同，共可以旋转6次，得
29、到不同的旋转方式 c(1)=6 4?5? 6旋转0度： 1?1?2?3? 旋转60度： 2?123456? c(1)=1 旋转120度：3?135?246? c(1)=2 旋转180度：4?14?25?36? c(1)=3 旋转240度：5?153?264? c(1)=2 旋转300度：6?165432? c(1)=1 所以g=6，根据polya定理，m=5， l?11g ?mc(1)?mc(2)?.?mc(6)? ? ? 612321 ?5?5?5?5?5?5?6 ?2635 故一共2635种涂色方案 4.15 对一个正六面体的8个顶点，用y和r两种颜色染色，使其中有5个顶点用色y，其余3个顶点用色r，求其方案数。 解： 相当于4.7节中例2中求b5r3的系数，为c(8,5)+8c(2,1)/24=3【篇三：李凡长版 组合数学课后习题答案习题4】1. 求下列数列的生成函数： （1）0,1,16,81,n4, 解：gk= 4 x(1?11x?11x2?x3) 5 （1?x） ?3?4?n?3?（2）?,?,?,? 333? ?n?3?1解：g?=?(1?x)4 n? （3）1,0,
