山大離散練習(xí)

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個無區(qū)別的球，放入n個有區(qū)別的盒子，在允許有空盒和不允許有空盒兩種情況下分別討論可能的放法數(shù)。4、求n元集合到m元集合單射、滿射、雙射的個數(shù)。5、用容斥原理求1n中與n互素的元素個數(shù)。6、<G,*>是個群，xG，定義G中的運算“D”為aDb=a*x*b，對&quo

2、t;a,bG，證名<G, D>也是群。證明：1）"a,bG，aDb=a*x*bG，運算是封閉的。2）"a,b,cG，（aDb）Dc=（a*x*b）*x*c=a*x*（b*x*c）=aD（bDc），運算是可結(jié)合的。3）"aG，設(shè)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，每個元素都有存在。所以<G, D>也

3、是個群7、設(shè)<G,*>是有限交換群，a,bG，|a|=m,|b|=n,m,n是整數(shù)，且GCD（m,n）=1即m,n互素，證明：|ab|=mn證明：設(shè)|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、設(shè)<S，·>是環(huán)，1是其乘法幺元，在S上定義運算 和 ：aÅbab1，ababa·b。（1）證明<S，&#

4、197;，>是一個環(huán)。（2）給出<S，Å，>的關(guān)于運算 Å 和 的單位元。證明：（1）對任意a、b、cS，則（aÅb）ÅcaÅbc1abc11，aÅ（bÅc）abÅc1abc11，于是（aÅb）ÅcaÅ（bÅc），即Å滿足結(jié)合律。aÅbab1ba1bÅa，所以Å是可交換的。aÅ（-1）a（-1）1a（-1）Åa，所以-1是 Å 單位元。aÅ（-1-1-a）a（-1-1-a）1-1

5、（-1-1-a）Åa，所以-1-1-a是a的逆元。綜上可知，<S，Å>是一個交換群。（2）（ab）cabc（ab）·caba·bc（aba·b）·caba·bca·cb·ca·b·ca（bc）abca·（bc）abcb·ca·（bcb·c）abcb·ca·ba·ca·b·c所以（ab）ca（bc），即滿足結(jié)合律。又a0a0a·0a，0a0a0·aa，0 是 單位元因

6、而<S，>是有幺元的半群。a（bÅc）abÅca·（bÅc）abc1a·（bc1）2abca·ba·c1（ab）Å（ac）abac1aba·baca·c12abca·ba·c1a（bÅc）（ab）Å（ac），所以 對 Å 滿足分配律。從而<S，Å，>是一個環(huán)。9、設(shè) G是一個群,e是G的單位元,H是G的子群. 如下定義關(guān)系R： 證明R是G上的等價關(guān)系.證明: 對于任意的aG， aea-1=eH， <a,a&

7、gt; R，故R是自反的。 對于任意的a，bG，若<a,b> R， aeb-1H，(aeb-1)-1=(ab-1)-1=ba-1H， <b,a> R，故R是對稱的。 對于任意的a,b,cG，若<a,b> R，<b,c> R， aeb-1H且 bec-1H， (aeb-1) (bec-1)=ac-1H， <a,c> R，故R是傳遞的10、<G,*>是個群，uG，定義G中的運算“D”為aDb=a*u-1*b，對任意a,bG，求證：<G, D>也是群。證明：1）"a,bG，aDb=a*u-1*bG，運算是封

8、閉的。2）"a,b,cG，（aDb）Dc=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=aD（bDc），運算是可結(jié)合的。3）"aG，設(shè)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，每個元素都有逆元。所以<G, D>也是個群11、證明有限群中階（周期）大于2的元素的個數(shù)必定是偶數(shù)。證明x與其逆元x-1的周期相同，又當(dāng)x的周期大于2時，xx-1。定義映射f: xx-1,是群中的雙射函數(shù)，所以階大于2的元素成對出現(xiàn)

9、（x與其逆元x-1是一對），故其個數(shù)必定是偶數(shù)。12、 證明n階循環(huán)群的子群的個數(shù)恰為 n的正因子數(shù)。證明：對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階子群。設(shè)H1是G的任一d階子群。則由定理5.4.4知，H1(am)，其中am是H1中a 的最小正冪，且|H|=。因為|H|=d，所以m=k，即H=H1。從而H是G的惟一d階子群。13、證明：對于剩余環(huán)Zn，n，×n ，n是素數(shù)當(dāng)且僅當(dāng)Zn中無零因子。證明：（1）設(shè)Zn中無零

10、因子，往證n是素數(shù)。假設(shè)n不是素數(shù)，則存在整數(shù)n1，n2，使nn1n2n1n2n因此 n1，n2，但n1×nn2. 即n1，n2是Zn的一對零因子，矛盾。所以，n是素數(shù)。（2）設(shè)n是素數(shù)，若Zn，n，×n 中有零因子i，jZn，使得i，j，i×nj=，則ij，因而 nij由于n是素數(shù)，故ni 或 nj即i 或 j，矛盾。所以，Zn，n，×n 中無零因子。14、假設(shè)<X,*>是一個代數(shù)系統(tǒng)，*是X上的二元運算。如果*運算是可結(jié)合的，并且對任意的x,yÎX，當(dāng)x*y=y*x時，有x=y。證明X中每個元素都是冪等元。證明：對任意的元素x&

