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!

Number of functions from one set to another

  1. Jan 24, 2013 #1
    1. The problem statement, all variables and given/known data

    How many functions are there from the set {1, 2, . . . , n}, where n is a positive integer, to the set {0, 1}
    a) that are one-to-one?
    b) that assign 0 to both 1 and n?
    c) that assign 1 to exactly one of the positive integers less than n?


    2. Relevant equations



    3. The attempt at a solution
    Since every element in the domain {1, 2, . . . , n} has two options in the codomain {0, 1} there a total of 2^n functions from the domain to the codomain.
    Also, I understand that to be a one-to-one relationship no element of the codomain is the image of more than one element in the domain.
    However, I'm unsure how to solve the problems. Any suggestions would be appreciated.
     
  2. jcsd
  3. Jan 24, 2013 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Start with a). The answer will depend on n. Suppose n=1, n=2 and n=3. What do you get in those cases?
     
  4. Jan 25, 2013 #3
    Sorry for the delay.

    a) If n = 1 then there are two choices for the first and only element in the domain.
    So, we have 2 functions if n = 1

    If n = 2 then there are two choices for the first element in the domain. Then, since one choice is taken there is one choice for the second element in the domain.
    So, we have 2 * 1 = 2 functions if n = 2.

    If n >= 3 then there will always be elements in the domain with no images to map to.
    So, we have 0 functions if n >= 3.
     
  5. Jan 25, 2013 #4

    dx

    User Avatar
    Homework Helper
    Gold Member

    I guess you know how to do part b.

    Hint for part c: there are n - 1 ways to choose an element less than n, and once you assign that element to 1, all the other elements except n must go to 0. Then you can assign either 0 or 1 to n.
     
  6. Jan 25, 2013 #5
    Actually I do need help with b). I don't understand what the problem is asking for.
     
  7. Jan 25, 2013 #6

    dx

    User Avatar
    Homework Helper
    Gold Member

    You said that the number of functions from {1, ..., n} to {0, 1} is 2n.

    Part (b) is the same, except there are only n - 2 elements instead of n, since two of the elements must always go to 0.

    If the function must assign 0 to both 1 and n then there are n - 2 numbers left which can be either 0 or 1.

    Given n - 2 elements, how many ways are there to map them to {0, 1}?
     
  8. Jan 25, 2013 #7
  9. Jan 25, 2013 #8

    dx

    User Avatar
    Homework Helper
    Gold Member

    Yep, that's the answer.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number of functions from one set to another
Loading...