Thread: Counting onto functions

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

Let 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.

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

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 . Note we must have

You should the answer here is .