11、#206;X，由于*運算可結(jié)合，所以有 (x*x)*x=x*(x*x) 由題設(shè)條件可知x*x=x 由x的任意性則每個元素都是等冪元。15、假設(shè)<X,Å,Ä>是一個代數(shù)系統(tǒng)，Å和Ä分別是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)Å

12、;(zÄx)證畢。16、 假設(shè)<X,*>和<Y, Ä>是兩個代數(shù)系統(tǒng)，*和Ä分別是X和Y上的二元運算，并且滿足結(jié)合律和交換律。f1和f2都是代數(shù)系統(tǒng)X到Y(jié)的同態(tài)映射。令：h:X®Y，對任意的xÎX，h(x)=f1(x) Äf2(x)。證明h是代數(shù)系統(tǒng)X到Y(jié)的同態(tài)映射證明：由h的定義可知h是X到Y(jié)的函數(shù) 對任意的x,yÎX h(x*y)=f1(x*y) Äf2(x*y) =(f1(x)Äf1(y)Ä(f2(x)Äf2(y) 由于運算Ä滿足結(jié)合律和交換律，

13、所以上式=(f1(x)Äf2(x)Ä(f1(y)Äf2(y)=h(x)Ä h(y)h對于運算保持。所以h是代數(shù)系統(tǒng)X到Y(jié)的同態(tài)映射。證畢 17、假設(shè)<G,*>是一個群，|G|=2n。證明G中至少有一個周期為2的元素。證明：因為群<G,*>中的元素互逆，即元素a的逆元是a，a的逆元是a。因而G中逆元不等于自身的元素必為偶數(shù)個（包括零個）。但是G包含偶數(shù)個元素，因此G的逆元等于自身的元素個數(shù)也必為偶數(shù)個，而G的單位元e的逆元是其本身，所以G中至少還有另一個元素a其逆元是它本身，即a-1=a。從而 a2=a*a=a*a-1=e，并且e&

14、#185;a。即 a是一個周期為2 的元素所以至少存在一個周期為2的元素。18、已知G=1,2,3,4,5,6，´7為模7乘法，試說明<G,´7>是否構(gòu)成群？是否為循環(huán)群？若是，生成元是什么？它是否有子群？若有，子群是什么？解：列出運算表如下：´7123456112345622461353362514441526355316426654321由運算表和模7乘法的性質(zhì)可知<G,´7>是群。是循環(huán)群，生成元是3，5。它有子群，子群是：< G,´7>，< 1,´7>，< 1,6,

15、0;7>，< 1,2,4,´7>19、假設(shè)f,g是群<X,*>到群<Y, Ä>的同態(tài)映射。證明<H,*>是群<X,*>的子群，其中 H=x|xÎX ,并且f(x)=g(x)。證明：由H的定義可知HÍX。假設(shè)ex是群<X,*>的單位元，ey是<Y, Ä>的單位元 由f,g是群<X,*>到群<Y, Ä>的同態(tài)映射可知 f(ex)= ey=g(ex) 從而exÎH，故H非空。 對于任意的a, bÎH，則有f(

16、a)=g(a)，f(b)=g(b) 由f,g是群<X,*>到群<Y, Ä>的同態(tài)映射可知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、假設(shè)<X,*>是一個代數(shù)系統(tǒng)，*是X上的二元運算。對任意的x,y,z,wÎX，有x*x=x，并且(x*y)*(z*w)=(x*z)*(y*w)。證明：x*(y*z)=(x*y)*(x*

17、z)證明：對任意的x,y,zÎX 有 x*x=x 所以x*(y*z)= (x*x)*(y*z)=(x*y)*(x*z) （由已知條件）證畢。21、假設(shè)S=a,b,c，X=<Æ,S,Ç,È,>，Y=<a,b,S,Ç,È,>。二元運算符Ç,È和一元運算符分別是集合的交、并、補運算。問X和Y是否同構(gòu)？為什么？答：X和Y不同構(gòu)。因為Y=<a,b,S,Ç,È,>不是代數(shù)系統(tǒng)，補運算關(guān)于集合a,b,S不封閉。如果存在X和Y同構(gòu)，則X是代數(shù)系統(tǒng)，Y一定是代數(shù)系統(tǒng)。由上可知產(chǎn)

18、生矛盾。22、假設(shè)<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、設(shè)<S,*>是一個含幺半群，e是單位元。證明若任意的xÎS，有x*x=e，則<S,*>是阿貝爾群。證明：對于任意的xÎS，有x*x=e，因此x-1=x，所以<S,*>是群。 對任意的x,yÎS x*y= x-1*y-1=(y*x)-1=y*x 所以<S,*>是阿貝爾群證畢。24、已知G=0,1,2,3,4,5，+6為模6加法，試說明<G,+6>是否構(gòu)成群？是否為循