组合数学作业1-8.doc

1．1） 在边长为1的等边三角形内任意放10个点，证明一定存在 两个点，其距离不大于1/3。
证：如图所示：

在三角形的边上加两个点等分每条边，把大三角形分别9个边长为1/3的小三角形。由鸽巣原理：10个点中一定存在两个点落于同一个小三角形，其距离不大于1/3。

2）在边长为1的三角形内放个点，则把三角形分割成n-1个小三角形。
由鸽巣原理可知：个点必有两点落于同一个小三角形内，则其距离不大于1/n.

2．证：…… m个数，i=1,2…..m.
设 0≤≤m-1
当=0时，存在一个整数可以被m整除。
当从1…..m-1这m-1个中取值，那么m个中只有m-1种可能，则鸽巣原理可知：必存在j和k，使得,j>k,即有

3.证：
∵有理数可由整数和分数组成。
∴当为整数时，存在以0为循环的循环小数。
∴当为分数时，若分数是有限的循环小数，则存在以0为循环的循环小数。
∴若分数是无限循环的循环小数，则肯定存在某一位后以某一位为循环的循环小数。

4．证：
设全部由7组成的N+1个数，7，77，777，……,7777。。。。77（N+1个7）
存在整数N，由7组成的数除以N，以代表N+1中的数。
即=Nq+ 0≤≤ N-1
则存在0….N-1这n个数，则鸽巣原理可知：必定存在两个数
使得 是N 的倍数
组合数学第2次作业
2．5
⑴ 证明在任意选取的n+1个正整数中存在着两个正整数，其差能被n整除。
解：设任意n+1正整数，任意取两个整数的差为=,i>j.差除以n的余数为。 ∴0≤≤n-1
如果存在i，使得=0.则可以被n整除，对所有i，i=1,2 。。。。n都有≠0
则这n个i中只能取1,2.。。。。n-1。这n-1种情况。由鸽巢原理可知，必存在i和j使得，i＞j，则有= 可以被n整除。
⑵证明在任意选取的n+2个正整数中存在着两个正整数，其差能被2n整除或者其和能被2n整除。
解：设任意n+2正整数，任意取两个整数的差为=,i>j. 差除以2n的余数为。 ∴0≤≤2n-1
如果存在i，使得=0.则可以被n整除，对所有i，i=1,2 。。。。2n都有≠0
则这2n个i中只能取1,2.。。。。n-1。这2n-1种情况。由鸽巢原理可知，必存在i和j使得，i＞j，则有= 可以被2n整除。

2.6某学生有37天的时间准备时间考试，根据她过去的经验至多需要复习60个小时，但每天至少要复习1小时。证明无论怎样安排都存在连续的若干天，使得她在这些天里恰好复习了13小时。
设是从第1天到第i天复习的总小时，i=1,2，。。。37.至多复习60个小时。
∴1≤。。。。≤60。
做序列：

这个序列也是严格单调上升的，且有+13≤60+13。考察下面的序列：

