山大离散练习

1、1、Solve the recurrence relation an=an-1+ an-2 with a0= a1=1 using generating function.2、Determine the number of the terms in the expansion of (x1+ x1+ x10)20.3、将m个无区别的球，放入n个有区别的盒子，在允许有空盒和不允许有空盒两种情况下分别讨论可能的放法数。4、求n元集合到m元集合单射、满射、双射的个数。5、用容斥原理求1n中与n互素的元素个数。6、是个群，xG，定义G中的运算“D”为aDb=a*x*b，对a,bG，证名也是群。证明：1

2、）a,bG，aDb=a*x*bG，运算是封闭的。2）a,b,cG，（aDb）Dc=（a*x*b）*x*c=a*x*（b*x*c）=aD（bDc），运算是可结合的。3）aG，设E为D的单位元，则aDE=a*x*E=a，得E=x-1，存在单位元。4）aG，aD x-1*a-1*x-1=a*x* x-1*a-1*x-1= x-1=E，x-1*a-1*x-1D a = x-1*a-1*x-1* x* a=x-1=E,a的逆元为x-1*a-1*x-1，每个元素都有存在。所以也是个群7、设是有限交换群，a,bG，|a|=m,|b|=n,m,n是整数，且GCD（m,n）=1即m,n互素，证明：|ab|=mn

3、证明：设|ab|=k，因为(ab)mn= (ab)(ab)(ab)=(am)n(bn)m=e,所以k|mn,e=(ab)k)m=(ab)km=(akm)(bkm)= bkm, 所以n|km,由于GCD（m,n）=1，所以n|k同理可求，所以m|k.所以有mn|k，mn=k ,|ab|=mn8、设是环，1是其乘法幺元，在S上定义运算 和 ：abab1，ababab。（1）证明是一个环。（2）给出的关于运算 和 的单位元。证明：（1）对任意a、b、cS，则（ab）cabc1abc11，a（bc）abc1abc11，于是（ab）ca（bc），即满足结合律。abab1ba1ba，所以是可交换的。a（-

4、1）a（-1）1a（-1）a，所以-1是 单位元。a（-1-1-a）a（-1-1-a）1-1（-1-1-a）a，所以-1-1-a是a的逆元。综上可知，是一个交换群。（2）（ab）cabc（ab）cababc（abab）cababcacbcabca（bc）abca（bc）abcbca（bcbc）abcbcabacabc所以（ab）ca（bc），即满足结合律。又a0a0a0a，0a0a0aa，0 是 单位元因而是有幺元的半群。a（bc）abca（bc）abc1a（bc1）2abcabac1（ab）（ac）abac1ababacac12abcabac1a（bc）（ab）（ac），所以 对 满足分配律

5、。从而是一个环。9、设 G是一个群,e是G的单位元,H是G的子群. 如下定义关系R： 证明R是G上的等价关系.证明: 对于任意的aG， aea-1=eH， R，故R是自反的。 对于任意的a，bG，若 R， aeb-1H，(aeb-1)-1=(ab-1)-1=ba-1H， R，故R是对称的。 对于任意的a,b,cG，若 R， R， aeb-1H且 bec-1H， (aeb-1) (bec-1)=ac-1H， R，故R是传递的10、是个群，uG，定义G中的运算“D”为aDb=a*u-1*b，对任意a,bG，求证：也是群。证明：1）a,bG，aDb=a*u-1*bG，运算是封闭的。2）a,b,cG，

6、（aDb）Dc=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=aD（bDc），运算是可结合的。3）aG，设E为D的单位元，则aDE=a*u-1*E=a，得E=u，存在单位元。4）aG，aDx=a*u-1*x=E，x=u*a-1*u，则xDa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。所以也是个群11、证明有限群中阶（周期）大于2的元素的个数必定是偶数。证明x与其逆元x-1的周期相同，又当x的周期大于2时，xx-1。定义映射f: xx-1,是群中的双射函数，所以阶大于2的元素成对出现（x与其逆元x-1是一对），故其个数必定是偶数。12、 证明n阶循环群的子群的个数恰

7、为 n的正因子数。证明：对n 的每一正因子d，令k=,b=ak, H=e,b,b2,bd-1。因为|a|=n,所以bd=(ak)d=akd=an=e且|b|=d。从而H中的元素是两两不同的，易证HG。故|H|=d。所以是G的一个d阶子群。设H1是G的任一d阶子群。则由定理5.4.4知，H1(am)，其中am是H1中a 的最小正幂，且|H|=。因为|H|=d，所以m=k，即H=H1。从而H是G的惟一d阶子群。13、证明：对于剩余环Zn，n，n ，n是素数当且仅当Zn中无零因子。证明：（1）设Zn中无零因子，往证n是素数。假设n不是素数，则存在整数n1，n2，使nn1n2n1n2n因此 n1，n2

