关于离散数学的函数

题目

关于离散数学的函数
1.设X,Y是集合,|X|=m,|Y|=n,问:(1)若存在从X到Y的满射函数,那么有多少个不同的满射函数?(2)若存在从X到Y的双射函数,那么有多少个不同的双射函数?
2.设函数f:X→Y,g:Y→Z,证明:(1)如果f,g是双射的,则复合函数g○f也是双射的.(2)如果f○g是满射的,则f是满射.

答案

(1)若存在从X到Y的满射函数,则必有m>=n 那么,先从m中取出n个,用这个组合数乘以n!在用剩下的没m-n 个数随便映射过去,又有n的m-n次方个.最后答案是
组合数*n!*（n的m-n次方）.
若存在双设,则必有m=n,此时不同的双设共有n!个
(2)g○f是从X->Z的映射,由g○f(x)=g○f(y)得f(x)=f(y),又得x=y
（这是因为f,g都是双射）,从而说明g○f是单设,若其不是满射,则存在z
使得无论如何选取x,都有g○f（x）不等于z,但g是满射,则存在一个y,无论如何选取x都有f(x)不等于y,这与f是满射矛盾,故g○f也是满射,因此g○f必然是双设.
第二问的解答与第一问原理一样.