If $A$ is a set with $m$ elements and $B$ a set with $n$ elements, how many functions are there from $A$ to $B$. If $m=n$ how many of them are bijections?
I got $n^m$ for my first answer.
I wasn't sure for the bijection bit is it just $n$?
Asked
Active
Viewed 86 times
2 Answers
1
The number of functions from A to B is equal to the number of lists of m elements where each element of the list is an element of b. Since we have n choices for each the answer is $n^m$
For the second one we have that n=m. Call the elements of A: $a_1,a_2...a_n$. therefore the number of bijections from A to B is the number of lists where $b_\in B$ of the form $b_1,b_2...b_n$ such that if $x\neq$ y then $b_x \neq b_y$
But this is just the number of permutations of n elements which is $n!$
Because we have n choices for the first element, n-1 choices for the second, and in general $n-k+1$ choices for the $k$'th element.
Asinomás
- 105,651
1
Your first answer is right, but your second answer is wrong. Just try with $n = 3$ to see what happens. From there you should be able to guess the right answer.
J.-E. Pin
- 40,163