组合数学卢开澄第四版答案
【篇一：组合数学+卢开澄版++答案第四章】
x是群g的一个元素，存在一最小的正整数m，使xm=e，则称m为x m n
m?n m
,等式右边x x＝x nmm?n
，?ab?ba，即所有 的阶，试证：
c=｛e,x,x2, …,xm-1｝ 证：
x是g的元素，g满足封闭性所以，xk是g中的元素 c∈g 再证c是群：
xa∈c, (xa)-1= xb=xm-a
4.3设g是阶为n 的有限群，则g的所有元素的阶都不超过n.
证明：设g是阶为n 的有限群，a是g中的任意元素，a的阶素为k， 则此题要证k?n
首先考察下列n+1个元素 a,a,a,a,..a.. 234n?1
由群的运算的封闭性可知，这n+1个元素都属于g,，而g中仅有n 个元素，所
以由鸽巢原理可知，这n+1个元素中至少有两个元素是相同的，不妨设为 a i i ? a i i?j
（1?j?n） j a
? a?a j j
由群的性质3可知，a是单位元，即a=e，又由元素的阶数的定义可知，当a为k阶元素时a=e，且k是满足上诉等式的最小正整数，由此可证k?j?n k
4.4 若g是阶为n的循环群，求群g的母元素的数目，即g的元素可表示a的幂： a,a2……..an
所以群g中母元素的数目为n(1-1/p1)………(1-1/pk)个. 4.5 证明循环群的子群也是循环群
证明：设h是g=a的子群，若h=e,显然h是循环群，否则取h中最小的正方幂元am，下面证明am是h的生成元,易见am?h，只要证明h中的任何元素都可以表成am的整数次方，由除法可知存在q和r,使得l=qm+r,其中0?r?m-1,因此有ar=al?qm，因为am是h中最小的正方幂元，必有r=0,这就证明出 a l
=amq?{am}证明完毕。
4.6 若h是g的子群，x和y是g的元素，试证xh?yh或为空，或xh?yh 4.7若h是g的子群,|h|=k,试证： |xh|=k 其中x?g.
证明：∵h是g的子群，x?g ∴|xh|≤k
如果|xh|k,则必存在a,b?h,使得xa=xb, 因为且x?g所以存在逆元 x-1xa=x-1xb ∴a=b ∴|h|k 又∵|h|=k ∴|xh|=k
.4.8 有限群g的阶为n，h是g的子群，则h的阶必除尽g的阶。 答案：已知|g|=n, |h|=|g| m r
设g={a0,a1,a2.......an?1}， h={b0,b1,b2......bn?1}
因为h是g的子群，所以在h中的一个(bm)r一定在g中对应一个am使得 m
(b)?a ，
所以有brm?am，则rm一定是m的倍数，所以则h的阶必除尽g的阶。
4．9 g是有限群，x是g的元素，则x的阶必除尽g的阶。 解：证： 设|g|=g,则x,x2,x3,?,xg?1中必有相同元。设xk?xl, 1?k?l?g?1，则xl?k?e，1?l?k?g。
对于给定的x，存在最小的正整数r，使得xr?e。于是h?{x,x2,x3,?,xr}是g 的子群，
若h?g，则?a?h，显然，h?ha??，h?ha?2r。 若h?ha?g， 则 2r?g,r|gr(k?1)?g
，否则?b?h?ha，hb?(h?ha)??。 于是h?ha?hb???g，，r|g。证毕。
4.10 若x和y在群g作用下属于同一等价类，则x所属的等价类ex，y所属的等价类ey有 |ex| = |ey|
解：因为x和y在群g作用下属于同一等价类，所以x和y在群g作用下存在置换p1使x和y互相转变，即 ex = ey={x,y}
所以|ex| = |ey|。
置换群: 格式: (1)9 ,1个.(1)3(2)3,4个.(1) (4)2,2个.(1)(2)4,1个 =(36+24+4)/8=8
其中划横线为红色,其它为蓝色.共8种着色方案.
4.12：试用burnside引理解决n个人围一圆桌坐下的方案问题。 解： 图一 c1
……………………………………
如图： n个人围成一个圆桌的所有排列如上图所示。一共n!个。 …………………………
旋转360/i，i={n,n-1,n-2,……1}； 得到n种置换 当且仅当i=1的置换（即顺时针旋转360/1度：p1=(c1)(c2)……(cn!);）
时有1阶循环存在（因为只要圆桌转动，所有圆排列中元素的绝对位置都发生了变化，所以不可能有1阶循环存在）。
不同的等价类个数就是不同的圆排列个数，根据burnside引理， 所以一共有(n-1)!种排列。
4.13 对正六角形的6个顶点用5种颜色进行染色，试问有多少种不同的方案，旋转使之重合作为相同处理
解：首先对每个顶点进行编号，分别为1，2，3，4，5，6，根据旋转的角度不同，共可以旋转6次，得到不同的旋转方式 c(1)=6 4??5? 6旋转0度： 1??1??2???3???
旋转60度： 2??123456? c(1)=1 旋转120度：3??135??246? c(1)=2 旋转180度：4??14??25??36? c(1)=3 旋转240度：
5??153??264? c(1)=2 旋转300度：6??165432? c(1)=1 所以g=6，根据polya定理，m=5， l?11g
?mc(1)?mc(2)?...?mc(6)? ?? ?
612321
???5?5?5?5?5?5??6 ?2635
故一共2635种涂色方案
4.15 对一个正六面体的8个顶点，用y和r两种颜色染色，使其中有5个顶点用色y，其余3个顶点用色r，求其方案数。 解： 相当于4.7节中例2中求b5r3的系数，为[c(8,5)+8c(2,1)]/24=3
【篇二：组合数学第四版卢开澄标准答案-第一章】
>1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：[解] (a) a?b?5 将上式分解，得到?a?b??5 (a)a?b?5;(b)a?b?5. ?
?a?b??5
(6?10)?5?11?(45?4)?16?5?11?41?531个点。 1.2 5个女生，7个男生进行排列，
(a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？
(c) 两男生a和b之间正好有3个女生的排列是多少？
[解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。 (b) 先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有c8种选择。将女生插入，有5!种方案。故按乘法原理，有：
(c) 先从5个女生中选3个女生放入a，b之间，有c5种方案，在让3个女生排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有 (7+1)! = 8!
由于a，b可交换，如图 **a***b** 或 **b***a** 故按乘法原理，有：
1.3 m个男生，n个女生，排成一行，其中m，n都是正整数，若 (a) 男生不相邻(m?n+1)； (b) n个女生形成一个整体； (c) 男生a和女生b排在一起； 分别讨论有多少种方案.
[解] (a) 先将n个女生排列，有n!种方法，共有n+1个空隙，选出m个空隙，共有cn?1种 m 3 3 5 5
方法，再插入男生，有m!种方法，按乘法原理，有： m
(n?1)!n!(n?1)!
m!(n?1?m)!(n?1?m)!
(b) n个女生形成一个整体，看作一个人，与m个男生做重排列，然后，n个女生内部 5
[解] 选入26－2＝24个字母中选取5个字母，有c24种方法，5个字母内部排列，有
5!种方案，再将x*****y这7个字母看作一个，与其余19个合起来作排列，共有(19+1)!=20!种方案，又因为x与y可交换，故按乘法原理，有： 24!?24? 5 5!?19!e??
又因为：ln40+0.5(lg?+lg48)+24(lg24–lge)
≈1.602059991+0.5(0.497149872+1.681241237)+24(1.380211242-0.434294481) =25.39325777
1.5 求3000到8000之间的奇整数的数目，而且没有相同的数字. [解] 3000~8000中各位不同的奇数，分类讨论： 1?1!?2?2!?3?3!???n?n!