Suppose $X$ has $N$ elements and $Y$ has $M$ elements. How many one to one function are there from $X$ to $Y$? How many onto function are there from $X$ to $Y$?
The number of one to one functions is $N!$,
because the max mapping to $Y$ is $N$.The number of onto functions is $M^N – M + M((M-1)^N-(M-1))$,
because the the range of the mapping has to cover all $M$ element
Am I right? Thanks.
Best Answer
Not quite.
For the one-to-one function, each element in $X$ is mapped to a unique element in $Y$. Therefore, there are $M$ ways to map the first element in $X$, and $M-1$ ways to map the second one, etc. There should be totally $M!/(M-N)!$ ways of one-to-one mapping when $M\geq N$. When $M<N$, you cannot get any one-to-one mapping.
For the onto function, there seems to be no simple, non-recusive formula for the number of onto functions.
See Stirling number