Question

关于离散数学的函数

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是满射.

Answer 1

(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必然是双设。
第二问的解答与第一问原理一样。