Results 1 to 6 of 6

Math Help - Number of functions from one set to another

  1. #1
    Junior Member
    Joined
    Oct 2012
    From
    Wisconsin
    Posts
    29
    Thanks
    1

    Number of functions from one set to another

    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?

    For a) my answer is 2 if n = 1 or n = 2 and 0 if n > 2.
    But I'm stuck on both b) and c). Any help would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1784
    Awards
    1

    Re: Number of functions from one set to another

    Quote Originally Posted by nicnicman View Post
    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?
    For a) my answer is 2 if n = 1 or n = 2 and 0 if n > 2.
    But I'm stuck on both b) and c). Any help would be appreciated.
    There are a total of 2^n functions \{1, 2, \cdots , n\}\to\{0,1\}.

    b) The answer is 1 if n=1, or 2^{n-2} if n\ge 2..

    Now, you reply with an explication. If you do we can help with c).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2012
    From
    Wisconsin
    Posts
    29
    Thanks
    1

    Re: Number of functions from one set to another

    Well, that's the hard part (the answer's in the back of the book), but I'll work on it.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1784
    Awards
    1

    Re: Number of functions from one set to another

    Quote Originally Posted by nicnicman View Post
    Well, that's the hard part (the answer's in the back of the book), but I'll work on it.

    Well that I suggest that you draw diagrams.
    Do it for n=2,3,4,5.
    Say \begin{array}{*{20}c}   1 & {} & {}  \\   2 & {} & 0  \\   3 & {} & {}  \\   4 & {} & 1  \\   5 & {} & {}  \\ \end{array}

    Draw lines from 1 & 5 to 0. How many ways can you map the 2, 3, & 4?
    Last edited by Plato; January 24th 2013 at 03:02 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2012
    From
    Wisconsin
    Posts
    29
    Thanks
    1

    Re: Number of functions from one set to another

    How many ways can you map the 2, 3, & 4?
    3; 2 to 1, 3 to 1, and 4 to 1
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1784
    Awards
    1

    Re: Number of functions from one set to another

    Quote Originally Posted by nicnicman View Post
    3; 2 to 1, 3 to 1, and 4 to 1

    Now I understand your problem: you simply do not understand what this is all about

    2^3 is the correct answer.

    Your difficulty requires live sit-down help. Please see your instructor.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: August 19th 2010, 10:32 PM
  2. number of functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 16th 2010, 11:23 AM
  3. Number of functions
    Posted in the Math Topics Forum
    Replies: 8
    Last Post: October 23rd 2008, 03:42 AM
  4. Replies: 5
    Last Post: October 7th 2008, 01:55 PM
  5. Number of Functions
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 25th 2008, 12:17 PM

Search Tags


/mathhelpforum @mathhelpforum