1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting Principles: All Surjections from A to B

  1. Feb 2, 2012 #1
    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. jcsd
  3. Feb 2, 2012 #2
    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
     
  4. Feb 2, 2012 #3
    Do you mean n+1 x n x n-1 etc. ? And don't worry they're finite, thanks for the response.
     
  5. Feb 2, 2012 #4
    Also could you point me to somewhere that would prove why this is true?
     
  6. Feb 2, 2012 #5

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Here's a somewhat easier problem that may help.

    Count the surjections of C to B, (f: C → B) where |C| = |B| .
     
  7. Feb 2, 2012 #6
    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
     
  8. Feb 2, 2012 #7

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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."
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook