# Counting onto functions

• Mar 26th 2011, 10:37 PM
quiney
Counting onto functions
How many onto functions are there from A to B, if |A| = 10 and |B| = 4?
• Mar 27th 2011, 12:02 AM
Tinyboss
Let $f:A\to B$ be onto. Then some element of A has to go to the first element of B, and there are 10 possibilities for that. Some other element has to go to the second element of B, so 9 possibilities there, and so on. So there are 10*9*8*7 ways to choose four elements of A and send them onto the four elements of B. Once that's done, f is surjective, and we may choose its value on the other 6 elements of A arbitrarily, so the total number is 10*9*8*7*4^6.
• Mar 27th 2011, 12:53 AM
quiney
I'm getting something different. The book says the formula for the number of onto functions from a set with m elements to a set with n elements, with m ≥ n, is

n^m - C(n, 1)(n - 1)^m + C(n, 2)(n - 2)^m - ... + (-1)^(n - 1)C(n, n - 1)*1^m

Letting m = 10 and n = 4, we get

4^10 - C(4, 1)*3^10 + C(4, 2)*2^10 - C(4, 3) = 4^10 - (4!/3!)*3^10 + [4!/(2!*2!)]*2^10 - 4!/3! = 4^10 - 4*3^10 + 6*2^10 - 4 = 818,520

onto functions from A to B
• Mar 27th 2011, 03:23 AM
Plato
Quote:

Originally Posted by quiney
How many onto functions are there from A to B, if |A| = 10 and |B| = 4?

Unfortunately the method suggested in reply #2 results is a gross over-count. This is a standard inclusion/exclusion problem. The number of surjections (onto functions) from a set of N to a set of K is $\displaystyle\sum\limits_{j = 0}^K {( - 1)^j \binom{K}{j}\left( {K - j} \right)^N }$. Note we must have $N\ge K.$

You should the answer here is $818520$.