第1章32 *
第2章4, 16, 20 *
第3章4, 5, 26 *
第4章8, 15, 23, 33 *
第5章可选: 27, 28
第6章3, 5, 17, 25 *
第7章6, 11, 21, 24, 38 *
第8章
第9章11, 12, 15, 16
第10章12, 17, 43, 46 *
第14章15, 20, 26, 32 *
第一章
1.32．证明：在具有奇数枚硬币且堆的数目是奇数的Nim取子游戏中，游戏人I总能够取胜。注：原版题目为证明若在一个Nim取子游戏中，有奇数枚硬币的堆的数目是奇数，则游戏人I总能够取胜。
证明：设共有k堆硬币，且每堆中硬币的个数分别为n1, n2,…, n k, 令a1, a2,…, a k分别表示n1, n2,…, n k的二进制表示的最低位。则a i=1当且仅当n i为奇数。由于有奇数个a i等于1，所以最低位是非平衡的。因此这是一个非平衡的Nim取子游戏。所以游戏人I总能够取胜。
第二章
2.4、证明：如果从{1，2，……，2n}中选择n+1个整数，那么总存在两个整数，它们之间的差为1。
证明一：设取到n+1个数a1 < a2 < … < a n+1. 若没有两个数的差为1，则对于任意1≤ i ≤ n，a i+1－a i ≥ 2. 于是a n+1 ≥ 2n + a1 ≥ 2n+1，矛盾。
证明二：将{1,2,…,2n}分成n组数：{1,2}, {3,4}, …, {2n-1,2n}. 由鸽巢原理，取出的n+1个数必有两个属于同一组。
2.16、证明，在一n>1个人中，存在两个人，他们在这人中有相同数目的熟人（假设没有人和他/她自己是熟人）。
证明：n个人中，每人认识的人数是0～n-1，但是若有一人A与0个人互相认识，则其它所有人至少与A不互相认识，所以不可能有人与n-1个人互相认识。即n个人认识的人数中不可能同时有0和n-1. n个人认识的人数只有n-1种值，所以存在两人在这人种有相同数目的熟人。
2.20、证明，r（3，3，3）<=17.
对于K17，任取其中一点P，与其他16点的连线中，根据鸽巢原理，至少有6条为红，或者至少有6条为兰，或者至少有6条为绿。
不妨取6条染成红，即16点中就有6点与P点连线为红。若这6点中有两点以红边相连，则这两点与A组成红三角形。若这6点中组成的K6中无红边，即只有兰和绿两种颜的边。根据K6—>K3，K3也知或者有一兰三角形或者有一绿三角形。
因此结论得证。
第三章排列与组合
4，下列各数有多少互异正因子。
1）34×52×76×11, 因子数为5×3×7×2=210
2) 620=2×2×5×31, 所以因子数为3×2×2＝12
3）1010=210510, 所以因子数为11×11＝121
5，确定成为下列各数的因子的10的最大幂。
1）50！
50中有10个5，2个25.所以，有10＋2＝12个0
2）1000！
1000中有200个5，40个25，8个125，1个625，有200＋40＋8+1＝249个0
26，确定多重集S＝{3a,4b,5c}的10排列的个数。
所有10组合即对应全排列数如下：
{a,4b,5c} 10!/(4!×5!)＝1260
{2a,3b,5c} 10!/(2!×3!×5!)=2520
{3a,2b,5c} 10!/(3!×2!×5!)=2520
{2a,4b,4c} 10!/(2!×4!×4!)=3150
{3a,3b,4c} 10!/(3!×3!×4!)=4200
{3a,4b,3c} 10!/(3!×4!×3!)=4200
S的10排列数为1260+2520+2520+3150+4200+4200=17850.
第四章习题
8.｛1，2，3，4，5，6｝有多少排列具有
ⅰ恰好15个逆序？
ⅱ恰好14个逆序？
ⅲ恰好13个逆序？
解：对于一个排列i1i2…i6, 令其逆序列为a1a2…a6, 则该排列的逆序数为：a1+a2+a3+a4+a5+a6;
其中各数满足：0≤a1≤5;0<=a2<=4;0≤a3≤3;0≤a4≤2;0≤a5≤1;a6=0;
则总的逆序数为：0≤ a1+a2+a3+a4+a5+a6≤15;
恰有15个逆序的排列为：1
恰有14个逆序的排列为：5
恰有13个逆序的排列为：4+C(5,2)=14
15.对于{x7,x6,…x1,x0}的下列每一个组合，通过使用基为2的生成算法确定其直接后继组
合。
ⅰ){x4,x1,x0}
ⅱ){x7,x5,x3}
ⅲ){x7,x5,x4,x3,x2,x1,x0}
ⅳ){x0}
解：ⅰ)写成基为2的形式：00010011
得其直接后继组合：00010100
组合为：{x4,x2}
ⅱ)写成基为2的形式：10101000
得其直接后继组合：10101001
组合为：{x7,x5,x3,x0}
ⅲ)写成基为2的形式：10111111
得其直接后继组合：11000000
组合为：{x7,x6}
ⅳ)写成基为2的形式：00000001
得其直接后继组合：00000010
组合为：{x1}
23.确定下列9阶反射Gray 码中9元组得直接后继
ⅰ)010100110
ⅱ)110001100
ⅲ)111111111
解：ⅰ)010100110中1的个数为4，是偶数
则其直接后继是：010100111
ⅱ）110001100中1的个数为4，是偶数
则其直接后继是：110001101
ⅲ）111111111中1的个数为9，是奇数
则其直接后继是：111111101
33.组合2489出现在{1,2,3,4,5,6,7,8,9}中4－组合的字典序的哪个位置？
解:2489在字典序下的序号为
⎪⎪⎭
⎫  ⎝⎛--⎪⎪⎭⎫  ⎝⎛--⎪⎪⎭⎫  ⎝⎛--⎪⎪⎭⎫  ⎝⎛--⎪⎪⎭⎫  ⎝⎛19928934942949=81 注：其中最后两项为0.
第6章作业
3. 求1~10000中既不是完全平方也不是完全立方的整数的个数。
解：令A={1~10000中的完全平方数}
B={1~10000中的完全立方数}
全集U={1~10000}
则|A|=[210000]=100, |B|=[310000]=21, |A ⋂B|=[610000]=4
所以既不是完全平方也不是完全立方的整数的个数为 |A ⋂B | = |U|-|A|-|B|+|A ⋂B|=10000-100-21+4=9883
5.
解：令全集U={(x 1, x 2, x 3, x 4)| x 1+x 2+x 3+x 4=10, x 1, x 2, x 3, x 4≥0}
A={(x 1, x 2, x 3, x 4)| x 1+x 2+x 3+x 4=10, x 1, x 3, x 4≥0, x 2≥5}
B={(x 1, x 2, x 3, x 4)| x 1+x 2+x 3+x 4=10, x 1, x 2, x 4≥0, x 3≥6}
C={(x 1, x 2, x 3, x 4)| x 1+x 2+x 3+x 4=10, x 1, x 2, x 3≥0, x 4≥8}
其中|U|=⎪⎪⎭
⎫  ⎝⎛+3310,|A|=⎪⎪⎭⎫  ⎝⎛+335,|B|=⎪⎪⎭⎫  ⎝⎛+334,|C|=⎪⎪⎭⎫  ⎝⎛+332, |A ⋂B|=|A ⋂C|=|B ⋂C|=|A ⋂B ⋂C|=0
本题所求10-组合的个数为 |A ⋂B ⋂C | =|U|-|A|-|B|-|C|+|A ⋂B|+|A ⋂C|+|B ⋂C|-|A ⋂B ⋂C|=⎪⎪⎭
⎫  ⎝⎛-⎪⎪⎭⎫  ⎝⎛-⎪⎪⎭⎫  ⎝⎛-⎪⎪⎭⎫  ⎝⎛353738313            =185
17. 解：令 U={S 的全排列}
A={3个a 连续出现的排列}
B={4个b 连续出现的排列}
C={2个c 连续出现的排列}
则 |U|=⎪⎪⎭
⎫  ⎝⎛++243243=9!/(3!4!2!)=1260  |A|=(1+4+2)!/(1!4!2!)=105
|B|=(3+1+2)!/(3!1!2!)=60
|C|=(3+4+1)!/(3!4!1!)=280
|A ⋂B|=(1+1+2)!/(1!1!2!)=12
|A ⋂C|=(1+4+1)!/(1!4!1!)=30
|B ⋂C|=(3+1+1)!/(3!1!1!)=20
|A ⋂B ⋂C|=(1+1+1)!/(1!1!1!)=6
于是同类型字母不能连续出现的排列数有
|A ⋂B ⋂C | =|U|-|A|-|B|-|C|+|A ⋂B|+|A ⋂C|+|B ⋂C|-|A ⋂B ⋂C|
=1260-105-60-280+12+30+20-6=871
25解：参考P117例，计算得
r 1=8, r 2=20, r 3=20, r 4=7, r 5= r 6=0
由定理6.4.1得排列数为
6!- 8×5!+20×4!-20×3!+7×2!=134
第七章的作业
6.
解：考虑n 个格子的染方案数
若第一个格子为红，则第二个只能为蓝，第3个格子既可以是红也可以是蓝，所以从第3个格子到第n 个格子的(n-2)个格子的染方案有h n-2种;
若第一个格子为蓝，则其后(n-1)个格子的着数为h n-1.
所以，h n = h n-1 + h n-2（线性齐次递推关系）
特征方程：x 2-x-1=0
得特征根：α=(1+sqrt(5))/2 β=(1-sqrt(5))/2
一般解：h n =c 1αn + c 2βn
由题，h1=2, h2=3
h0=c1+c2=h2-h1=3-2=1
h1= c1α+ c2β=2
解得，c1=α2/sqrt(5), c2=-β2/sqrt(5)
所以，h n=(αn+2 - βn+2)/sqrt(5)
11、
解：
特征方程：x2-6x+9=0
解得：x1=x2=3正则化一个五行五列的随机矩阵
一般解：h n = c13n+ c2 n 3n
特解：h n= a n + b代回方程，比较系数得
a=1/2, b=3/2 此时特解h n = (1/2)n+3/2
因此，h n = c1 3n+ c2 n 3n+(1/2)n+3/2
代入初始条件，
h0 = c1+3/2=1
h1 =3c1+3c2+1/2+3/2
解得，
c1=-1/2
c2=-1/6
所以，
h n = (-1/2)*3^n+(-1/6)*3^n+(1/2)*n+3/2
24、
解：
(1)g(x)=(x+x^3+x^5+……)^4
=x^4/[(1-x^2)^4]
(2)g(x)=(1+x^3+x^6+……)^4
=1/[(1-x^3)^4]
(3)g(x)=1*(1+x)*(1+x^2+x^3+x^4+……)^2
=(1+x)/[(1-x)^2]
(4)g(x)=(x+x^3+x^11)* (x^2+x^4+x^5)* (x+x^3+x^11) *(x+x^3+x^11)
=x^5 * (1+x^2+x^10)^3 * (1+x^2+x^3)
(5)g(x)=(x^10+x^11+x^12+……)^4
=x^40/[(1-x)^4]
38
g(e)(x)=(1+x^2/2!+ x^4/4!……)*( x+x^3/3!+ x^5/5!……)*( 1+x^2/2!+ x^3/3!……)^2 =(e x+e-x)/2 (e x-e-x)/2 e x e x
=(e4x-1)/4
=1/4*∑x^n/n!*(4^n)-1/4
所以，
h n = (1/4)*4^n=4^(n-1), n≥1
h0=0

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。