组合数学第四版答案.docx

资源描述

组合数学第四版答案.docx

《组合数学第四版答案.docx》由会员分享，可在线阅读，更多相关《组合数学第四版答案.docx（30页珍藏版）》请在冰点文库上搜索。

组合数学第四版答案.docx

组合数学第四版答案

【篇一：

组合数学参考答案（卢开澄第四版）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|?

|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0；由上题知当|a-b|=5时有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题m个男生，n个女生，排成一行，其中m,n都是正整数，若

（a）男生不相邻（m?

1）;（b）n个女生形成一个整体；（c）男生a和女生b排在一起；分别讨论有多少种方案。

解：

（a）可以考虑插空的方法。

n个女生先排成一排，形成n+1个空。

因为m?

1正好m个男生可以插在n+1个空中，形成不相邻的关系。

则男生不相邻的排列个数为

（b）n个女生形成一个整体有n！

种可能，把它看作一个整体和m个男生排在一起，则排列数有（m+1）!

种可能。

因此，共有n!

（m?

1）!

种可能。

（c）男生a和女生b排在一起，因为男生和女生可以交换位置，因此有2！

种可能，a、b组合在一起和剩下的学生组成排列有（m+n-1）！

（这里实际上是m+n-2个学生和ab的组合形成的）种可能。

共有组合数为2!

（m?

1）!

1.4题26个英文字母进行排列，求x和y之间有5个字母的排列数解：

c（24，5）*13！

1.5题求3000到8000之间的奇整数的数目，而且没有相同的数字。

1.7题试证：

（n?

1）（n?

2）?

（2n）被2n除尽。

证明：

因（2n）!

2n!

（2n?

1）!

（n?

1）（n?

2）?

（2n）n!

（n?

1）（n?

2）?

（2n）（2n）!

（2n?

1）!

nnn

2n!

因为（2n-1）!

是整数所以（n?

1）（n?

2）?

（2n）能被2n除尽。

1．8题求10和20的公因数数目。

404040403010306030402030

解：

因为10?

2*5?

2*5*520?

2*5?

2*2*5

4030

它们最大公因子为2*5转化为求最大公因子能除尽的整数个数，能除尽它的整数是2a*5b,0?

40,0?

根据乘法法则，能除尽它的数个数为41*31=1271

1.9题试证n的正除数的数目是奇数。

证明：

设有0?

n,n?

n2,则一定有表达式n?

b，

则可知符合范围的a和b必成对出现，所以为偶数。

又当a=b=n时，表达式n=a?

b仍然成立。

所以n的正除数的数目是―偶数?

1‖为奇数。

1.10题证任一正整数n可唯一地表成如下形式:

证：

对n用归纳法。

0≤ai≤i,i＝1,2,…。

由假设对n-k!

命题成立，设

，其中ak≤k-1,，命题成立。

再证表示的唯一性：

设

不妨设aj＞bj,令j=max{i|ai≠bi}

（aj?

bj）?

（bi?

ai）?

bi?

ai?

（bi?

ai）?

矛盾，命题成立。

1.11题证明nc（n-1,r）=（r+1）c（n,r+1）,并给予组合解释.

证：

nc（n?

1,r）?

（n?

1）!

（r?

1）?

（r?

1）?

（r?

1）c（n,r?

1）

（n?

1）!

（r?

1）?

（n?

1）!

（r?

1）!

（n?

1）!

所以左边等于右边

组合意义：

等式左边：

n个不同的球，先任取出1个，再从余下的n-1个中取r个；

等式右边：

n个不同球中任意取出r+1个，并指定其中任意一个为第一个。

所以两种方案数相同。

1.12题证明等式：

kc（n,k）?

nc（n?

1,0）?

c（n?

1,1）?

c（n?

1,n?

1）?

n2?

右边?

证明：

等式左边?

1.13题有n个不同的整数，从中间取出两组来，要求第1组的最小数大于另一组的最大数。

解题思路：

（取法由大到小）

第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）?

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时，后面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份，要求是每份至少有一个球。

如下图所示：

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个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？

解：

要求空盒不相邻，这样球的位置共有8种。

而不同标志的球的排列有p5?

。

所以共有8*5！

种排列。

a）1111

b）1111

在a）中剩下的一个球有四种位置，b）中剩下的一个球也有四种位置，两者合起来一共有8种1.17题n和r都是正整数，而且r?

n，试证下列等式：

（a）p?

1r?

（b）

（n?

1）p?

r（p

（c）

1r?

nn?

（d）

（e）

）

解：

（a）n

（n?

1）!

pr?

（n?

r）!

（n?

r）!

等式成立。

nn!

等式成立。

pr?

1pr（n?

1）!

（n?

r）!

1nnn（n?

1）!

（c）?

pn?

r（n?

1）!

（n?

r）!

pr等式成立。

（b）（n?

1）?

（n?

1）?

（d）

（n?

1）n!

（n?

1）!

（n?

1）!

pr?

rpr?

（n?

r）!

（n?

1）!

（n?

1）!

（n?

1）!

（n?

1）!

（n?

r）!

（e）利用（d）的结论可证明本题。

r（p

1r?

）?

rp?

1r?

2r?

1r?

2r?

1r?

1.19题n+m位由m个0，n个1组成的符号串，其中n≤m+1,试问不存在两个1相邻的符号串的数目。

解：

m个0进行排列，留出m+1个空挡，任选n个空挡放1，共有c（m+1,n）种方案.

1.21题一个盒子里有7个无区别的白球，5个无区别的黑球，每次从中随机取走一个球，已知前面取走6个，其中3个是白的，试问取第6个球是白球的概率。

