组合数学作业答案2016

1、组合数学作业第一章 引言Page 13, ex3,4,7,30ex3. 想象一座有64 个囚室组成的监狱，这些囚室被排列成8 8 棋盘。所有相邻的囚室间都有门。某角落处意见囚室例的囚犯被告知，如果他能够经过其它每一个囚室正好一次之后，达到对角线上相对的另一间囚室，那么他就可以获释。他能获得自由吗？解：不能获得自由。方法一：对64 个囚室用黑白两种颜色染色，使得横和竖方向相邻的囚室颜色不同。则对角线上两个囚室颜色为同黑或同白。 总共偶数个囚室， 若能遍历且不重复， 则必然是黑出发白结束，矛盾。方法二： 64 个囚室，若要经过每个囚室正好一次，需要走63 步，即奇数步。不妨假设该囚犯在第 1 行第

2、 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-牌)对3Xn棋盘作完美覆盖的个数。估计 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)+

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的因子。证明 mx n棋盘有ax b的完美覆盖当且仅当a既是m又是n的因子，而b是m或n的

4、因子。(提示：把ax b牌分割成a个1 x b牌。) 解：充分性。当a既是m又是n的因子，而b是m或n的因子，则mXn棋盘有ax b的平 凡完美覆盖。必要性。假设mXn棋盘有ax b牌的完美覆盖。则mXn棋盘必有b牌的完美覆盖。根据书 中的定理， b 是 m 的因子或 n 的因子。下面证明 a 既是 m 的因子又是n 的因子。方法一：因为a是b的因子，所以ax b牌可以分割成b/a个ax a牌。mXn棋盘有axa的 完美覆盖，则必然有ax a牌的完美覆盖。而 ax a牌是正方形的，所以只有唯一的一种平凡覆盖方式。从而m 是 a 的倍数， n 也是 a 的倍数。方法二：因为a是b的因子，不妨设

5、b=ka。由mXn棋盘有axb牌的完美覆盖，可任取一 个完美覆盖。设第一行的n个方格由p个ax b牌和q个bx 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:0101010000X20:101001110110=630:1111010011010=2640:1 01000110010X50:1 100101010001010=10平衡0 11010

6、游戏是不平衡的。从上表可以得到，可从20个堆中取6个，从30个堆中取26个，从50个堆中取10个。第2章排列组合P37: ex5,11,27,32,51ex5.确定作为下列各数的因子的10的最大哥(等价于用通常的10进制表示时尾部0的个数):(a) 50!,(b) 1000!解：(a) 50/5 =10,即 150 中有 10 个 5 的倍数。 50/25 = 10/5 =2,即 150 中有 2 个 25 的 倍数。从而50!的因子的5的最大哥是10+2=12。因为2的最大哥比5大，所以5的因子个 数决定10的最大哥。(b)同理，1000/5=200, 200/5=40, 40/5=8, 8

7、/5 =1, 1/5 =0,所以 1000!的因子的 10 的最大哥 等于 200+40+8+1=249.ex11.从数集1,2,2寸形成3个数的集合，如果没有2个相连的数字在同一个集合中，那么能形成多少个3个数的集合。解法一：任选3个数有C(20,3)种方案。两数相邻另一个分离：1,2和19,20这两个相邻数对， 各对应另一不相邻数有 17种选择；2,3到18,19共17种相邻数对，各对应另一不相邻数有 16种选择。三数相邻有 18种选择。202 17 17 16 18 816.3解法二：任选3个数有C(20,3)种方案。取两个相邻数有19种选择，另一个与已取出两数不同有18种选择。每三个相

8、邻的数在前一步被计数了两次，需要补回一次。2019 18 18 816 ;3解法三：先放17个0排成一排。再在18个空挡中放3个1,有C(18,3)种方法。在17个0 和3个1形成的排列中，数 1所在的位置abc,即彳#到3个不相邻的1到20中的数。解法四：令3个数从小到大排列为 a,b,d,满足a+1<b, b+1<d。令B=b-1,D=d-1,则a<B<D 为从1到18中的数，且无不相邻限制。81618ex27. 5个没有区别的车放在8 8棋盘上，使得没有车能够攻击别的车并且第一行和第一列都不空的放置方式有多少？解：方法一：5个横坐标的选择方案有 C(7,4)种，因

9、为第1列必选；5个纵坐标的选择方案有C(7,4)种，因为第一行必选；横纵坐标的配合有5!种，因为横坐标固定，纵坐标全排列。所以总的方案数为 C(7,4) C(7,4) 5!=147000.方法二：分两种情况：一是选第一行第一列， 其它4个在其它7行7歹U;有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.确定下面的多重

