《组合数学》测试题含答案

?n?l?Ai1?Ai2????Ail???k?????n?m? ??n?k?????ml?n?mAi????k??????1?i?1??l?1ml?i1??il???????m,llj?1Aij

?m??n?l?????1???k????k??l?0????(b) 设Ai为m?l个元中取m?i个，含特定元素的方案集；Ni为m?l个元中取m?i个的方案数，则：

?m?l?Ni???m?i??,???m?l?1??m?l?1??,A? Ai???m?i?1?i??m?i??

?????m?l?1?Ai?1?Ai???m?i????Ai?Ni?Ai,i?0,1,??,l

A0?N0?A0?N0?A1?N0?N1?A1?N0?N1?N2??????1?Nll??

88. 我们可以用母函数的方法求解：

G?x???1?x?x2?x3??1?x?x2?x3?x4??1?x?x2?x3?x4?x5?x6??1?3x????x???所以共有10种不同的写法

10

89. G?x???1?2x??1?3x?x?2?1?x?2x2?5x3?13x4?34x5?89x6??

90. 用母函数的方法：

G?x??x?x2?x3????x8

??x31?3x????28x6????x21?x3?3x4????28x9????x24??3?x31?x????x7???3

x9项的系数是28，所以共有28种取出3色均有9个球。

2n91. G?x??c?n,0??c?n,1?x?c?n,2?x??????1?c?n,n?x??1?x?

nn292. 令G?x??a0?a1x?a2x???

26 / 35

《组合数学》测试题含答案

因为an?an?2?0,a0?0,a1?2，由此推知a2?0,a3?2,a4?0,a5?2

223 作G?x??xG?x??a0?a1x??a2?a0?x??a3?a1?x????2x

即

?1?x?G?x??2x,G?x??2x??1?ix??1?ix?2

??i?1?ix?n?i?1?ix???i?in???i?xn

nn?0??? 所以 an?i?in???i? 93. 令

??G?x???x?3??x2?3x?2????1/2??3?x???1?3x/2?x2/2????1/2??4/?1?x??1/?1?x/2??????1/2?4??1/2??xnnn?0??

所以an???1/2?4??1/2? 于是知a50???1/2?4??1/2?n???50?

94. 因为第一个骰子可能出现的数字为2，4，6，第二个骰子可能出现的数字为1，3，5，

所以?ar?的母函数为G?x??x?x?x24?6??x?x3?x5?x3?2x5?3x7?2x9?x11

?95. 假设对二叉数的n个结点从1到n的加以编号，且令其前序序列为1，2，3……n。我们知道，不同的二叉数所得的中序序列不同。因此，不同形态的二叉数的数目恰好是前序序列均为1，2……n的二叉数所能得到的中序序列的数目。而中序遍历的过程实质上是一个结点进栈和出栈的顺序，二叉数的形态决定了其进栈和出栈的顺序，也确定了其结点的中序序列。如果我们用s表示入栈操作，x表示出栈操作,则一棵有n个结点的二叉数的中序遍历就有一个长度为2n的字符串对应，这个字符串p1p2??p2n满足以下条件：（1）共有n个s和n个x；(2)且在任何位置I，S的个数不少于X的个数。

于是在具有n个结点的不同形态的二叉数组成的集合T和长度为2n且满足以上条件的字符串集合p之间就建立起一一对应。而我们可以证明：集合p中有c?2n,n?/?n?1?个字符串，于是知有个结点的二叉数共有c?2n,n?/?n?1?种不同的形态。

事实上，共有c?2n,n?个长度为2n，且有n个S和n个X的字符串，但这些字符串中有许多不满足条件（2），即存在某个最小位置i（i<2n），使p1p2??pi?1中含有相同的S和X，但pi为X。令i?2k?1，于是在pi?1pi?2??p2n的2n?2k?1个字符中，有?n?k?个S, ?n?k?1?个X。令pi?1pi?2??p2n中的S变成X，X变成S，于是新得到的字符串

p1p2??pipi?1pi?2??p2n中有n?1个S，n?1个X，换句话说，不符合条件（2）的

27 / 35

《组合数学》测试题含答案

字符串对应于一个长度为2n，但有n?1个S，n?1个X的字符串。

k96. 对等边?1?x????1?c?n,k?x的两边在区间[0，1]积分

