山大离散练习案例.doc

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、用容斥原理求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|=mn 8、设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·c a(（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＋1 a(（b(c）＝（a(b）(（a(c）， 所以 ( 对 ( 满足分配律。 从而S，(，(是一个环。 9、设 G是一个群,e是G的单位元,H是G的子群. 如下定义关系R： 证明R是G上的等价关系. 证明: 对于任意的a?G，∵ aea-1=e?H， ∴ a,a ? R，故R是自反的。 对于任意的ab?G，若a,b? R， ∴ aeb-1?H，∴(aeb-1)-1=(ab-1)-1=ba-1?H， ∴ b,a ? R，故R是对称的。 对于任意的a,b,c?Ga,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为(的单位