该序列有84个数，每个数都是小于等于73的正整数，由鸽巢原理可知，必存在i和j使得 (i>j）.令n=i-j,该学生在第j+1,j+2,…..j+n=i 的连续n 天中复习了13个小时。

(P34)3.7把q个负号和p个正号排在一条直线上，使得没有两个负号相邻，证明不同的排法有C（p+1，q）种。
证：先把p个正号排在一条直线上，那么就有p+1个间隔，那就可以把q个负号插进这p+1个位置，则就知道其不同的排法有C（p+1，q）种。
3.8（1）从整数1,2，、、、、、、，100中选出两个数，使得他们的差正好是7，有多少种不同的选法。
解：从整数1,2，、、、、、、，100中选出两个数，使得他们的差正好是7的两个数有1和8, 2和9, 3和10, 4和11，、、、、、、、、93和100，，则一共有93种选法。
（2）如果选出的两个数之差小于等于7，又有多少种选法？
解：如果选一个数为1的话，那另一个数就可以是2,3,4,5,6,7,8有7种
如果选一个数为2的话，那另一个数就可以是3,4,5,6,7,8,9有7种、、、、、、、、、、、、、、、、、、、、
如果选一个数是93的话，有94,95,96,97,98,99,100，也是7种
选94，那就有95,96,97,98,99,100 6种
选95，那就有96,97,98,99,100 5种
选96，那就有97,98,99,100 4种
选97，那就有98,99,100 3种
选98，那就有99,100 2种
选99，那就有100 1种
那把上面所有的选法加起来得：93×7+6+5+4+3+2+1=672
则从整数1,2，、、、、、、，100中选出的两个数之差小于等于7有672种选法。
3.20从整数1,2、、、、，1000中选取三个数使得它们的和正好被4整除，问有多少种选法。
解：将1,2、、、、1000都除以4，
A、余数为0的有4,8,12,16，、、、、、1000， 250个
B、余数为1的有1，5,9,13，、、、、997， 250个
C、余数为2的有2,6,10,14，、、、、、998， 250个
D、余数为3的有3,7,11,15，、、、、、9999， 250个
然后再从A,B,C,D中选取三个数可被4整除：
在A中取三个数，则有C（250，3）
在A,B,D中各取一个数，则有【C（250,1）】3
在A中取一个，在C中取两个；在B中取两个和在C中取一个；
在C中取一个，再在D中取两个,则有3C(250，2)C(250，1)
所以总选法是C（250,3）+【C（250,1）】3+3C（250,2）·C（250,1）
3.32设S={n1·a1，n2·a2，……，nk·ak}，问S的大小不同的各种组合的总数是多少？
解：当K=1时，S1={n1·a1}，S1的组合为∅，{a1}，{2·a1}，……，{n1·a1}，有n1+1个.
当k=2时，S2={n1·a1，n2·a2}，显然S1的组合都是S2的组合，如果对S1的组合加入a2，就可以构成S2的含a2的组合。S1的组合有n1+1个，对其中的每一个组合加入a2的方法有n2种，由乘法法则，S2中含a2的组合有（n1+1）·n2个。所以S2的组合有（n1+1）+（n1+1）·n2=（n1+1）（n2+1）个。
由归纳法不难证明S={n1·a1，n2·a2，……，nk·ak}的各种组合的总数是 （n1+1）·（n2+1）·……·（nk+1）.
P62
4.3
解：（1）、
∵要取的系数，则k=13.
∴的系数为：
（2）∵要取的系数，且
∴
则只能取k=10,取的系数为：

4.4

解：由二项式定理得：
（1）、
（2）、对任意的实数r求和
解：用任意的实数r求和
实数r的和=
4.7

方法一：∵ ∴……
=……
=……
又∵
∴……
=0

方法二：∵= =
由两边同时微分得：
令x=1时：左边=0，右边=
而又∵……=
∴……=0 可证！
4.16

由二项式定理得：
=
两边同时积分得：
—=
令x=-1时：左边= ，
右边==
∴ =
∴
= 可证！
4.22 用多项式定理展开
解：= ，
∴的取法有：004的3种，112的3种，220的3种和130的6种。
当为004时：有=
当为112时：有
++
=
………经计算得：

=++++6
+4
5.1在1和10000之间不能被4，5，6整除的数有多少个？
解：令P1, P2, P3, 分别表示一个整数能被4,5,6整除的性质.
设 S={x|x是整数۸1≤x≤10000}
Ai ={x|x∈S۸x具有性质Pi }, i=1,2,3.
则：|A1|=【10000 / 4】=2500
|A2|=【10000 / 5】=2000
|A3|=【10000 / 6】=1666
|A1∩A2|=【10000 / （4，5）】=【10000 / 20】=500
|A1∩A3|=【10000 / （4，6）】=【10000 / 12】=833
|A2∩A3|=【10000 / （5，6）】=【10000 / 30】=333
|A1∩A2∩A3|=【10000 / （4，5，6）】=【10000 / 60】=166
由定理得：
|1∩2∩3|
=10000 -（2500+2000+1666）+（500+833+333）-166
=5334
5.4确定S={ ∞ · a, 3 · b, 5 · c, 7 · d }的10 - 组合数.
解：令T={ ∞ · a, ∞ · b, ∞ · c, ∞ · d }，T的所有10- 组合构成集合W.则由定理3.7得
|W|=286
任取T的一个10- 组合，
如果其中b多于3个则称它具有性质P1，
如果其中c多于5个则称它具有性质P2，
如果其中d多于7个则称它具有性质P3.
不难看出所求的10- 组合数就是W中不具性质P1，P2，P3的元素个数.
令Ai={x|x∈W۸x具有性质Pi }，i=1,2,3.
|A1|=84
|A2|=35
|A3|=10
|A1∩A2|=1
|A1∩A3|=0 |A2∩A3|=0 |Ab∩Ac∩Ad|=0

由定理得：
|1∩2∩3|=286-(84+35+10)=158
5.5 1)确定方程X1+X2+X3=14的不超过8的非负整数解的个数.
解： 方程不超过8的非负整数解，则0≤x1≤8, 0≤x2≤8, 0≤x3≤8.
|S|=120
|A1|=21
|A2|=21 |A3|=21
|A1∩A2|=0 |A1∩A3|=0 |A2∩A3|=0 |A1∩A2∩A3|=0
由定理得：
|1∩2∩3|=120 -21*3=57
2) 确定方程X1+X2+X3=14的不超过8的正整数解的个数.
解： 方程不超过8的正整数解，则1≤x1≤8, 1≤x2≤8, 1≤x3≤8.
相当于取值为0≤x1≤7, 0≤x2≤7, 0≤x3≤7，
x1+x2+x3=11
|S|=78
|A1|=10
|A2|=10 |A3|=10
|A1∩A2|=0 |A1∩A3|=0 |A2∩A3|=0 |A1∩A2∩A3|=0
由定理得：
|b∩c∩d|=78-10*3=48
P86
5.7求集合｛1,2，…，n｝的排列数，使得在排列中正好有k个整数在它们的自然位置上（所谓自然位置就是整数i排在第i位上）
解：由题意可知，从n个数中取n-k个数后，再将n-k个数错位排列，则所求的排列数是：

=

5.8定义=1，用组合分析的方法证明
n！=
证：n！是对｛1,2…….，n｝进行全排列，

是对｛1,2…….n｝进行分类：
当{1,2,……,n}中有0个数错位排列，则排法为
当{1,2,……,n}中有1个数错位排列，则排法为
当{1,2,……,n}中有2个数错位排列，则排法为
……..
当{1,2,……,n}中有n个数错位排列，则排法为
由于加法法则｛1,2……n｝的排法总数为

所以：
5.9证明为偶数当且仅当n为奇数.
证：（反证法）
“”设n为偶数，则n为偶数，为奇数，即
为奇数，与题设为偶数矛盾，所以假设不成立。即n为奇数。
“”已知n为奇数，则n-1是偶数，为偶数。
综合上所述，为偶数当且仅当n为奇数可证。5.1在1和10000之间不能被4，5，6整除的数有多少个？
解：令P1, P2, P3, 分别表示一个整数能被4,5,6整除的性质.
设 S={x|x是整数۸1≤x≤10000}
Ai ={x|x∈S۸x具有性质Pi }, i=1,2,3.
则：|A1|=【10000 / 4】=2500
|A2|=【10000 / 5】=2000
|A3|=【10000 / 6】=1666
|A1∩A2|=【10000 / （4，5）】=【10000 / 20】=500
|A1∩A3|=【10000 / （4，6）】=【10000 / 12】=833
|A2∩A3|=【10000 / （5，6）】=【10000 / 30】=333
|A1∩A2∩A3|=【10000 / （4，5，6）】=【10000 / 60】=166
由定理得：
|1∩2∩3|
=10000 -（2500+2000+1666）+（500+833+333）-166
=5334
6.1 計算 f (0)―f(1)＋f(2) ―……＋f(n)
当n为偶数时：
f (0)―f(1)＋f(2) ―……＋f(n)
= f (0)＋f(0)+f(2)＋ ……＋f(n―2) 由性质2得：
=1+ f(n―2+1)= f(n―1)+1
当n为奇数时：
f (0)―f(1)＋f(2) ―……＋f(n)
= f (0)―f(1)＋f(2) ―……＋f(n-1)―f(n)+ f(n+1)―f(n+1)
= f (0)＋f(0)+f(2)＋ ……＋f(n―1)―f(n+1) 由性质2得：
=1+ f(n―1+1)―f(n+1)
=1+ f(n)―f(n+1)
= f(n―1)+1
6.2 证明下面的等式
⑴f(2n)
∵
∵
∴+
=
=
=
=
由性质6得：= f(2n)
方法二：直接由性质6得：令2n=(n-1)+(n+1)
∴ f[(n-1)+(n+1)]=f(n+1-1)f(n-1+1)+f(n+1-2)f(n-1)2
=
⑵=f(2n) (由第一小题已证出)
⑶
∵f(3n+2)=f(2n+1)f(n+1)+f(2n)f(n)
f(2n+1)= f(n)f(n+1)+f(n-1)f(n)
f(2n)= f(n)f(n)+f(n-1)f(n-1)
∴f(3n+2)=f(2n+1)f(n+1)+f(2n)f(n)
=[f(n)f(n+1)+f(n-1)f(n)]f(n+1)+[f(n)f(n)+f(n-1)f(n-1) ]f(n)
=
=
= =+

=
=
=

6.4定义级数且求
解：特征方程为：　∴
∴=+
∵
∴+=b ,+=a
解得：
=+

6.5 已知 满足递推关系 求
解
代入可求出：
6.5已知满足递推关系，
求和.
解：由已知得：，解得：.