10、集合的11排列的数目：S=3 a,4b,5c。解：多重集S=3 a,4 b,5 c的11排列可分为3个部分：2 a,4 b,5 c:2!4!5!6930；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个一盒的酥 皮

11、蛋糕盒。(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)=2方法二：1,2,n腑全体组合有2n个，1,2,n胸任何一个组合配上相应个数的a可以得到S的一个n组合。ex52.考虑大小为3n+1的多重集合n a,

12、nb,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= 2 C(n+1,k)x n-k+1 ,两边同时对 x 求导，得到(n+1)(x+1) n= 2C(n+1,k) (n-k+1)xn-k。令 x=1 ,便得到 2 C(n+1,k) (n-k+1)=(n+1) 2n。第 3 章 鸽巢原理P50: ex4,7,11,13,

13、16ex4.证明：如果从集合1,2,2nf选择n+1个整数，那么总存在两个数它们之间相差1.证明：将2n个数分成n个集合：1,2,3,4, ,2n1,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 个

14、数， 至少有两个在同一个鸽巢。若这两个数模 100 同余，则两个数的差是100 的倍数；若这两个数模100 不同余，则这两个数的和是100 的倍数。ex11. 一个学生有37 天来准备考试。根据以往经验，她知道她需要的学习时间不超过60 小时。她还希望每天至少学习一个小时。证明，无论她怎么安排学习时间 (每天学习的时间是 整数小时)，都存在连续若干天，在此期间她恰好学习了13 个小时。证明：设 ai 是这名学生从第1 天到第 i 天学习的总小时数，那么0<a1<a2< - a36<a37 6013+ a1<13+ a2<- -13+ a36<13+ a

15、37<73于是a1,a2,，§6,a37和13+ a1,13+ a2,，13+ <36,13+ a37共74个数取值在1至U 73之间。一定有两个数相同，且这两数一定是13+ai=ajo于是从第i+1天到第j天这名学生学习了13小时。ex13. 设 S 是平面上 6 个点的集合，其中没有3 个点共线。给由 S 的点所确定的 15 条线段着色，将它们或者着成红色，或者着成蓝色。证明：至少存在两个由 S 的点所确定的三角形或者是红色三角形或者是蓝色三角形。证法一：六个点 ABCDEF 至少形成一个同色三角形，设此三角形为 ABC 且为红色。(1) 若 DEF 同色，则得到另一

16、同色三角形。(2) 否则 DEF 必有一条蓝色边，设为 DE 。考虑从 D,E 两点分别到 A,B,C 三点的连线。(2.(1) 或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 对同色，对应

17、数的和大于等于4，所有点对应数的和大于等于24 。若没有同色三角形，则所有数的和是20；若只有一个同色三角形，则所有数的和是22. 所以至少有两个同色三角形。(假设自己ex16. 证明：在一群 n>1 个人中，存在两人，他们在这群人中有相同数目的熟人不是自己的熟人) 。证明：n个人，每人的熟人数记为a,即ai,a2,a,取值于0到n-1之间。由于有人认识0个人和有人认识 n-1 个人不会同时出现。所以这n 个数的取值只有n-1 种，从而必有两人熟人数相同。第 4 章 生成排列和组合ex 6, 7, 23, 24, 33, 52ex6.确定1,2,，8的下列排列的逆序列。(a) 35168

18、274 (b)83476215解： (a) 24040010(b) 65113210ex7.构造1,2,，8的排列，使得其逆序列是(a) 25502110 (b) 66142100解： a) 48165723 b) 73658412ex23. 确定下列 9 阶反射 Gray 码中 9 元组的直接后继(a) 010100110(b) 110001100(c) 111111111解：后继为(a) 010100111 (b) 110001101 (c) 111111101ex24. 确定下列 9 阶反射 Gray 码中 9 元组的直接前趋(a) 010100110(b) 110001100(c) 1

