# Counting Principles: All Surjections from A to B

1. Feb 2, 2012

### StopWatch

1. The problem statement, all variables and given/known data

Count all surjections of A to B, (f: A ---> B) where |A| = |B| + 1

2. Relevant equations

None? This is just a problem I came across online.

3. The attempt at a solution

I'm really not sure. This isn't technically homework, but I'm just looking for a good method. I thought maybe the pigeonhole principle might help?

2. Feb 2, 2012

### sunjin09

If |B|=n is finite, then there are n*n*(n-1)*(n-2)*...*1 ways to arrange n+1 object ONTO n slots; if |B| is infinite, then the answer is uncountable

3. Feb 2, 2012

### StopWatch

Do you mean n+1 x n x n-1 etc. ? And don't worry they're finite, thanks for the response.

4. Feb 2, 2012

### StopWatch

Also could you point me to somewhere that would prove why this is true?

5. Feb 2, 2012

### SammyS

Staff Emeritus
Here's a somewhat easier problem that may help.

Count the surjections of C to B, (f: C → B) where |C| = |B| .

6. Feb 2, 2012

### sunjin09

My apologies, the answer should be (n+1)!*n/2, because you first choose 2 element to map to a single slot, that is (n+1)n/2, then you permute the n groups of elements onto n slot, that's n!, so the total is (n+1)!*n/2

7. Feb 2, 2012

### SammyS

Staff Emeritus
An important principle of these Forums is to help those who post questions to discover the solutions for themselves. It's not to give the answers.