How to determine number of Injective function from a set of $n$ element to a set of $n$ element and number of onto function on the same set to itself?
Thank you for your help.
Asked
Active
Viewed 160 times
2 Answers
2
We may as well assume that the set of $n$ elements is $S = \{1,2,3,\ldots,n\}$.
Then a mapping $f:S \to S$ can be represented by the sequence of values $T=\big(f(1), f(2), \ldots, f(n)\big)$. If the mapping is injective, it means there are no repetitions in the sequence $T$, so $T$ is just a permutation of $S$. The number of such permutations is $n!$.
If the mapping $f$ is onto, then the sequence $T$ contains every element of $S$, so it's again a permutation of $S$. So the answer is again $n!$.
bubba
- 43,483
- 3
- 61
- 122
1
For the first element you have $n$ possibilities for the second $n-1$ (it can not go to the same element, because of injectivity) etc. So you will get $n!$ different functions.
Kaladin
- 1,485
-
In other words, it is the same as the number of bijections, i.e. permutations of ${1,2,\ldots,n}$. – Andrew Kelley Mar 08 '14 at 02:37