(完整word版)山大离散练习分析.docVIP

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|=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是自反的。

对于任意的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