组合数学作业
第一章引言
Page 13, ex3,4,7,30
ex3. 想象一座有64个囚室组成的监狱，这些囚室被排列成8 8棋盘。所有相邻的囚室间都有门。某角落处意见囚室例的囚犯被告知，如果他能够经过其它每一个囚室正好一次之后，达到对角线上相对的另一间囚室，那么他就可以获释。他能获得自由吗？
解：不能获得自由。
方法一：对64个囚室用黑白两种颜色染色，使得横和竖方向相邻的囚室颜色不同。则对角线上两个囚室颜色为同黑或同白。总共偶数个囚室，若能遍历且不重复，则必然是黑出发白结束，矛盾。
方法二：64个囚室，若要经过每个囚室正好一次，需要走63步，即奇数步。
不妨假设该囚犯在第1行第1列，那么到第8行第8列，横着的方向需要走奇数步，竖着的方向需要走奇数步，即总共需要偶数步。
所以不能恰好经过每个囚室一次到达对角线上的囚室。
ex4. (a) 设f(n)是用多米诺牌(2-牌)对2×n棋盘作完美覆盖的个数。估计一下f(1),f(2),f(3),f(4)和f(5). 试寻找(或证明)这个计数函数f满足的简单关系。利用这个关系计算f(12)。
(b) 设g(n)是用多米诺牌(2-牌)对3×n棋盘作完美覆盖的个数。估计g(1),g(2),…,g(6).
解：(a)
f(1)=1, f(2)=2, f(3)=3, f(n+2)=f(n+1)+f(n)
f(4)=f(3)+f(2)=5,
f(5)=f(4)+f(3)=8
f(6)=f(5)+f(4)=13
f(7)=f(6)+f(5)=21
f(8)=f(7)+f(6)=34
f(9)=f(8)+f(7)=55
f(10)=f(9)+f(8)=89
f(11)=f(10)+f(9)=144
f(12)=f(11)+f(10)=233
(b) g(1)=0, g(2)=3, g(3)=0, g(4)=9+2=11, g(n+4)=4g(n+2)-g(n), g(5)=0, g(6)=41.
ex7. 设a和b是正整数，且a是b的因子。证明m×n棋盘有a×b的完美覆盖当且仅当a 既是m又是n的因子，而b是m或n的因子。(提示: 把a×b牌分割成a个1×b牌。)
解：充分性。当a既是m又是n的因子，而b是m或n的因子，则m×n棋盘有a×b的平凡完美覆盖。
必要性。假设m×n棋盘有a×b牌的完美覆盖。则m×n棋盘必有b牌的完美覆盖。根据书中的定理，b是m的因子或n的因子。
下面证明a既是m的因子又是n的因子。
方法一: 因为a是b的因子，所以a×b牌可以分割成b/a个a×a牌。m×n棋盘有a×a的完美覆盖，则必然有a×a牌的完美覆盖。而a×a牌是正方形的，所以只有唯一的一种平凡覆盖方式。从而m是a的倍数，n也是a的倍数。
方法二: 因为a是b的因子，不妨设b=ka。由m×n棋盘有a×b牌的完美覆盖，可任取一个完美覆盖。设第一行的n个方格由p个a×b牌和q个b×a牌盖住，则有n=pb+qa=(pk+q)a，所以n是a的倍数。同理，m也是a的倍数。
ex30. 考虑堆的大小分别为10,20,30,40,50的5堆Nim 游戏。这局游戏是平衡的吗？确定玩
家I 的第一次取子方案。
解：将10,20,30,40,50用二进制表示
目标 取出个数
10: 0 1 0 1 0 10000 ×
20: 1 0 1 0 0 1110 110=6
30: 1 1 1 1 0 100 11010=26
40: 1 0 1 0 0 0 110010 ×
50: 1 1 0 0 1 0 101000 1010=10
平衡 0 1 1 0 1 0
游戏是不平衡的。从上表可以得到，可从20个堆中取6个，从30个堆中取26个，从50
个堆中取10个。
第2章 排列组合
P37: ex5,11,27,32,51
ex5. 确定作为下列各数的因子的10的最大幂(等价于用通常的10进制表示时尾部0的个数)：(a) 50!, (b) 1000!
解：(a) ?50/5?=10, 即1~50中有10个5的倍数。?50/25?=?10/5?=2，即1~50中有2个25的
倍数。从而50!的因子的5的最大幂是10+2=12。因为2的最大幂比5大，所以5的因子个
数决定10的最大幂。
(b) 同理，1000/5=200, 200/5=40, 40/5=8, ?8/5?=1, ?1/5?=0，所以1000!的因子的10的最大幂
等于200+40+8+1=249.
ex11.从数集{1,2,…,20}中形成3个数的集合，如果没有2个相连的数字在同一个集合中，那
么能形成多少个3个数的集合。
解法一：任选3个数有C(20,3)种方案。两数相邻另一个分离：1,2和19,20这两个相邻数对，
各对应另一不相邻数有17种选择；2,3到18,19共17种相邻数对，各对应另一不相邻数有
16种选择。三数相邻有18种选择。
202171716188163??-?-?-= ???
. 解法二：任选3个数有C(20,3)种方案。取两个相邻数有19种选择，另一个与已取出两数不
同有18种选择。每三个相邻的数在前一步被计数了两次，需要补回一次。
201918188163??-?+= ???
； 解法三：先放17个0排成一排。再在18 个空挡中放3个1，有C(18,3)种方法。在17个0
和3个1形成的排列中，数1所在的位置abc ，即得到3个不相邻的1到20中的数。
解法四：令3个数从小到大排列为a,b,d ，满足a+1
为从1到18中的数，且无不相邻限制。
188163??= ???
ex27. 5个没有区别的车放在8?8棋盘上，使得没有车能够攻击别的车并且第一行和第一列都不空的放置方式有多少?
解：
方法一: 5个横坐标的选择方案有C(7,4)种，因为第1列必选；5个纵坐标的选择方案有C(7,4)种，因为第一行必选；横纵坐标的配合有5!种，因为横坐标固定，纵坐标全排列。所以总的方案数为C(7,4)?C(7,4)?5!=147000.
方法二: 分两种情况：一是选第一行第一列，其它4个在其它7行7列；有C(7,4)?C(7,4)?4!种方案。二是第一行2至8列中选一个，第一列2至8行中选一个，其它3个在其它6行6列；有7?7?C(6,3)?C(6,3)?3!。
总方案数为C(7,4)?C(7,4)?4! + 7?7?C(6,3)?C(6,3)?3! = C(7,4)?C(7,4)?5! = 147000。
ex32. 确定下面的多重集合的11排列的数目：S={3?a,4?b,5?c}。
解：多重集S={3?a,4?b,5?c}的11排列可分为3个部分：
{2?a,4?b,5?c}：
11!
6930
2!4!5!
=；
{3?a,3?b,5?c}：
11!
9240
3!3!5!
=；
{3?a,4?b,4?c}：
11!
11550
3!4!4!
=；
共有6930+9240+11550=27720个排列。
ex37. 一家面包店销售6种不同类型的酥皮糕点。如果该店每种糕点至少有一打，那么可能配置成多少打不同类型的酥皮糕点？如果在一盒中每种糕点至少有一块，又能有多少打？解：
(1) 12个球与5个间隔的全排列有C(12+5,5)个，所以总共可以配成C(17,5)种12个一盒的酥皮蛋糕盒。
(2) 每种蛋糕至少一块，则盒中已有6块蛋糕。还需要放入6块蛋糕。等价于6个球与5个间隔全排列，有C(6+5,5)种方案。所以总共可以配成C(11,5)种12个一盒且每种蛋糕至少有一个的酥皮蛋糕盒。
ex51. 考虑大小为2n的多重集合{n?a,1,2,3,…,n}，确定它的n组合数。
解：令S={n?a,1,2,3,…,n}.
方法一：{1,2,…,n}中取k个有C(n,k)种方案，再取n-k个a得到S的n组合。所以方案数是C(n,0)+C(n,1)+…+C(n,n)=2n.
方法二：{1,2,…,n}的全体组合有2n个，{1,2,…,n}的任何一个组合配上相应个数的a可以得到S的一个n组合。
ex52. 考虑大小为3n+1的多重集合{n?a,n?b,1,2,3,…,n+1}，确定它的n组合数。
解：在{1,2,…,n+1}中取k个有C(n+1,k)种方案，n个a和n个b中取n-k个组合有C(n-k+1,1)=n-k+1种方案。
方法一: C(n+1,k)?(n-k+1)=(n+1)?C(n,k)，对k从1到n求和得到(n+1)?2n种方案。
方法二: 因为(x+1)n+1=ΣC(n+1,k)x n-k+1，两边同时对x求导，得到(n+1)(x+1)n=ΣC(n+1,k)?(n-k+1)x n-k。令x=1，便得到ΣC(n+1,k)?(n-k+1)=(n+1)?2n。
第3章鸽巢原理
P50: ex4,7,11,13,16
ex4. 证明：如果从集合{1,2,…,2n}中选择n+1个整数，那么总存在两个数它们之间相差1.证明：将2n个数分成n个集合：{1,2},{3,4},…,{2n-1,2n}。那么任取的n+1个数至少有两个在同一个集合中，它们之间相差1.
ex7. 证明：对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。
证明：构造51个鸽巢：模100余0的一个鸽巢；模100余1和余99的一个鸽巢；模100余2和余98的一个鸽巢；模100余3和余97的一个鸽巢；以此类推…；模100余49和余51的一个鸽巢；模100余50的一个鸽巢。52个数，至少有两个在同一个鸽巢。若这两个数模100同余，则两个数的差是100的倍数；若这两个数模100不同余，则这两个数的和是100的倍数。
ex11. 一个学生有37天来准备考试。根据以往经验，她知道她需要的学习时间不超过60小时。她还希望每天至少学习一个小时。证明，无论她怎么安排学习时间(每天学习的时间是整数小时)，都存在连续若干天，在此期间她恰好学习了13个小时。
证明：设ai是这名学生从第1天到第i天学习的总小时数，那么
0 13+ a1<13+ a2<…13+ a36<13+ a37<73 于是a1,a2,…,a36,a37和13+ a1,13+ a2,…,13+ a36,13+ a37共74个数取值在1到73之间。一定有两个数相同，且这两数一定是13+a i=a j。于是从第i+1天到第j天这名学生学习了13小时。 ex13. 设S是平面上6个点的集合，其中没有3个点共线。给由S的点所确定的15条线段着色，将它们或者着成红色，或者着成蓝色。证明：至少存在两个由S的点所确定的三角形或者是红色三角形或者是蓝色三角形。 证法一： 六个点ABCDEF至少形成一个同色三角形，设此三角形为ABC且为红色。 (1) 若DEF同色，则得到另一同色三角形。 (2) 否则DEF必有一条蓝色边，设为DE。考虑从D,E两点分别到A,B,C三点的连线。(2.1) 若D或E有两条红色边连到A,B或C，将得到另一红色三角形。 (2.2) 否则D,E都至少有两条蓝色边连接到A,B和C上。D,E必各有一条蓝色边连到A,B和C三点的同一点(设为C)上，则DEC是蓝色三角形。 证法二： 任相邻两条边给一个数，若同色则给1，否则给0。 (1) 任何一个同色三角形对应数1,1,1；任何一个不同色三角形对应数1,0,0。六点共有C(6,3)=20个三角形。 (2) 从一个点出发的边有5条，共10对，至少有4对同色，对应数的和大于等于4，所有点对应数的和大于等于24。 若没有同色三角形，则所有数的和是20；若只有一个同色三角形，则所有数的和是22. 所以至少有两个同色三角形。 ex16. 证明：在一群n>1个人中，存在两人，他们在这群人中有相同数目的熟人(假设自己 不是自己的熟人)。 证明：n个人，每人的熟人数记为a i，即a1,a2,…,a n，取值于0到n-1之间。由于有人认识0个人和有人认识n-1个人不会同时出现。所以这n个数的取值只有n-1种，从而必有两人熟人数相同。 第4章生成排列和组合 ex 6, 7, 23, 24, 33, 52 ex6. 确定{1,2,…,8}的下列排列的逆序列。(a) 35168274 (b)83476215 解：(a) 24040010 (b) 65113210 ex7. 构造{1,2,…,8}的排列，使得其逆序列是(a) 25502110 (b) 66142100 解：a) 48165723 b) 73658412 ex23. 确定下列9阶反射Gray码中9元组的直接后继 (a) 010100110 (b) 110001100 (c) 111111111 解：后继为(a) 010100111 (b) 110001101 (c) 111111101 ex24. 确定下列9阶反射Gray码中9元组的直接前趋 (a) 010100110 (b) 110001100 (c) 111111111 解：前驱为(a) 010100010 (b) 110000100 (c) 111111110 ex33.子集2489出现在{1,2,3,4,5,6,7,8,9}的4-子集的字典序的哪个位置上? 解：2489的位置为 975 81 443 ?????? --= ? ? ? ?????? ex52.验证二进制n元组a n-1a n-2…a0位于Gray码表的位置k处，其中k确定如下：对i=0,1,…,n-1，若a n-1+…+ a i是偶数则b i=0，否则b i=1，则有k=(b n-1…b0)2。 证明：为方便，记b n-1… b0=f(a n-1a n-2…a0)，其中对i=0,1,…,n-1，若a n-1+…+ a i是偶数则b i=0，否则b i=1。 数学归纳证法一： 当二进制位数1 n=时，公式成立； 假设当位数为1 n-时，公式成立，即a n-2…a0在Gray码表中位于k’处，k’=(c n-2…c0)2，其中c n-2…c0 = f(a n-2…a0)。 考虑n位二进制码a n-1a n-2…a0。当a n-1=0时，根据定义，b n-1=0，且b i=c i (i=n-2,…,0)；再根据Gray码的递归构造，以及a n-1=0，可知a n-1a n-2…a0在Gray码中的位置是 (c n-2…c0)2 = (b n-1…b0)2。 当a n-1=1时，根据定义，b n-1=1, 且b i=1- c i (i=n-2,…,0)。根据Gray码的递归构造，以及a n-1=1，可知a n-1a n-2…a0在Gray码中的位置是 2n - (c n-2… c0)2 - 1 = (1…1)2 - (c n-2… c0)2 = (b n-1…b0)2， 其中1…1是n-1个1。 数学归纳证法二： 考虑n阶反射Gray码。 (1) 在n 阶反射Gray 码中，第一个n 元组是0…0，对应f(0…0) = 0…0，满足位置关系，命 题成立。 (2) 假设n 元组a n -1a n -2…a 0 ≠10…0在Gray 码中的位置是(b n -1…b 0)2，其中b n -1…b 0 = f(a n -1a n -2…a 0)。 (2.1) 当b 0=0时，σ(a n -1a n -2…a 0)=0，a n -1a n -2…a 0的下一个Gray 码是将a 0改为1-a 0，即 120n n a a a --K 。它的位置是(b n -1…b 10)2+1=(b n -1…b 11)2， f(120n n a a a --K )=b n -1…b 11，满足位置 关系，命题成立。 (2.2) 当b 0=1时，σ(a n -1a n -2…a 0)=1。取j 为a n -1a n -2…a 0中从右往左若干个连续的0后面的第 一个1的位置，即a j a j -1…a 0=10…0。此时，b j =b j -1=…= b 0=1，b j +1=0。注意到a n -1a n -2…a 0下 一个Gray 码是110n j j a a a a -+K K ，其位置应该是(b n -1…b 0)2+1=(b n -1…b j +210…0)2。令c n -1…c 0 = f(110n j j a a a a -+K K )，则c j =c j -1=…= c 0=0，c j +1=1，c k =b k ，(k = j +2,…,n -1)，满足位置关系。 第6章 容斥原理 ex5, ex13, ex17, ex26, ex30 5. 确定多重集{∞?a,4?b,5?c,7?d}的10-组合个数。 解：令全集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|=1033+?? ???,|A|=533+?? ???,|B|=433+?? ???,|C|=233+?? ??? , |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|=138753333????????--- ? ? ? ????????? =185 13. 确定{1,2,…,9}的至少有一个奇数在它的自然位置上的排列数。 解：方法一 对于i=1,3,5,7，定义A i ={i 在位置i 上} A 1∪A 3∪A 5∪A 7∪A 9 = C(5,1)8!-C(5,2)7!+C(5,3)6!-C(5,4)5!+C(5,5)4! = 157824. 方法二 将计算没有奇数在自然位置上的问题转化为带禁止位置的排列，共5个禁止位置分布在对角 线上。 r 1=C(5,1), r 2=C(5,2), r 3=C(5,3), r 4=C(5,4), r 5=C(5,5), r 6=…= r 9=0. 9!-(9!- r 18!+ r 27!- r 36!+ r 45!- r 54!)= C(5,1)8!-C(5,2)7!+C(5,3)6!-C(5,4)5!+C(5,5)4!=157824. 17. 确定多重集S={3?a,4?b,2?c}的排列数，其中，对每种类型的字母，同类型的字母不能连 续出现。(例如，abbbbcaca 是不允许的，但abbbacacb 可以。) 解：令U={S的全排列} A={3个a连续出现的排列} B={4个b连续出现的排列} C={2个c连续出现的排列} 则|U|=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. 26. 计算{1,2,…,6}的排列i1i2i3i4i5i6的个数，其中i1≠1,2,3，i2≠1，i3≠1，i5≠5,6，i6≠5,6。解： 带禁止位置的排列，放置方法数是6!-r15!+r24!-r33!+r42!-r51!， 由r1=9, r2=2?2+2+5?4=26, r3=4?4+5?2=26, r4=4?2, r5=0, r6=0, 得到排列数为6!-9?5!+26?4!-26?3!+8?2!-0?1!+0?0!=124. 30. 多重集{3?a,4?b,2?c,1?d}存在多少循环排列，对每种类型的字母，该类型的所有字母不连续出现？ 解： 方法一：固定d，其它元素排列与17题相同，所以有871种循环排列方式。 方法二： 令U={S的所有循环排列} A={3个a连续出现的循环排列} B={4个b连续出现的循环排列} C={2个c连续出现的循环排列} 则|U| = (3+4+2+1-1)!/(3!4!2!) = 9!/(3!4!2!) = 1260 |A| = (1+4+2+1-1)!/(1!4!2!) = 7!/(4!2!) = 105 |B| = (3+1+2+1-1)!/(3!1!2!) = 6!/(3!2!) = 60 |C| = (3+4+1+1-1)!/(3!4!1!) = 8!/(3!4!) = 280 |A?B| = (1+1+2+1-1)!/(1!1!2!) = 4!/2! = 12 |A?C| = (1+4+1+1-1)!/(1!4!1!) = 6!/4! = 30 |B?C| = (3+1+1+1-1)!/(3!1!1!) = 5!/3! = 20 |A?B?C| = (1+1+1+1-1)!/(1!1!1!) = 3! = 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. 31. 多重集S={2?a,3?b,4?c,5?d}存在多少循环排列，对每种类型的字母，该类型的所有字母不连续出现? 解: 令U={S的所有循环排列} A={2个a连续出现的循环排列} B={3个b连续出现的循环排列} C={4个c连续出现的循环排列} D={5个d连续出现的循环排列} 则|U| = (2+3+4+5-1)!/(2!3!4!5!) = 13!/(2!3!4!5!) = 180180 |A| = (1+3+4+5-1)!/(1!3!4!5!) = 12!/(1!3!4!5!) = 27720 |B| = (2+1+4+5-1)!/(2!1!4!5!) = 11!/(2!1!4!5!) = 6930 |C| = (2+3+1+5-1)!/(2!3!1!5!) = 10!/(2!3!1!5!) = 2520 |D| = (2+3+4+1-1)!/(2!3!4!1!) = 9!/(2!3!4!1!) = 1260 |A?B| = (1+1+4+5-1)!/(1!1!4!5!) = 10!/(1!1!4!5!) = 1260 |A?C| = (1+3+1+5-1)!/(1!3!1!5!) = 9!/(1!3!1!5!) = 504 |A?D| = (1+3+4+1-1)!/(1!3!4!1!) = 8!/(1!3!4!1!) = 280 |B?C| = (2+1+1+5-1)!/(2!1!1!5!) = 8!/(2!1!1!5!) = 168 |B?D| = (2+1+4+1-1)!/(2!1!4!1!) = 7!/(2!1!4!1!) = 105 |C?D| = (2+3+1+1-1)!/(2!3!1!1!) = 6!/(2!3!1!1!) = 60 |A?B?C| = (1+1+1+5-1)!/(1!1!1!5!) = 7!/(1!1!1!5!) = 42 |A?B?D| = (1+1+4+1-1)!/(1!1!4!1!) = 6!/(1!1!4!1!) = 30 |A?C?D| = (1+3+1+1-1)!/(1!3!1!1!) = 5!/(1!3!1!1!) = 20 |B?C?D| = (2+1+1+1-1)!/(2!1!1!1!) = 4!/(2!1!1!1!) = 12 |A?B?C?D| = (1+1+1+1-1)!/(1!1!1!1!) = 3!/(1!1!1!1!) = 6 于是同类型字母不能连续出现的排列数有 =13!/(2! 3! 4! 5!) - 12!/(3! 4! 5!) - 11!/(2! 4! 5!) - 10!/(2! 3! 5!) - 9!/(2! 3! 4!) + 10!/(4! 5!) + 9!/(3! 5!) + 8!/(3! 4!) + 8!/(2! 5!) + 7!/(2! 4!) + 6!/(2! 3!) - 7!/5! - 6!/4! - 5!/3! - 4!/2! + 3! =144029 第7章递推关系和生成函数 ex. 9,46,47; 13,17,25, 9. 令h n等于1行n列棋盘的方格能够用红、白和蓝色着色并使得没有两个涂成红色的方格相邻的着色方案数。求出并验证h n所满足的递推关系。然后找出h n的公式。 解： 棋盘的第一个格子有3中着色方法： (1) 着红色，则第二个格只能着蓝色或者白色，此时的方案数为2h n -2； (2) 着蓝色或者白色，此时的方案数为2h n -1； 因此, h n = 2h n -1+ 2h n -2, 且h 0 = 1, h 1 = 3. 求h n ： 特征方程：x 2-2x -2=0 解得：x 1, x 2=1 则有：h n = c 1n + c 2(1n 代入初始条件， h 0 = c 1+c 2=1 h 1 =c 1)+c 2(1)=3 解得， c 1= 12+2=12- 因此, h n =11((22n n ++. 46. 求解非齐次递推关系h n = 6h n -1- 9h n -2+2n, (n ≥2), h 0 = 1, h 1 = 0. 解： 对于齐次递推关系：h n = 6h n -1- 9h n -2 特征方程：x 2-6x+9=0 解得：x 1=x 2=3 一般解：h n = c 13n + c 2 n 3n 对于非齐次递推关系，其特解为：h n = a n + b 代回递推关系，比较系数得 a=1/2, b=3/2, 此时特解h n = (1/2)n+3/2 因此，h n = c 1 3n + c 2 n 3n +(1/2)n+3/2 代入初始条件， h 0 = c 1+3/2=1 h 1 =3c 1+3c 2+1/2+3/2=0 解得， c 1=-1/2 c 2=-1/6 所以，h n = (-1/2-n/6)*3n +n/2+3/2. 47. 求解非齐次递推关系 h n = 4h n -1- 4h n -2+3n+1, (n ≥2), h 0 = 1, h 1 = 2. 解： 对于齐次递推关系：h n = 4h n -1- 4h n -2 特征方程：x 2-4x+4=0 解得：x 1=x 2=2 一般解：h n = c 12n + c 2n2n 对于非齐次递推关系，其特解为：h n = an + b 代回方程，比较系数得 a=3, b=13, 此时特解h n = 3n+13 因此，h n =(c 1+c 2n)2n +3n+13 代入初始条件， h 0 = c 1+13=1 h 1 =2(c 1+c 2)+3+13=2 解得， c 1=-12 c 2=5 所以，h n = (5n -12) *2n +3n+13. 13. 确定下列每个序列的生成函数 解： (a) g(x) = 1+cx+c 2x 2+…+c n x n +… = 1+cx+(cx)2+…+(cx)n +… = 1/(1-cx) (b) g(x) = 1-x+x 2-x 3+…+(-1)n x n +… = 1+(-x)+(-x)2+(-x)3+…+(-x)n +… = 1/(1+x) (c) g(x) = 2(1)012n n x x x n αααα????????-+++-+ ? ? ? ????????? L L = 2()()012n x x x n αααα????????+-+++-+ ? ? ? ????????? L L = (1-x)α (d) g(x) = 1+1/1!*x+1/2!*x 2+…+1/n!*x n +… = e x (e) g(x) = 1- x/1! +x 2/2! +…+(-1)n x n /n! +… = 1+(-x)/1! +(-x)2/2! +…+(-x)n /n! + … = e -x 17. 确定苹果、橘子、香蕉和梨的袋装水果的袋数h n 的生成函数，其中各袋要有偶数个苹果， 最多两个橘子，3的倍数个香蕉，最多一个梨。然后从该生成函数求出h n 的公式。 解：序列h 0,h 1,…的生成函数是 g(x) = (1+x 2+x 4+…) (1+x+x 2) (1+x 3+x 6+…) (1+x) = 1/(1-x 2)*(1+x+x 2)*(1+x)*1/(1-x 3) = 1/(1-x)2 =0(1)n n n x ∞ =+∑. 因此，h n =n+1. 17’. 确定苹果、橘子、香蕉和梨的袋装水果的袋数h n 的生成函数，其中各袋要有偶数个苹 果，至少两个橘子，3的倍数个香蕉，最多一个梨。然后从该生成函数求出h n 的公式。 解: 序列h 0,h 1,…的生成函数是 g(x) = (1+x 2+x 4+…) (x 2+x 3+…) (1+x 3+x 6+…) (1+x) = 1/(1-x 2) * x 2/(1-x) * 1/(1-x 3) * (1-x 2)/(1-x) = ) 1()1(232 x x x x ++- =??? ? ??---++---+--ααααx x x x x 1)1(3)1(3119132 =∑∞=+-??? ? ??++???? ??+-++-021223)1(3191n n n n n n x αα 其中i 2 321+-=α 所以??? ? ??++???? ??+-++-=+-21223)1(3191n n n n n h αα, 验证(h 0, h 1, h 2, h 3)=(0,0,1,2). 25. 如果偶数个方格被涂成红色以及奇数个方格被涂成白色，试确定用红、白、蓝和绿为1 行n 列棋盘的方格着色的方案数h n 。 解：设满足如题要求的1行n 列棋盘的方格着色的方案数为h n . 则序列h 0,h 1,…的指数生成 函数是 g (e)(x)= (1+x 2/2!+x 4/4!+…) (x/1!+x 3/3!+x 5/5!+...) (1+x/1!+x 2/2!+…) (1+x/1!+x 2/2!+…) = 1/4*(e x +e -x ) (e x -e -x )e x e x = 1/4(e 4x - 1) = ???? ??-∑∞=1!4410n n n n x =∑∞=-1 1!4n n n n x . 因此，h n = 4n -1(n ≥1), h 0 = 0. 26. 如果偶数个方格被涂成红色以及偶数个方格被涂成绿色，试确定用红、蓝、绿和橘黄为 1行n 列棋盘的方格着色的方案数。 解：设满足如题要求的1行n 列棋盘的方格着色的方案数为h n . 则序列h 0,h 1,…的指数生成 函数是 g (e)(x)= (1+x 2/2!+x 4/4!+…) (1+x 2/2!+x 4/4!...) (1+x/1!+x 2/2!+…) (1+x/1!+x 2/2!+…) = 1/4*(e x +e -x ) (e x +e -x )e x e x = 1/4(e 4x +2e 2x +1) = 001142244!!n n n n n n x x n n ∞∞==??+?+? ???∑∑=011(422)44!n n n n x n ∞=++?∑. 因此，h n = 4n -1+2n -1(n ≥1), h 0 = 1. 第14章 Polya 计数 Ex22. 用两种颜色对一个非正方形矩形的顶点进行着色, 求不等价的着色数. 如果用p 种颜色染色有多少种方案. 解： 不考虑翻转 变换群：{ρ20,ρ21}。其中ρ20是恒等变换，ρ21旋转180度的变换。给矩形的4个顶点顺时针 依次标号1,2,3,4。则有ρ20=[1][2][3][4], ρ21=[13][24]。从而用两种颜色染色不等价的着色数 是(24+22)/2=10 考虑翻转 变换群：{ρ20,ρ21,τx ,τy }。其中ρ20是恒等变换，ρ21旋转180度的变换，τx 是沿x 轴翻转，τy 是沿y 轴翻转。给矩形的4个顶点顺时针依次标号1,2,3,4。则有ρ20=[1][2][3][4], ρ21=[13][24], τx =[14][23], τy =[12][34]。从而用两种颜色染色不等价的着色数是 (24+22+22+22)/4=7 如果用p 中颜色，则只需将上面的2换成p 。 Ex26. 用4个红色珠子与3个蓝色珠子镶成项链, 有多少种不同项链? 解：项链需要考虑翻转。{ρ70,ρ71,…, ρ76, τ1,τ2,…,τ7 }。给项链上均匀分布的7个顶点顺时针 依次标号1,2,3,4,5,6,7。 则有ρ70=[1][2][3][4][5][6][7], ρ7i =[1234567], i=1,2,3,4,5,6, τ1=[1][27][36][45], |C(ρ70)|=C(7,3), |C(ρ7i )|=0, |C(τi )|=C(3,2) 从而不等价的着色数是 (C(7,3)+6?0+7?3)/14=4 Ex32. 用3种颜色对正六边形顶点着色, 求不等价着色数. (只考虑旋转) 解：ρ61 = [012345]，ρ62 = [024][135]，ρ63 = [03][14][25] 不等价着色方案数：(36+31+32+33+32+31)/6=130. 第10章 组合设计 Ex17. 证明x 3+x +1不能在域Z 2中分解(具有Z 2中系数的多项式的乘积), 然后利用该多项式 构造具有23=8个元素的域.令i 为该多项式添加到Z 2中的根, 然后做下列计算: (1) (1+i )+(1+i +i 2), (2) (1+i 2)+(1+i 2), (3) i -1, (4) i 2(1+i +i 2), (5) (1+i )(1+i +i 2), (6) (1+i )-1. 注：i 满足i 3+i+1=0。 解：(1)由于域Z 2中只有两个元素0和1，而03+0+1=1，13+0+1=1，所以x 3+x+1在Z 2中没 有根，即x 3+x+1不能以非平凡的方法分解； (2)令i 为该多项式添加到Z 2中的根，则有i 3=-i -1= i+1。 在集合{a+bi+ci 2: a,b,c ∈Z 2}上定义加法和乘法操作，即构成具有8个元素的域： <{0,1,i,1+i,i2,1+i2,i+i2,1+i+i2},+mod2,×mod2>。因此， i) (1+i)+(1+i+i2) = 2 +2i + i2= i2 ； ii) (1+ i2)+(1+ i2) = 0； iii)由i(i2+1)= i3+i=(i+1)+i=1, 得i-1= i2+1； iv) i2×(1+i+ i2)= i2+ i3+ i4= i2+(i+1)+i(i+1)=1； v) (1+i)(1+i+ i2)=i； vi) (1+i)-1=i+ i2. Ex46. 构造2个8阶正交拉丁方. 解：答案不唯一。 由习题17，得到8个元素组成的域{a0=0, a1=1, a2=i, a3=1+i, a4=i2, a5=1+i2, a6=i+i2, a7=1+i+i2},由定理10.4.4, 计算L n1 (a ij=a1?a i+a j) 得 01i1+i i21+i2i+i21+i+i2 101+i i1+ i2i21+i+i2i+i2 i1+i01i+i21+i+i2i21+i2 1+i i101+i+i2i+i21+i2i2 i21+i2i+i21+i+i201i1+i 1+i2i21+i+i2i+i2101+i i i+i21+i+i2i21+i2i1+i01 1+i+i2i+i21+i2i21+i i10 再将a k换为k得 0 1 2 3 4 5 6 7 1 0 3 2 5 4 7 6 2 3 0 1 6 7 4 5 3 2 1 0 7 6 5 4 4 5 6 7 0 1 2 3 5 4 7 6 1 0 3 2 6 7 4 5 2 3 0 1 7 6 5 4 3 2 1 0 计算L n2 (a ij=a2?a i+a j) 得 01i1+i i21+i2i+i21+i+i2 i1+i 01i+i21+i+i2i21+i2 i21+i2i+i21+i+i201i1+i i+i21+i+i2i21+i2i1+i01 1+i i 101+i+i2i+i21+i2i2 101+i i 1+i2i21+i+i2i+i2 1+i+i2i+i21+i2i21+i i10 1+i2i21+i+i2i+i2101+i i 再将a k换为k得 0 1 2 3 4 5 6 7 2 3 0 1 6 7 4 5 4 5 6 7 0 1 2 3 6 7 4 5 2 3 0 1 3 2 1 0 7 6 5 4 1 0 3 2 5 4 7 6 7 6 5 4 3 2 1 0 5 4 7 6 1 0 3 2 第13章最大流和二分图匹配 ex29. 利用匹配算法求下图的最大匹配和最小覆盖. 解：答案不唯一。 左图左顶点从上到下记为a1,…,a7，右顶点从上到下记为b1,…,b8.左图最大匹配：{{a1,b1},{a5,b2},{a2,b6},{a6,b3},{a3,b5},{a7,b4},{a4,b7}}左图最小覆盖: {a1,a2,a3,a4,a5,a6,a7} 右图左顶点从上到下记为a1,…,a7，右顶点从上到下记为b1,…,b8.右图最大匹配：{{a1,b7},{a2,b2},{a4,b3},{a5,b4},{a6,b6},{a7,b8}} 右图最小覆盖: {a1,a2,a5,a6,a7,b3} 补充.二分图G如上图， M={{x1, y1},{x3, y2},{x4, y4},{x5, y5}}是G的一个匹配， (1) 找一条M-交错路径。 (2) 找一个G的最大匹配。 (3) 找一个G的最小覆盖。 答案不唯一。 (1) M-交错链x6, y5, x5, y4, x4, y6 (2) {{x1,y1}, {x3,y2}, {x4,y6}, {x5,y4}, {x6,y5}} (3) {x3,y1,y4,y5,y6}
相关主题
文本预览