nk 左端=?1?x?nn?1/?n?1?|?1/?n?1?，

01右端=

n???1?c?n,k?xk?1/?k?1?|0?1?c?n,1?/2?c?n,2?/3?????1?c?n,k?/?n?1? k?0k1 所以 1?c?n,1?/2?c?n,2?/3??????1?c?n,n?/?n?1??1/?n?1?

n97. 解：

?x1?x2?x3?4?x14?x24?x34?4x13x2?4x13x3?4x23x3?4x23x1?4x33x1?4x33x2??6xx?6xx?6xx?12xx2x3?12xxx?12xxx2122212322232122132312

98．解：第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 种方案

99．解：相当于把n个小球放入6个不同的盒子里，为可重组合，即共有C(n+6-1,n)中方案，即 C(n+5,n)中方案。

19?1?20?22?5100. 解：因

?2?2?5?2?5?2?5?2?2所以部分数最小的19-完备分拆有如下3个：

19?4?4?4?4?2?1 19?10?2?2?2?2?1 19?10?5?1?1?1?1

101.

?kf?n???k2n??k??1?kini?k?k?ink?k?k?in?????????1???E2????1??E?1?i?i?0i?0?i???i?k?n?k?ik?k?n?k?i???????????1??2??1?1??i??i?i?0i?0????ki.

?k?k?i?2n???1???i??2???1?i?0??kin?k?k????i??i?0??k?2n?2?1????1?kn?k2k?2n???1?n?k2k102. 解：设所求为N，则N是

A?t??t?t3?t5???1?t2?t4???1?t4?t8???

展开式中t的系数，且

17??????28 / 35

《组合数学》测试题含答案

A?t??t1?t2

???1?t??t?1?t??1?t??k?2????t?2t?t????2?t?24?1224335?k?0

4k??因为1?4k?17的解为k?4,3?4k?17无整数解，5?4k?17的解为k?3，所以 N???2?

四、证明题

1. 排列n(n-1)…2·1是有逆序n(n-1)/2。因为2有1个逆序，3有2个，…，n有n-1

个，所以总的最大逆序数为1+2+…+(n-1)=n(n-1)/2 2. 因为C(p,i)=p(p-1)…(p-i+1)/(i·(i-1)…2·1),又因为p是素数，而p>i，所以p不能整除i，i-1,…2,1。于是(p-1)…(p-i+1)/(i·(i-1)…2·1)一定是整数，因而p·(p-1)…(p-i+1)/(i!)必定是p的倍数，所以p能整除C(p,i)。 3. 因为(1+1)∧(2n)=2∧(2n)=4∧n,又因为

(1+1)∧(2n+1)=C(2n+1,0)+C(2n+1,1)+…+C(2n+1,2n)+C(2n+1,2n+1)

因为C(2n+1,0)+C(2n+1,2)+…+C(2n+1,2n)=C(2n+1,1)+C(2n+1,3)+…+C(2n+1,2n+1) 所以(1+1)∧(2n+1)=2(C(2n+1,0)+C(2n+1,2)+…+C(2n+1,2n))

即C(2n+1,0)+C(2n+1,2)+…+C(2n+1,2n)=(1+1)∧(2n)=2∧(2n) =4∧n 4. 证明：右边=(k+1)·C(n,k+1)+k·C(n,k)

=(k+1)·n!/((k+1)!(n-k-1)!)+k·n!/(k!(n-k)!) =n!/(k!(n-k-1)!)+k·n!/(k!(n-k)!)