19、11111111解：前驱为 (a) 010100010 (b) 110000100 (c) 111111110ex33.子集2489出现在1,2,3,4,5,6,7,8,9的4-子集的字典序的哪个位置上？解： 2489 的位置为 97581443ex52.验证二进制n元组an-1an-2a°位于 Gray码表的位置 k处，其中 k确定如下：对i=0,1，,n-1,若 an-1+ ai 是偶数则 bi=0 ,否则 bi=1,则有 k=(bn-1 b。”。证明：为方便，记bn-1b0=f(an-1an-2a°),其中对i=0,1, -n,若an-1+ ai是偶数则 bi=0 ,

20、 否则bi=1 。数学归纳证法一：当二进制位数n 1 时，公式成立；假设当位数为n 1时，公式成立，即an-2a0在Gray码表中位于k'处，k'环26)2,其中 Cn-2 , C0 = f( an-2a0)。考虑n位二进制码 an-1an-2- a0o当an-1=0时，根据定义，bn-1=0 ,且bi=ci (i=n-2,0)再根 据Gray码的递归构造，以及an-1=0 ,可知an-1an-2a0在Gray码中的位置是(Cn-2C0)2 = (bn-1 b0)2。当an-1=1时，根据定义，bn-1=1,且bi=1- ci (i=n-2,0)根据Gray码的递归构造，以及a

21、n-1=1 ,可知an-1an-2- a0在Gray码中的位置是2n - (Cn-2C0)2- 1 = (12l)(Cn-2C0)2= (bn-1 b0)2,其中1-1是n-1个1。数学归纳证法二：考虑 n 阶反射 Gray 码。在n阶反射Gray码中，第一个n元组是00,对应f(00) = 0 ”蹒足位置关系，命 题成立。(2)假设 n元组an-ian-2-ao100在 Gray码中的位置是(bn-ibo)2,其中bn-ibo=f(an-ian-2 ao)。(2.(1) b0=0 时，(an-ian-2 - a0)=0, an-ian-2aO 的下一个 Gray 码是将 a0 改为 1-a0

22、,即an1an2Ka0°它的位置是(bn-ibi0)2+i=(bn-ibii)2,f( an1an2Ka0)=bn-ibii,满足位置关系，命题成立。(2.(2) 0=1时，(an-ian-2a0)=1。取j为an-ian-2aO中从右往左若干个连续的 0后面的第 一个1的位置，即 ajaj-r- a0=10 - O o此时，加=切-仔=b0=1, bj+i=0。注意到an-ian-2 a。下一个 Gray 码是 an 1K d 1aj K a0,其位置应该是(bn-i bO)2+1=(bn-i bj+210 0)2。令 cn-i C0 = f( an iK aj iaj K a&#

23、176;),则 cj=cj-i=-= c0=0, cj+i=1, ck= bk, (k = j+2,n-1),满足位置关系。第6章容斥原理ex5, ex13, ex17, ex26, ex305.确定多重集 a,4 b,5c,7d的10-组合个数。解：令全集U=(x i ,x2, x3, x4)| xi+x2+x3+x 4=10, xi, x2, x3, x4 0 A=(x 1, x2, x3, x4)| xi+x2+x3+x4=10, xi, x3, x4 0, x2 5 B=(x 1, x2, x3, x4)| xi+x2+x3+x4=10, xi, x2, x4 0, x3 6C=(x

24、1, x2, x3, x4)| xi+x2+x3+x4=10, xi, x2, x3 0, x4 8其中 |U|=10 3,冏=5 3 旧=4 3 ,|C|=2 3, 3333|A B|=|A C|=|B C|=|A B C|=0133本题所求10-组合的个数为C |二|U|-|A|-|B|-|C|+|A B|+|A C|+|B C|-|A B C|二=185 13.确定1,2,触至少有一个奇数在它的自然位置上的排列数。解：方法一对于i=1,3,5,7,定义Ai=i在位置i上AiU A3UA5U A7U A9 = C(5,1)8! -C(5,2)7!+C(5,3)6! -C(5,4)5!+C(

25、5,5)4! = 157824.方法二将计算没有奇数在自然位置上的问题转化为带禁止位置的排列，共5个禁止位置分布在对角线上。c=C(5,1), r2=C(5,2), r 3=C(5,3), r4=C(5,4), r5=C(5,5),6= - = r9=0.9!-(9!- ri8!+ r27!- r36!+ r45!- r54!)= 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是不允许的，但 abbba

26、cacb可以。)解：令 U=S的全排列A=3个a连续出现的排列B=4个b连续出现的排列C=2个c连续出现的排列贝 U|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|

27、-|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。 解：XXXXXXXXX带禁止位置的排列，放置方法数是6!-门5!+r24!-r33!+r42!-r51!,由1=9,2=2 2+2+5 4=26,3=4 4+5 2=26,4=4 2, r5=0, r6=0, 得到排列数为 6!-9 5!+26 4!-26 3!+8 2!-0 1!+0 0!=124.30.多重集

28、3 a,4 b,2 c,1d存在多少循环排列，对每种类型的字母，该类型的所有字母不连 续出现？解：方法一：固定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

29、)!/(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、30+20 -6=871.31.多重集S=2 a,3 b,4 c,5d存在多少循环排列，对每种类型的字母，该类型的所有字母不 连续出现？解：令 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!) =