8、，但n1nn2. 即n1，n2是Zn的一对零因子，矛盾。所以，n是素数。（2）设n是素数，若Zn，n，n 中有零因子i，jZn，使得i，j，inj=，则ij，因而 nij由于n是素数，故ni 或 nj即i 或 j，矛盾。所以，Zn，n，n 中无零因子。14、假设是一个代数系统，*是X上的二元运算。如果*运算是可结合的，并且对任意的x,yX，当x*y=y*x时，有x=y。证明X中每个元素都是幂等元。证明：对任意的元素xX，由于*运算可结合，所以有 (x*x)*x=x*(x*x) 由题设条件可知x*x=x 由x的任意性则每个元素都是等幂元。15、假设是一个代数系统，和分别是X上的二元运算。若对任意

9、的x,yX，有xy=x。证明：对于是可分配的。证明：对任意的x,y,zX， x(yz)=xy = (xy)(xz) 而 (yz)x=yx = (yx)(zx)证毕。16、 假设和是两个代数系统，*和分别是X和Y上的二元运算，并且满足结合律和交换律。f1和f2都是代数系统X到Y的同态映射。令：h:XY，对任意的xX，h(x)=f1(x) f2(x)。证明h是代数系统X到Y的同态映射证明：由h的定义可知h是X到Y的函数 对任意的x,yX h(x*y)=f1(x*y) f2(x*y) =(f1(x)f1(y)(f2(x)f2(y) 由于运算满足结合律和交换律，所以上式=(f1(x)f2(x)(f1(

10、y)f2(y)=h(x) h(y)h对于运算保持。所以h是代数系统X到Y的同态映射。证毕 17、假设是一个群，|G|=2n。证明G中至少有一个周期为2的元素。证明：因为群中的元素互逆，即元素a的逆元是a，a的逆元是a。因而G中逆元不等于自身的元素必为偶数个（包括零个）。但是G包含偶数个元素，因此G的逆元等于自身的元素个数也必为偶数个，而G的单位元e的逆元是其本身，所以G中至少还有另一个元素a其逆元是它本身，即a-1=a。从而 a2=a*a=a*a-1=e，并且ea。即 a是一个周期为2 的元素所以至少存在一个周期为2的元素。18、已知G=1,2,3,4,5,6，7为模7乘法，试说明是否构成群？

11、是否为循环群？若是，生成元是什么？它是否有子群？若有，子群是什么？解：列出运算表如下：7123456112345622461353362514441526355316426654321由运算表和模7乘法的性质可知是群。是循环群，生成元是3，5。它有子群，子群是：，19、假设f,g是群到群的同态映射。证明是群的子群，其中 H=x|xX ,并且f(x)=g(x)。证明：由H的定义可知HX。假设ex是群的单位元，ey是的单位元 由f,g是群到群的同态映射可知 f(ex)= ey=g(ex) 从而exH，故H非空。 对于任意的a, bH，则有f(a)=g(a)，f(b)=g(b) 由f,g是群到群的同

12、态映射可知f(b-1)=(f(b)-1=(g(b)-1=g(b-1) 因此 f(a*b-1)=f(a)f(b-1)=g(a)g(b-1)=g(a*b-1) 所以a*b-1H 因此是群的子群。证毕。20、假设是一个代数系统，*是X上的二元运算。对任意的x,y,z,wX，有x*x=x，并且(x*y)*(z*w)=(x*z)*(y*w)。证明：x*(y*z)=(x*y)*(x*z)证明：对任意的x,y,zX 有 x*x=x 所以x*(y*z)= (x*x)*(y*z)=(x*y)*(x*z) （由已知条件）证毕。21、假设S=a,b,c，X=，Y=。二元运算符,和一元运算符分别是集合的交、并、补运算

13、。问X和Y是否同构？为什么？答：X和Y不同构。因为Y=不是代数系统，补运算关于集合a,b,S不封闭。如果存在X和Y同构，则X是代数系统，Y一定是代数系统。由上可知产生矛盾。22、假设是一个群。证明对于任意的a,bG，存在唯一的xG，使得a*x=b。证明：由于是一个群，所以对于任意元素a,bG，逆元aG存在，并且x=a*bG，使得 a*x=a*(a*b)=(a*a)*b=b假若还存在另一个元素cG，使得 a*c=b则 c=e*c=(a*a)*c=a*(a*c)=a*b=x所以x唯一。证毕。23、设是一个含幺半群，e是单位元。证明若任意的xS，有x*x=e，则是阿贝尔群。证明：对于任意的xS，有x

14、*x=e，因此x-1=x，所以是群。 对任意的x,yS x*y= x-1*y-1=(y*x)-1=y*x 所以是阿贝尔群证毕。24、已知G=0,1,2,3,4,5，+6为模6加法，试说明是否构成群？是否为循环群？若是，生成元是什么？它是否有子群？若有，子群是什么？+6012345001234511234502234501334501244501235501234解：由运算表和模6加法的性质可知是群。是循环群，生成元是1，5。它有子群，子群是：，25、假设是群，C=a | aG, 并且对 xG,a*x = x*a，证明是的子群。证明：（1）因为是群，所以存在单位元e。 对xG，有e*x = x*e =