=[n!/(k!(n-k)!)(n-k+k)=n·n!/(k!(n-k)!) =n·C(n,k)=左边

5. 证明：左端=c(m,m)+c(m+1,m)+…+c(n,m)=c(m,0)+c(m+1,1)+…+c(m+(n-m),n-m)

=c(n+1,n-m)=c(n+1,m+1).这里用到了等式3，令m=n，n-m=r即可。

6. 证明：

左式=C(n,0) ·C(n,0)+C(n,1)C(n,1)+…+C(n,n)C(n,n) =C(n,0)C(n,n)+C(n,1)C(n,n-1)+…+C(n,n) ·C(n,0) =在n个蓝球和n个红球中任取n个球的方案数 =C(2n,n)

2n

7. 令Ｇ(x)=F1x+F2x+…+Fnx+…

2

因为Ｆn=Fn-1+Fn-2,即Fn-Fn-1-Fn-2=0,所以｛Ｆn｝的特征方程为c(x)=x-x-1 。其根为α=（1+√5）/2，β=（1-√5）/2

nnn

于是G(x)=A/(1-α x)+B/(1-β x)=(A+B)+(Aα +Bβ)x+…+(Aα+Bβ)x+… 由此知 A+B=0 A=1/√5

29 / 35

?4?2??3?2??6??5??????2?????2?????2???25 ???????《组合数学》测试题含答案

Aα+Bβ=1 B=-1/√5 nn

所以 Fn=(α-β)/√5 .

8. 证明：假设n代表没有两人的朋友数相同，所以他们的朋友数必定为0，1，2，…，n-1

这n个不同的整数。也就是说他们中必定有1个代表A无朋友，而另一个代表B有n-1个朋友，但既然A无朋友，则B不可能是他的朋友，而如果B没有A这个朋友，则B不可能有n-1个朋友，于是产生矛盾，可见n个代表各自具有不同数目的朋友的假设是错误的，由此命题得证。

2

9. 用归纳法证明：当n=0时，左式=0=0,右式=0·1·1/6=0,命题成立。 假设当n≥0时对任意的m≤n命题均成立，则当m=n+1时

22222

左式=1+2+…+n+(n+1)=n(n+1)(2n+1)/6+(n+1)=(n+1)(n+2)(2n+3)/6 =(n+1)((n+1)+1)(2(n+1)+1)/6=右式,

222

命题也成立，所以对于任意的n≥0，1+2+…+n=n(n+1)(2n+1)/6。

10. 2n个人2人一组分成n组，排成二列纵队，每行左右不分，则其有

n

C(2n,2)?C(2n-2,2)…C(2,2)=(2n)(2n-1)/2?(2n-2)(2n-3)/2…2?1/2=(2n)!/2

n

种方案。所以（2n）!/2必定为整数。

11. 将等边三角形各边中点相连,将该三角形分成4个边长为1/2的小等边三角形,则5个点

必有2个点落在其中一个小三角形内,且此两点中至少有一点不在原三角形的边上,所以这两点的矩离必小于1/2.

12. 用归纳法证明,由F1=F2=1,Fn=Fn-1+Fn-2知F0=0

a) 当n?1时，左式=??

?F2?11?

??，右式=?F?10?1??

nF1??11?????10??，命题成立 F0????Fn??11????10?? Fn?1????b) 假设当n?1，对任意的m?n命题成立，则当m?n?1时

?11?左式=??10????n?1?11??11??Fn?1???10????10??????????Fn?Fn?1?Fn =??F?Fn?1?nFn?1??Fn?2????Fn???Fn?1Fn?1?? Fn?? 由此可知，对于任意的n?0,命题成立。

13. 证明：因为任一个整数除以10的余数只可能为0,1,…9,现有11个整数,故其中必有2

个数m,n它们的余数r1和r2相同,即m=10k1+r1,n=10k2+r2

于是,m-n=10(k1-k2)+r1-r2=10·(k1-k2)为10的倍数。

14．证明：将正方形划分为4个边长为1/2的小正方形，则５个点中必不２点取自同一个小正方形，小正方形内最长的线段均小于其对角线的长度√2 /2．因为这两条对角线的４个顶点中只有一个属于小正方形内部，所以由落在这个小正方形内的两点组成的线段的长度必定小于2/2.

15．证明：设H= {a1,a2,…ak},对任一 x∈G,若i≠j,则xai≠xaj,

-1-1-1

若不然，假设xai=xaj,在等式两边乘上x, 即xxai=xxaj,

于是得ai=aj,但已假设 i≠j,且Ｈ中无相同元素，所以xai≠xaj, 即｜xH|=|{xa1,xa2,…,xak}|=K．

16. 证明：令A＝｛(x1, y1)，(x２, y２)，…，(x５, y５)}。因为A中的点(xi，yi)（i＝１，

２，３，４，５）是格点，即xi和yi 均为整数，所以在这５个格点中必有３个格点的x坐标的奇偶性相同，不妨设x1, x2，x3均为偶数。于是在格点集B＝｛(x1, y1)，(x２,

30 / 35