31、 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|AC| = (1+3+1+5-1)!/(1!3!1!5!)=9!/(1!3!1!5!)=504|AD| = (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!) =

32、8!/(2!1!1!5!) = 168|BD| = (2+1+4+1-1)!/(2!1!4!1!)=7!/(2!1!4!1!)=105|CD| = (2+3+1+1-1)!/(2!3!1!1!)=6!/(2!3!1!1!)=60|ABC|=(1 + 1 + 1+5-1)!/(1!1!1!5!) = 7!/(1!1!1!5!) = 42|ABD|=(1 + 1+4+1-1)!/(1!1!4!1!) = 6!/(1!1!4!1!) = 30|ACD|=(1+3+1+1-1)!/(1!3!1!1!) = 5!/(1!3!1!1!) = 20|BCD|=(2+1 + 1+1-1)!/(2!1!1!1!

33、) = 4!/(2!1!1!1!) = 12|A BCD|=(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章

34、递推关系和生成函数ex. 9,46,47; 13,17,25,9.令hn等于1行n列棋盘的方格能够用红、白和蓝色着色并使得没有两个涂成红色的方格 相邻的着色方案数。求出并验证hn所满足的递推关系。然后找出hn的公式。解：棋盘的第一个格子有3中着色方法：(1)着红色，则第二个格只能着蓝色或者白色，此时的方案数为2hn-2；(2)着蓝色或者白色，此时的方案数为2hn-i；因此,hn = 2h n-i+ 2h n-2,且 ho = 1, hi = 3.求hn：特征方程：x2-2x-2=0解得：xi=1+ 3 , x2=1-.3则有：hn = C1(1+ ./3)n+ C2(1- , 3)n代入初始条

35、件，ho = C1 + C2=1h1 =C1(1 + ,3 )+C2(1- -.3 )=3解得，=1 立 =1 立1-2 T ,c2- 2 号因此，hn = (1 4)(13)n (1 -)(13)n.46 .求解非齐次递推关系hn = 6hn-1- 9hn-2+2n, (n 2), ho = 1, h1 = 0.解：对于齐次递推关系：hn = 6hn-1- 9hn-2特征方程：x2-6x+9=0解得：x1=x2=3一般解：hn = C13n+ C2 n 3n对于非齐次递推关系，其特解为：hn = a n + b代回递推关系，比较系数得a=1/2, b=3/2,此时特解 hn = (1/2)n

36、+3/2因此，hn = C1 3n+ C2 n 3n+(1/2)n+3/2代入初始条件，ho = C1+3/2=1h1 =3c1+3c2+1/2+3/2=0解得，C1=-1/2C2=-1/6所以，hn = (-1/2-n/6)*3 n+n/2+3/2.47 .求解非齐次递推关系hn = 4hn-1- 4hn-2+3n+1, (n 2), ho = 1, h1 = 2.解：对于齐次递推关系：hn = 4hn-1- 4hn-2特征方程：x2-4x+4=o解得：x1=x2=2一般解：hn = C12n+ c2n2n对于非齐次递推关系，其特解为：hn = an + b代回方程，比较系数得a=3, b=

37、13,此时特解 hn= 3n+13因此，hn =(C1+C2n)2 n+3n+13代入初始条件，h0 = ci+13=1hi =2(C1+C2)+3+13=2解得，C1=-12C2=5所以，hn = (5n-12) *2n+3n+13.13.确定下列每个序列的生成函数J )/-a o 111In-，(a i5 a real number)解：(a) g(x) = 1+Cx+C2x2+-.+Cnxn+.=1+cx+(cx) 2+(Cx)n+ .=1/(1 -Cx)(b) g(x) = 1-x+x2-x3+ +(-1)nxn+=1+(-x)+(-x)2+(-x)3+(-x)n+ x x2 L (

38、1)nxn L12n=1/(1+x)(C)g(x)=01 ( x) 2 x2 L n ( x)n L-0=(1 -x)(d) g(x) = 1+1/1!*x+1/2!*x 2+ - +1/n!*x n+ =ex(e) g(x) = 1- x/1! +x 2/2! + +()n xn/n! +=1+(-x)/1! +(-x)2/2! + +x)n/n! +=e-x17.确定苹果、橘子、香蕉和梨的袋装水果的袋数 hn的生成函数，其中各袋要有偶数个苹果, 最多两个橘子，3的倍数个香蕉，最多一个梨。然后从该生成函数求出hn的公式。解：序列ho,h1, 的生成函数是g(x) = (1+x 2+x4+ -

39、 ) (1+x+x 2) (1+x 3+x6+ - ) (1+x)=1/(1-x2)*(1+x+x 2)*(1+x)*1/(1 -x3)=1/(1 -x)2=(n 1)xn .n 0因此，hn =n+1.17确定苹果、橘子、香蕉和梨的袋装水果的袋数hn的生成函数，其中各袋要有偶数个苹果，至少两个橘子，3的倍数个香蕉，最多一个梨。然后从该生成函数求出hn的公式。解：序列h0,hi, 的生成函数是g(x) = (1+x 2+X4+ ) (x2+x3+- -) (1+x 3+x6+ - ) (1+x)=1/(1-x2) * x2/(1 -x) * 1/(1 -x3) * (1 -x2)/(1-x)2

