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

Printable View

- March 26th 2011, 09:37 PMquineyCounting onto functions
How many onto functions are there from A to B, if |A| = 10 and |B| = 4?

- March 26th 2011, 11:02 PMTinyboss
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.

- March 26th 2011, 11:53 PMquiney
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 - March 27th 2011, 02:23 AMPlato