山大离散练习

1、Solvetherecurrencerelationan=an-1+an-2witha0=a1=1usinggeneratingfunction.2、Determinethenumberofthetermsintheexpansionof(x1+x1+…+x10)20.3、将m个无区别的球，放入n个有区别的盒子，在允许有空盒和不允许有空盒两种情况下分别讨论可能的放法数。4、求n元集合到m元集合单射、满射、双射的个数。5、用容斥原理求1~n中与n互素的元素个数。6、G,*是个群，x∈G，定义G中的运算“”为ab=a*x*b，对a,b∈G，证名G,也是群。证明：1）a,b∈G，ab=a*x*b∈G，运算是封闭的。2）a,b,c∈G，（ab）c=（a*x*b）*x*c=a*x*（b*x*c）=a（bc），运算是可结合的。3）a∈G，设E为的单位元，则aE=a*x*E=a，得E=x-1，存在单位元。4）a∈G，ax-1*a-1*x-1=a*x*x-1*a-1*x-1=x-1=E，x-1*a-1*x-1a=x-1*a-1*x-1*x*a=x-1=E,a的逆元为x-1*a-1*x-1，每个元素都有存在。所以G,也是个群7、设G,*是有限交换群，a,b∈G，|a|=m,|b|=n,m,n是整数，且GCD（m,n）=1即m,n互素，证明：|ab|=mn证明：设|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、设S，＋，·是环，1是其乘法幺元，在S上定义运算和：ab＝a＋b＋1，ab＝a＋b＋a·b。（1）证明S，，是一个环。（2）给出S，，的关于运算和的单位元。证明：（1）对任意a、b、c∈S，则（ab）c＝ab＋c＋1＝a＋b＋c＋1＋1，a（bc）＝a＋bc＋1＝a＋b＋c＋1＋1，于是（ab）c＝a（bc），即满足结合律。ab＝a＋b＋1＝b＋a＋1＝ba，所以是可交换的。a（-1）＝a＋（-1）＋1＝a＝（-1）a，所以-1是单位元。a（-1-1-a）＝a＋（-1-1-a）＋1＝-1＝（-1-1-a）a，所以-1-1-a是a的逆元。综上可知，S，是一个交换群。（2）（ab）c＝ab＋c＋（ab）·c＝a＋b＋a·b＋c＋（a＋b＋a·b）·c＝a＋b＋a·b＋c＋a·c＋b·c＋a·b·ca（bc）＝a＋bc＋a·（bc）＝a＋b＋c＋b·c＋a·（b＋c＋b·c）＝a＋b＋c＋b·c＋a·b＋a·c＋a·b·c所以（ab）c＝a（bc），即满足结合律。又a0＝a＋0＋a·0＝a，0a＝0＋a＋0·a＝a，0是单位元因而S，是有幺元的半群。a（bc）＝a＋bc＋a·（bc）＝a＋b＋c＋1＋a·（b＋c＋1）＝2a＋b＋c＋a·b＋a·c＋1（ab）（ac）＝ab＋ac＋1＝a＋b＋a·b＋a＋c＋a·c＋1＝2a＋b＋c＋a·b＋a·c＋1a（bc）＝（ab）（ac），所以对满足分配律。从而S，，是一个环。9、设G是一个群,e是G的单位元,H是G的子群.如下定义关系R：1121212,,,.aaGaaRaeaH证明R是G上的等价关系.证明:对于任意的a∊G，∵aea-1=e∊H，∴a,a∊R，故R是自反的。对于任意的a，b∊G，若a,b∊R，∴aeb-1∊H，∴(aeb-1)-1=(ab-1)-1=ba-1∊H，∴b,a∊R，故R是对称的。对于任意的a,b,c∊G，若a,b∊R，b,c∊R，∴aeb-1∊H且bec-1∊H，∴(aeb-1)(bec-1)=ac-1∊H，∴a,c∊R，故R是传递的10、G,*是个群，u∈G，定义G中的运算“”为ab=a*u-1*b，对任意a,b∈G，求证：G,也是群。证明：1）a,b∈G，ab=a*u-1*b∈G，运算是封闭的。2）a,b,c∈G，（ab）c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a（bc），运算是可结合的。3）a∈G，设E为的单位元，则aE=a*u-1*E=a，得E=u，存在单位元。4）a∈G，ax=a*u-1*x=E，x=u*a-1*u，则xa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。所以G,也是个群11、证明有限群中阶（周期）大于2的元素的个数必定是偶数。证明x与其逆元x-1的周期相同，又当x的周期大于2时，x≠x-1。定义映射f:x→x-1,是群中的双射函数，所以阶大于2的元素成对出现（x与其逆元x-1是一对），故其个数必定是偶数。12、证明n阶循环群的子群的个数恰为n的正因子数。证明：对n的每一正因子d，令k=dn,b=ak,H={e,b,b2,…,bd-1}。因为|a|=n,所以bd=(ak)d=akd=an=e且|b|=d。从而H中的元素是两两不同的，易证HG。故|H|=d。所以是G的一个d阶子群。设H1是G的任一d阶子群。则由定理5.4.4知，H1＝(am)，其中am是H1中a的最小正幂，且|H|=mn。因为|H|=d，所以m=dn=k，即H=H1。从而H是G的惟一d阶子群。13、证明：对于剩余环〈Zn，＋n，×n〉，n是素数当且仅当Zn中无零因子。证明：（1）设Zn中无零因子，往证n是素数。假设n不是素数，则存在整数n1，n2，使n＝n1n2１＜n1≤n2＜n因此［n1］≠［０］，［n2］≠［０］，但［n1］×n［n2］＝［０］.即［n1］，［n2］是Zn的一对零因子，矛盾。所以，n是素数。（2）设n是素数，若〈Zn，＋n，×n〉中有零因子［i］，［j］∈Zn，使得［i］，［j］≠［０］，［i］×n［j］=［０］，则［ij］＝［０］，因而n｜ij．由于n是素数，故n｜i或n｜j．即［i］＝［０］或［j］＝［０］，矛盾。所以，〈Zn，＋n，×n〉中无零因子。14、假设X,*是一个代数系统，*是X上的二元运算。如果*运算是可结合的，并且对任意的x,yX，当x*y=y*x时，有x=y。证明X中每个元素都是幂等元。证明：对任意的元素xX，由于*运算可结合，所以有(x*x)*x=x*(x*x)由题设条件可知x*x=x由x的任意性则每个元素都是等幂元。15、假设X,,是一个代数系统，和分别是X上的二元运算。若对任意的x,yX，有xy=x。证明：对于是可分配的。证明：对任意的x,y,zX，x(yz)=xy=(xy)(xz)而(yz)x=yx=(yx)(zx)证毕。16、假设X,*和Y,是两个代数系统，*和分别是X和Y上的二元运算，并且满足结合律和交换律。f1和f2都是代数系统X到Y的同态映射。令：h:XY，对任意的xX，h(x)=f1(x)f2(x)。证明h是代数系统X到Y的同态映射证明：由h的定义可知h是X到Y的函数对任意的x,yXh(x*y)=f1(x*y)f2(x*y)=(f1(x)f1(y))(f2(x)f2(y))由于运算满足结合律和交换律，所以上式=(f1(x)f2(x))(f1(y)f2(y))=h(x)h(y)h对于运算保持。所以h是代数系统X到Y的同态映射。证毕17、假设G,*是一个群，|G|=2n。证明G中至少有一个周期为2的元素。证明：因为群G,*中的元素互逆，即元素a的逆元是a’，a’的逆元是a。因而G中逆元不等于自身的元素必为偶数个（包括零个）。但是G包含偶数个元素，因此G的逆元等于自身的元素个数也必为偶数个，而G的单位元e的逆元是其本身，所以G中至少还有另一个元素a其逆元是它本身，即a-1=a。从而a2=a*a=a*a-1=e，并且ea。即a是一个周期为2的元素所以至少存在一个周期为2的元素。18、已知G={1,2,3,4,5,6}，7为模7乘法，试说明G,7是否构成群？是否为循环群？若是，生成元是什么？它是否有子群？若有，子群是什么？解：列出运算表如下：由运算表和模7乘法的性质可知G,7是群。是循环群，生成元是3，5。它有子群，子群是：G,7，{1},7，{1,6},7，{1,2,4},7712345611234562246135336251444152635531642665432119、假设f,g是群X,*到群Y,的同态映射。证明H,*是群X,*的子群，其中H={x|xX,并且f(x)=g(x)}。证明：由H的定义可知HX。假设ex是群X,*的单位元，ey是Y,的单位元由f,g是群X,*到群Y,的同态映射可知f(ex)=ey=g(ex)从而exH，故H非空。对于任意的a,bH，则有f(a)=g(a)，f(b)=g(b)由f,g是群X,*到群Y,的同态映射可知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-1H因此H,*是群X,*的子群。证毕。20、假设X,*是一个代数系统，*是X上的二元运算。对任意的x,y,z,wX，有x*x=x，并且(x*y)*(z*w)=(x*z)*(y*w)。证明：x*(y*z)=(x*y)*(x*z)证明：对任意的x,y,zX有x*x=x所以x*(y*z)=(x*x)*(y*z)=(x*y)*(x*z)（由已知条件）证毕。21、假设S={a,b,c}，X={,S},,,~，Y={{a,b},S},,,~。二元运算符,和一元运算符~分别是集合的交、并、补运算。问X和Y是否同构？为什么？答：X和Y不同构。因为Y={{a,b},S},,,~不是代数系统，补运算~关于集合{{a,b},S}不封闭。如果存在X和Y同构，则X是代数系统，Y一定是代数系统。由上可知产生矛盾。22、假设G,*是一个群。证明对于任意的a,bG，存在唯一的xG，使得a*x=b。证明：由于G,*是一个群，所以对于任意元素a,bG，逆元a’G存在，并且x=a’*bG，使得a*x=a*(a’*b)=(a*a’)*b=b假若还存在另一个元素cG，使得a*c=b则c=e*c=(a’*a)*c=a’*(a*c)=a’*b=x所以x唯一。证毕。23、设S,*是一个含幺半群，e是单位元。证明若任意的xS，有x*x=e，则S,*是阿贝尔群。证明：对于任意的xS，有x*x=e，因此x-1=x，所以S,*是群。对任意的x,ySx*y=x-1*y-1=(y*x)-1=y*x所以S,*是阿贝尔群证毕。24、已知G={0,1,2,3,4,5}，+6为模6加法，试说明G,+6是否构成群？是否为循环群？若是，生成元是什么？它是否有子群？若有，子群是什么？解：由运算表和模6加法的性质可知G,+6是群。是循环群，生成元是1，5。它有子群，子群是：G,+6，{0},+6，{0,3},+6，{0,2,4},+625、假设G,*是群，C={a|aG,并且对xG,a*x=x*a}，证明C,*是G,*的子群。证明：（1）因为G,*是群，所以存在单位元e。对xG，有e*x=x*e=x所以eC，即C是非空的。又由C的定义可知：CG。（2）对a,bC，有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*