40、x=32(1 x) (1 x x )11331二239 1 x (1 x) (1 x) x1 nn=-x 1 3(n 1) 39n 02其中1n 2n 1 n 213(n1) 3,验证(ho, h1, h2, h3)=(0,0,1,2).9225.如果偶数个方格被涂成红色以及奇数个方格被涂成白色，试确定用红、白、蓝和绿为1行n列棋盘的方格着色的方案数hn。解：设满足如题要求的 1行n列棋盘的方格着色的方案数为hn.则序列h0,h1,的指数生成函数是g(x尸(1+x2/2!+x4/4!+ )(x/1!+x/3!+x5/5!+)(1+x/1!+x 2/2!+ -) (1+x/1!+x2/2!+ )

41、=1/4*(ex+e-x) (ex-e-x)ex ex=1/4(e4x - 1) nn1 n xn 1 x=41=44 n 0 n! n 1 n!因此，hn = 4n-1(n 1), h0 = 0.26.如果偶数个方格被涂成红色以及偶数个方格被涂成绿色，试确定用红、蓝、绿和橘黄为1行n列棋盘的方格着色的方案数。解：设满足如题要求的1行n列棋盘的方格着色的方案数为hn.则序列h0,h1,的指数生成函数是g(x尸(1+x2/2!+x4/4!+ ) (1+X/2!+x4/4!.) (1+x/1!+x 2/2!+ )(1+x/1!+x2/2!+ )=1/4*(ex+e-x) (ex+e-x)ex ex

42、=1/4(e4x+2e2x+1)n1 n x4 4 n o n!n2 2nx- =1 1(4n 0 n!44 n 0n2 2n). n!因此，hn = 4n-1+2n-1(n 1), h0 = 1.第14章Polya计数Ex22.用两种颜色对一个非正方形矩形的顶点进行着色，求不等价的着色数. 如果用p种颜色染色有多少种方案.解：不考虑翻转变换群： 20,21。其中20是恒等变换，21旋转180度的变换。给矩形的4个顶点顺时针依次标号1,2,3,4。则有20=1234,21=1324。从而用两种颜色染色不等价的着色数是(24+22)/2=10考虑翻转变换群：20, 21, x, y。其中20是恒

43、等变换，21旋车专180度的变换，x是沿X轴翻转，y是沿y轴翻转。给矩形的4个顶点顺时针依次标号1,2,3,4。则有20=1234,21=1324,x =1423, y=1234。从而用两种颜色染色不等价的着色数是(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=1234567,7i=1234567, i=1,2,3,4,5,6,1=1273645,|C( 70)

44、|二C(7,3), |C( 7i)|=0, |C( i)|=C(3,2)从而不等价的着色数是(C(7,3)+6 0+7 3)/14=4Ex32.用3种颜色对正六边形顶点着色，求不等价着色数.(只考虑旋转)解：61 = 012345 , 62= 024135 , 63 = 031425不等价着色方案数：(36+31+32+33+32+31)/6=130.第10章组合设计Ex17.证明x3+x+1不能在域Z2中分解(具有Z2中系数的多项式的乘积),然后利用该多项式构造具有23=8个元素的域.令i为该多项式添加到 Z2中的根，然后做下列计算：(1) (1+i)+(1 + i+i2),(2) (1 + i2)+(1+i2),(3) i-1,(4) i2 (1+i+i2),(5) (1+i)(1+i+i2),(6) (1 + i)-1.注：i 满足 i3+i+1=0。解：(1)由于域Z2中只有两个元素 0和1,而03+0+1=1, 13+0+1=1,所以x3+x+1在Z2中没 有根，即x3+x+1不能以非平凡的方法分解；(2)令i为该多项式添加到 Z2中的根，则有i3=-i-1= i+1。在集合a+bi+ci 2: a