Counting Principles: All Surjections from A to B

[StopWatch]

Homework Statement

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

Homework Equations

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

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?

 

[sunjin09]

Homework Statement

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

Homework Equations

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

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?

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

 

[StopWatch]

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

 

[StopWatch]

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

 

[SammyS]

Homework Statement

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

Homework Equations

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

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?

Here's a somewhat easier problem that may help.

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

 

[sunjin09]

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

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

 

[SammyS]

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

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.

See the link: https://www.physicsforums.com/showthread.php?t=414380. In particular, look at "Homework Help."