山大离散练习

1、Solvetherecurrencerelationan=an-1+an-2witha0=a1=1usinggeneratingfunction.2、Determinethenumberofthetermsintheexpansionof(X+X+X10)203、将m个无区别的球，放入n个有区别的盒子，在允许有空盒和不允许有空盒两种情况下分别讨论可能的放法数。4、求n元集合到m元集合单射、满射、双射的个数。5、用容斥原理求1n中与n互素的元素个数。6、G,*是个群，xG,定义G中的运算“A”为aAb=a*x*b,对0a,bWG,证名G,A也是群。证明：1)Va,b$G,aAb=a*x*bG,运算是封闭的。2) Va,b,c$G,(aAb)Ac=(a*x*b)*x*c=a*x*(b*x*c)=aA(bAc),运算是可结合的。3) VaG，设E为A的单位元，则aAE=a*x*E=a，得E=x-i，存在单位元。VaG,aAx-i*a-i*x-i二a*x*x-i*a-i*x-i二x-i=E,x-i*a-i*x-iAa=x-i*a-i*x-i*x*a=x-i=E,a的逆元为x-i*a-i*x-i,每个元素都有存在。所以G,A也是个群7、设G,*是有限交换群，a,beG,|a|=m,|b|=n,m,n是整数，且GCD(m,n)=1即m,n互素，证明:|ab|=mn证明：设lab丨二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、设S,+,是环，1是其乘法幺元，在S上定义运算和:ab=a+b+1,aOba+b+ab。(1) 证明S,，O是一个环。(2) 给出S,，的关于运算和O的单位元。证明：(1)对任意a、b、ceS,贝】J(ab)c=ab+c+1=a+b+c+1+1,a(bc)=a+bc+1=a+b+c+1+1,于是(ab)c=a(bc),即满足结合律。ab=a+b+1=b+a+1=ba,所以是可交换的。a(T)=a+(-1)+1=a=(-1)a,所以-1是单位元。a(T-1-a)=a+(TT-a)+1=T=(TT-a)a,所以T-1-a是a的逆元。综上可知，S,是一个交换群。(2)(a0b)0c=a0b+c+(a0b)c=a+b+ab+c+(a+b+ab)c=a+b+ab+c+ac+bc+abcaO(bOc)=a+bOc+a*(bOc)=a+b+c+bc+a(b+c+bc)=a+b+c+bc+ab+ac+abc所以(aOb)Oc=aO(bOc)，即O满足结合律。又aO0a+0+a0a，OOaO+a+Oaa，0是O单位元因而S,O是有幺元的半群。aO(bc)a+bc+a*(bc)(ab)(ac)=ab+ac+l=a+b+ab+a+c+ac+l=2a+b+c+ab+ac+la(bc)=(ab)(ac)，所以对满足分配律。从而是一个环。9、设G是一个群,e是G的单位兀,H是G的子群.如下定义关系R:a严2a严2Ra1ea21H.证明R是G上的等价关系.证明:对于任意的aGaea_1=eH,R故R是自反的。对于任意的a,bG,若Raeb-1H，:(aebi)-i=(abi)T=baTH,R故R是对称的。对于任意的a,b,cG，若RRaeb-1H且bec-1H，(aeb-1)(bec)=ac-1H,R故R是传递的10、是个群，uG,定义G中的运算“”为ab=a*u-1*b，对任意a,bG求证：也是群。证明：1)a,bgG,ab=a*u-1*bG，运算是封闭的。2) a,b,gG,(ab)c=(a*u-1*b)*u-1*c=a*u-1*(b*u-1*c)=a(bc),运算是可结合的。3) aG，设E为的单位元，则aE=a*u-1*E=a,得E=u，存在单位元。4) aG，ax=a*u-1*x=E，x=u*a-1*u，则xa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。所以也是个群11、证明有限群中阶(周期)大于2的元素的个数必定是偶数。证明X与其逆元X-1的周期相同，又当x的周期大于2时，xfx-1。定义映射f:XX-1,是群中的双射函数，所以阶大于2的元素成对出现(x与其逆元x-1是一对)，故其个数必定是偶数。12、证明n阶循环群的子群的个数恰为n的正因子数。n证明：对n的每一正因子d，令k二一，b二ak,H二e,b,b2,bd-1。d因为|a|=n,所以bd=(ak)d=akd=an=e且|b|二d。从而H中的兀素是两两不同的，易证HG。故|H匸d。所以是G的一个d阶子群。设H是G的任一d阶子群。则由定理5.4.4知，H=(am)，其中am是H中a的111最小正幂，且|H|二-。因为|H|=d，所以m二-二k,卩H二H。从而H是G的惟一dmd1阶子群。13、证明：对于剩余环Zn,+n,Xn，n是素数当且仅当Zn中无零因子。证明：(1)u设Zn中无零因子nn因此nJ工0,的一对零因子，矛盾(2)n，往证n是素数。假设n-nin2】n2H所以，nlVn0,nJ2是素数。不是素数，则存在整数n1，n2，使Xn2=0.即n,n2是Zn212n设n是素数，若Z,+,X)中有零因子i,jGZ，使得i,j工nnnJnJ0,iXnj=0,则ij=0,因而nIij.由于n是素数，故nIi或n丨j.即】i=0或j=0，矛盾。所以，Z,+,X中无零因子。JJnnn14、假设X,*是一个代数系统，*是火上的二元运算。如果*运算是可结合的，并且对任意的x,yGX，当x*y=y*x时，有x=y。证明X中每个元素都是幂等元。证明：对任意的元素xeX，由于*运算可结合，所以有(x*x)*x=x*(x*x)由题设条件可知x*x=x由x的任意性则每个元素都是等幂元。15、假设X,心是一个代数系统，和分别是X上的二元运算。若对任意的x,yGX，有xy=x。证明：g对于是可分配的。证明：对任意的x,y,zeX，xg(yz)=xgy=(xgy)(xgz)而(yz)x=yx=(ygx)(zgx)证毕。16、假设VX,*和VY,0是两个代数系统，*和0分别是X和Y上的二元运算，并且满足结合律和交换律。1和f2都是代数系统X到Y的同态映射。令:h:XTY,对任意的xeX，h(x)=f1(x)0f2(x)。证明h是代数系统X到Y的同态映射证明：由h的定义可知h是X到Y的函数对任意的x,yeXh(x*y)=fl(x*y)gf2(x*y)=(fl(x)gfl(y)g(f2(x)gf2(y)由于运算满足结合律和交换律，所以上式=(f1(x)gf2(x)g(f1(y)gf2(y)=h(x)gh(y)h对于运算保持。所以h是代数系统X到Y的同态映射。证毕17、假设G,*是一个群，|G|=2n。证明G中至少有一个周期为2的元素。证明：因为群G,*中的元素互逆，即元素a的逆元是a，a的逆元是a。因而G中逆元不等于自身的元素必为偶数个(包括零个)。但是G包含偶数个元素，因此G的逆元等于自身的元素个数也必为偶数个，而G的单位元e的逆元是其本身，所以G中至少还有另一个元素a其逆元是它本身，即a-i=a。从而a2=a*a=a*a-i=e，并且eza。即a是一个周期为2的元素所以至少存在一个周期为2的元素。18、已知G=1,2,3,4,5,6，水为模7乘法，试说明G,x是否构成77群？是否为循环群？若是，生成元是什么？它是否有子群？若有，子群是什么？解：列出运算表如下：X7123456112345622461353362514441526355316426654321由运算表和模7乘法的性质可知G,x?是群。是循环群，生成元是3，5。它有子群，子群是：G,x7，1,x7，1,6,x7，1,2,4,x719、假设f,g是群X,*到群Y,Q的同态映射。证明H,*是群X,*的子群，其中H=x|xeX,并且f(x)=g(x)。证明：由H的定义可知HX。假设ex是群X,*的单位元，ey是vY,g的单位元由xyf,g是群X,*到群Y,0的同态映射可知f(ex)=ey=g(ex)从而exeH，故H非空。对于任意的a,beH，则有f(a)=g(a)，f(b)=g(b)由f,g是群X,*到群Y,g的同态映射可知f(b-i)=(f(b)-i=(g(b)-i=g(b-i)因此f(a*b-i)=f(a)gf(b-i)=g(a)gg(b-i)=g(a*b-i)所以a*b-ieH因此H,*是群X,*的子群。证毕。20、假设X,*是一个代数系统，*是X上的二元运算。对任意的x,y,z,weX，有x*x=x，并且(x*y)*(z*w)=(x*z)*(y*w)。证明：x*(y*z)=(x*y)*(x*z)证明：对任意的x,y,zeX有x*x=x所以x*(y*z)=(x*x)*(y*z)=(x*y)*(x*z)(由已知条件)证毕。21、假设S=a，b,c，X=v0,S,c，u,Y=a,b,S,n,u,。二元运算符和一元运算符分别是集合的交、并、补运算。问X和Y是否同构？为什么？答:X和Y不同构。因为Y=va,b,S,c,u,不是代数系统，补运算关于集合a,b,S不封闭。如果存在X和Y同构，则X是代数系统，Y一定是代数系统。由上可知产生矛盾。22、假设G,*是一个群。证明对于任意的a,beG,存在唯一的xeG，使得a*x=b。证明：由于G,*是一个群，所以对于任意元素a,beG，逆元aeG存在，并且x=a*beG，使得a*x=a*(a*b)=(a*a)*b=b假若还存在另一个元素ceG,使得a*c=b则c=e*c=(a*a)*c=a*(a*c)=a*b=x所以x唯一。证毕。23、设S,*是一个含幺半群，e是单位元。证明若任意的xGS,有x*x=e，贝9S,*是阿贝尔群。证明：对于任意的xeS,有x*x=e，因此x-i=x,所以vS,*是群。对任意的x,yeSx*y=x-1*y-1=(y*x)-1=y*x所以S,*是阿贝尔群证毕。24、已知G=0,l,2,3,4,5,+为模6加法，试说明G,+是否构成66群？是否为循环群？若是，生成元是什么？它是否有子群？若有，子群是什么？+6012345001234511234502234501334501244501235501234解：由运算表和模6加法的性质可知G,+6是群。是循环群，生成元是1,5。它有子群，子群是：G,+6，0,+6，0,3,+6，0,2,4,+625、假设G,*是群，C=aIaeG,并且对VxeG,a*x=x*a，证明vC,*是vG,*的子群。证明：(1)因为vG,*是群，所以存在单位元e。对VxeG,有e*x=x*e=x所以eeC,即C是非空的。又由C的定义可知：CcGo(2)对Va,beC，有a*x=x*a和b*x=x*b而(a*b)*x=a*(b*x)=a*(x*b)=(a*x)*b=(x*a)*b=x*(a*b)所以a*beC又对VaeC，有a*x=x*a又有a-1*a*x=a-1*x*a所以x=a-1*x*a而x*a-1=a-1*x*a*a-1=a-1*x所以a-1C