解：

c（6,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）=1417502..甲单位出3个男同志，乙单位出2个男同志，从甲单位出1个女同志,从乙单位出1个女同志。

c（10,3）*c（15,2）*c（4.1）*c（10,1）=504000

3..甲单位出2个男同志，乙单位出3个男同志，从甲单位出2个女同志.c（10,2）*c（15,3）*c（4,2）=1228501+2+3即为所求，总的方案数为7686001.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），根据乘法法则:

560

（b）分两步走o（0,0）→a（3,2）,b（4,2）→p（8,5），根据乘法法则:

350

（c）分三步走:

o（0,0）→a（3,2）,a（3,2）→c（6,3）,c（6,3）→p（8,5）,根据乘法法则:

240

（d）ab封锁路径数加必经ab路径数即o（0,0）→p（8,5）的所有路径数有加法法则可得：

1287?

350?

937?

1.23题令s={1,2,…,n+1},n≥2,t={（x,y,z）|x,y,z∈s,xz,yz},试证:

|t|?

证明：

要确定x,y,z的取值，有两种方法，

种可能。

故|t|?

。

（2）由xz,yz，可以分为三种情况：

①x=yz,x,y可看作一个元素，这种情况等价于从1,2,…,n+1中取2个进行组合，然后比较大小，小者为x（y）,大者为z,其组合数为?

；?

②xyz,等价于从1,2,…,n+1中取3个进行组合，然后比较大小可得x,y,z,其组合数为?

；

③yxz,等价于从1,2,…,n+1中取3个进行组合，然后比较大小可得x,y,z,其组合数为?

。

所以满足题意的x,y,z的组合数为?

＝?

。

由于这两种方法是等价的，故可得|t|?

k2?

。

证毕。

1.24题a={（a,b）|a,b∈z,0≤a≤9,0≤b≤5}（a）求x-y平面上以a作顶点的长方形的数目.（b）求x-y平面上以a作顶点的正方形数目.

解（b）：

如下图（b），网格左边是b的取值，下面是a的取值。

网格里是x-y平面上对应每个顶点a（a,b）所得的正方形的数目。

1.26题s={1,2,……，1000}，a,b∈s,使ab≡0mod5,求数偶{a,b}的数目

解：

根据题意，ab可以整除5，2*c（200，1）*1000=4000001.25题平面上有15个点p1,p2。

。

Ｐ15，其中p1p2p3p4p5共线，此外不存在3点共线的。

（1）求至少过15个点中两点的直线的数目

（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*c102225c：

有着五个点的两个点：

10*c52=100由15个点中3点组成的三角形的数目=425故数目为c（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）*7！

1.28题k和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数。

解：

若每个圆桌的的人数相等，则每个桌子有n个人。

因为圆周排列的个数为因此本题的结果为

（kn）!

k。

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

等式右边xx＝x

nmm?

，?

ab?

ba，即所有

的阶，试证：

c=｛e,x,x2,…,xm-1｝证：

x是g的元素，g满足封闭性所以，xk是g中的元素c∈g

再证c是群：

xa∈c,（xa）-1=xb=xm-a

4.3设g是阶为n的有限群，则g的所有元素的阶都不超过n.

证明：

设g是阶为n的有限群，a是g中的任意元素，a的阶素为k，则此题要证k?

首先考察下列n+1个元素

a,a,a,a,..a..

234n?

由群的运算的封闭性可知，这n+1个元素都属于g,，而g中仅有n个元素，所

以由鸽巢原理可知，这n+1个元素中至少有两个元素是相同的，不妨设为

（1?

n）

由群的性质3可知，a是单位元，即a=e，又由元素的阶数的定义可知，当a为k阶元素时a=e，且k是满足上诉等式的最小正整数，由此可证k?

4.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?

m-1,因此有ar=al?

qm，因为am是h中最小的正方幂元，必有r=0,这就证明出

=amq?

{am}证明完毕。

4.6若h是g的子群，x和y是g的元素，试证xh?

yh或为空，或xh?

yh4.7若h是g的子群,|h|=k,试证：

|xh|=k其中x?

证明：

∵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|

设g={a0,a1,a2.......an?

1}，h={b0,b1,b2......bn?

因为h是g的子群，所以在h中的一个（bm）r一定在g中对应一个am使得

（b）?

，

所以有brm?

am，则rm一定是m的倍数，所以则h的阶必除尽g的阶。

4．9g是有限群，x是g的元素，则x的阶必除尽g的阶。

解：

证：

设|g|=g,则x,x2,x3,?

xg?

1中必有相同元。

设xk?

xl,1?

1，则xl?

e，1?

g。

对于给定的x，存在最小的正整数r，使得xr?

e。

于是h?

{x,x2,x3,?

xr}是g的子群，

若h?

g，则?

h，显然，h?

ha?

，h?

ha?

2r。

若h?

ha?

g，则

2r?

g,r|gr（k?

1）?

，否则?

ha，hb?

（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个人围一圆桌坐下的方案问题。

解：

图一

……………………………………

如图：

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次，得到不同的旋转方式

（1）=64?

6旋转0度：

旋转60度：

123456?

（1）=1旋转120度：

135?

246?

（1）=2旋转180度：

14?

25?

36?

（1）=3旋转240度：

153?

264?

（1）=2旋转300度：

165432?

（1）=1所以g=6，根据polya定理，m=5，

11g

（1）?

（2）?

...?

mc（6）?

612321

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,…}解：

g{k}=

x（1?

11x?

11x2?

x3）

（1?

x）

（2）?

333?

1解：

（1?

x）4n?

（3）{1,0,

展开阅读全文