# Functions Problem 7

### Solution, Method 1

There are $$2^5 = 32$$ functions from A to B. Most of these are onto, the only exceptions being the two functions that map all elements of A to the same element of B. So there are $$32- 2 = 30$$ onto functions from A to B. This method is very slick but also harder to come up with. A student found it, not the course staff.

### Solution, Method 2

Since it doesn't matter what the elements of A and B are named, let's suppose that $$A = \{1,2,3,4,5\}$$ and $$B = \{x,y\}$$. Now, let's divide up our problem based on how many elements of A map to x. Since the function is onto, this number must be between 1 and 4. Case 1: 1 element of A maps onto x. There are five possibilities for what this element is. Case 2: 2 elements of A map onto x. There are $$5 \cdot 4 = 20$$ ways to choose an ordered pair of two elements. But we don't care about the order, so we need to divide by 2. So there are 10 ways to choose a pair of two elements. Case 3: 3 elements of A map onto x. This is similar to case 2, just reverse the roles of x and y. Case 4: 4 elements of A map onto y. This is similar to case 1. So, in total, we have $$5 + 10 + 10 + 5 = 30$$ ways to construct our onto function. This method is more plodding but also easier to come up with.