Combinatorics (Surjective functions)

Douglasm · 2010-02-18 03:41:45

I'm having some difficulty to understand this question:

Let A and B be two finite sets, with |A| = n and |B| = p (n is greater or equal to p). Determine the number of surjective functions f: A -> B.

Can anyone explain me how does it works?

mathsyperson · 2010-02-18 06:51:59

A function A -> B is surjective if every element of B is mapped to by some element of A.

For example, taking A = {1, 2, 3, 4, 5} and B = {7, 8, 9}...

The function with the following maps:

1 -> 7
2 -> 8
3 -> 9
4 -> 8
5 -> 7

is surjective, because 7, 8 and 9 all have something that maps to them.

This function:

1 -> 9
2 -> 8
3 -> 9
4 -> 8
5 -> 9

is not surjective, because 7 isn't mapped to by anything.

This may not be the best way, but I'd try to solve the problem by building up the function piece by piece.

f(1) doesn't really matter - whatever you assign it to, the value will be 'new'.
There are therefore 3 functions f: {1} -> {7, 8, 9} that map to one element.

f(2) might map to the same thing as f(1), or it might map to something different (there are two ways of doing this).

So there are 3 functions f: {1, 2} -> {7, 8, 9} that map to one element, and 6 functions that map to two.

Now we can consider f(3).
If you build on a function that maps to one element, there is one way of keeping it as a function that maps to one, and two ways to change it into a function that maps to two.

On the other hand, if you build on a function that maps to two elements, there are two ways to keep it that way, and one way of mapping it to all three.

Overall then, there are 3 functions f:{1,2,3} -> {7,8,9} that map to one element,
18 functions that map to two elements, and 6 functions that map to all three.

You can use the same inductive reasoning to find the numbers for after you add in f(4) and f(5), and it turns out that there are 150 surjective functions where |A| = 5 and |B| = 3.

---

Bit long-winded, but it works at least. Maybe someone else will come along with a much better way.

Douglasm · 2010-02-18 07:49:10

Thanks mathsyperson! I could solve the problem. I counted all the possible f: A -> B (that would be p^n), then I subtracted from it all the non-surjective functions (that would be (p-1)^n, (p-2)^n, etc.). Finally the awser became:

Took me some time but I finally got it!

mathsyperson · 2010-02-18 08:33:14

Ah, I like that way much more. Nice work.

Math Is Fun Forum

#1 2010-02-18 03:41:45

Combinatorics (Surjective functions)

#2 2010-02-18 06:51:59

Re: Combinatorics (Surjective functions)

#3 2010-02-18 07:49:10

Re: Combinatorics (Surjective functions)

#4 2010-02-18 08:33:14

Re: Combinatorics (Surjective functions)

Board footer