组合数学1章课后习题答案

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

?n?1??n?1??n?1??n?1??n?1??+??+??=???2??。 ?2??3??3??2??3??n?1??n?1?2k?????2??。证毕。 k?1?2??3?n由于这两种方法是等价的,故可得|T|?1.24题(王卓)

A={(a,b)|a,b∈Z,0?a?9,0?b?5},

(a) 求x-y平面上以A作顶点的长方形的数目。 解:如图,

(a,b) 从图中可以看出,对于x-y平面上满足题意的任一顶点A(a,b),除它本身以外,横坐标取值有9种可能,纵坐标取值有5种可能。顶点A(a,b)与和它不在同一水平线或垂直线上的任一点(x,y)均可构成一个长方形。故满足要求的长方形的数目为9×5=45个。

(b) 求x-y平面上以A作顶点的正方形的数目。

解:如下图,网格左边是b的取值,下面是a的取值。网格里是x-y平面上对应每个顶点A(a,b)所得的正方形的数目。

1.25题(翟聪)

平面上有15个点P1,P2。。。P15,其中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*C102 225 c:有着五个点的两个点: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.26题(周英华)

S={1,2,??,1000},a,b∈S,使ab≡0 mod 5,求数偶{a,b}的数目

解:

根据题意,ab可以整除5, 2*C(200,1)*1000=400000 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个人。因为圆周排列的个数为因此本题的结果为

prnr

(kn)!(kn)!?k。

n?n?nn1.29 题(王星)

从n个对象中取个r做圆排列,求其方案数目。1<=r<=n

解:

c(n,r)*Q(r,r)

=c(n,r)*(r-1)! 1.30题(宗传玉)

(1)??r?1??, 1?r?n; ?r??=n/r?

?n????n?1??

?

(2) ??r??=(n-r+1)/r??r?1??, 1?r?n;

?n????n???(3) ??r?r??=n/(n-r)?

?n????n?1?

?? , 0?r?n; ??

解:

(1):

??r???n!/(r!(n-r)!)

?n????n?1? n/r??r?1??=n/r*((n-1)!/((r-1)!(n-r)!))= n!/(r!(n-r)!)=上式

??

所以两式相等

(2):

??r???n!/(r!(n-r)!)

?n????n?(n-r+1)/r??r?1??=(n-r+1)/r*((n!)/((r-1)!(n-r+1)!))= n!/(r!(n-r)!)=上式

??所以两式相等

(3): ??r???n!/(r!(n-r)!)

?n???n/(n-r)??

?n?1?

?=(n-1)!/(r!(n-r-1)!))= n!/(r!(n-r)!)=上式 ??r?

所以两式相等 1.31题(宗传玉)

证明:由 P(n ,r)=n*(n-1)?(n-r+1)

可知:(n+1)(n+2)?(n+r)= p(n+r,r)=c(n+r,r)* r!

所以 [(n+1)(n+2)?(n+r)]/r!= p(n+r,r)/ r!

= c(n+r,r)

故任意个相邻数连乘可被r!除尽。

1.32题(王星) 解:

满足y必须加在两个x之间应为 x y x y x 然后再把a ,b ,c ,d ,e ,f插入,a插入时有6种选择,b插入时有7种选择,c插入时有8种选择,d插入时有9种选择,e插入时有10种选择,f插入时有11种选择,由此可得排列数 N=11*10*9*8*7*6=11!/5! 1.33题(王丹竹)

已知r,n,k都是正整数,r?nk,将r个无区别的球放在n个有标志的盒子里,每盒至少k个球,试问有多少种方案? 解:

首先从r个球中取出nk个球放入n个盒中,因为球是无区别的。因此只有一种排列方案。剩下的球,每个球放的时候都有n中可能。因此方案数为n(r-nk).

1.34 题(孔令琦)

在r,s,t,u,v,w,x,y,z的排列中求y居于x和z中间的排列数 解 :

2*(5+4+3+2+1)*6!=2430

1.35题(周英华)

凸十边形的任意三条对角线不共点。试求这凸十边形的对角线相交于多少个点?

解:

根据题意,1个顶点有7条对角线,与它相邻的顶点有7条对角线,这样的点2个; 与它不相邻的顶点有6条对角线(有1条与它重复的),这样的点8个; 因此 (2* C(7,1)* C(7,1)+8* C(6,1)* C(7,1))*(9+1) =4340 1.36题(翟聪)

试证一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数 证明:

设N=P1a1 P2a2。。。Pnan,P1,P2,。。。Pn是n个不同的素数,每个能整除尽数n的正整数都可以选取每个素数Pi从0到ai次,即每个素数都有ai+1种选择,所以能整除n的正整数的数目为(a1+1)(a2+1)。。。(ai+1)个。而设M=N2=P12a1 P22a2。。。Pn2an,能被(2a1+1)(2a2+1)。。。2(ai+1)个整除。所以一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数。 1.37题(王卓) .给出

?n??r??n?1??r?1??n?2??r?2??n?m??r?m??n?r?1????????????????+++?+?m??0??m?1??1??m?2??2??0???m??=??m? ??????????????????的组合意义。

解: Y B(m,n+r+1-m)

P’

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4