离散数学复习资料(2)

m故不同的单射有Cnm!＝n(n－1)(n―m―1)个。

(3)显然当|m|＝|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，故不同的双射有m!个。

十四、集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个？

解 X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个2到Y的二元关系总共有2mnmn，所以X

个。

十五、若是群，则对于任意的a、b∈G，必有惟一的x∈G使得a*x＝b。

证明 设e是群的幺元。令x＝a1*b，则a*x＝a*(a1*b)＝(a*a1)*b＝e*b＝b。所以，x＝a

－

－

－

－

1

*b是a*x＝b的解。

若x?∈G也是a*x＝b的解，则x?＝e*x?＝(a1*a)*x?＝a1*(a*x?)＝a1*b＝x。所以，x＝a1*b是a*x

－

－

－

－

＝b的惟一解。

十六、给定连通简单平面图G＝，且|V|＝6，|E|＝12。证明：对任意f∈F，d(f)＝3。

证明 由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是?d(f)＝2|E|＝24。若存在f∈

f?FF，使得d(f)＞3，则3|F|＜2|E|＝24，于是|F|＜8，与|F|＝8矛盾。故对任意f∈F，d(f)＝3。

6