Results 1 to 11 of 11

Math Help - help me with counting of function

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    129

    help me with counting of function

    How many functions are there from the set {1,2,...,n}, where n is a positive integer, to the set {0,1}
    a) that assign 0 to both 1 and n?
    b) that assign 1 to exactly one of the positive integers less than n?
    Answer to a) is n? and b) is n-1?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by zpwnchen View Post
    Answer to a) is n? and b) is n-1?
    In the first one, you have a sequence \{a_k\}_{k=1}^{n} such that a_i \in \{0,1\} \ \forall 1 \leq i \leq n and such that a_1=a_n = 0. So you have n-2 more spots to fill in the sequence, where each of them can be either 0 or 1, ie. 2 options for each spot, n-2 spots, gives 2^{n-2}.

    b is correct, though.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1
    How many functions are there from the set {1,2,...,n}, where n is a positive integer, to the set {0,1}
    a) that assign 0 to both 1 and n?
    b) that assign 1 to exactly one of the positive integers less than n?
    a) There are no functions that assign 0 to both 1 and n.
    No function can have two pairs with the same first term: (0,1)~\&~(0,n).

    b) Notice that the range is \{0,1\}
    If n=1 the answer is 0
    If n>1 the answer is 2^{n-1}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Plato View Post
    a) There are no functions that assign 0 to both 1 and n.
    No function can have two pairs with the same first term: (0,1)~\&~(0,n).

    b) Notice that the range is \{0,1\}
    If n=1 the answer is 0
    If n>1 the answer is 2^{n-1}
    Since f:\{1,2,...,n\} \to \{0,1\}, I think what we are to assume is that f(1) = f(n) = 0, which is of course possible, we just lose f being injective.

    As for b, let f(m) = 1 for some 1\leq m < n. Then, f has assign 0 to every other element of \{1,...,n\}, therefore there is only one such sequence, and there are n-1 choices of m.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1
    Quote Originally Posted by Defunkt View Post
    Since f:\{1,2,...,n\} \to \{0,1\}, I think what we are to assume is that f(1) = f(n) = 0, which is of course possible, we just lose f being injective.
    The wording is misleading. A function assigns 0 to 1 & n if the pairs (0,1) and (0,n) are in the function.
    That is the reason for my comment.
    So the statement of the question is incorrect.

    As for your objection about the b) part, do you know that 0 is not a positive integer?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Plato View Post
    The wording is misleading. A function assigns 0 to 1 & n if the pairs (0,1) and (0,n) are in the function.
    That is the reason for my comment.
    So the statement of the question is incorrect.

    As for your objection about the b) part, do you know that 0 is not a positive integer?
    Of course I know that! But I solved it using the same "definition" as part (a). That is, f(m) = 1 for some 1\leq m < n. It can't be that f(0) = 1 since 0 is not in the domain of f!

    I agree that the wording is ambiguous/incorrect... however this way it makes much more sense, more so because 0 is not in the domain.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1
    Quote Originally Posted by Defunkt View Post
    Of course I know that! But I solved it using the same "definition" as part (a). That is, f(m) = 1 for some 1\leq m < n. It can't be that f(0) = 1 since 0 is not in the domain of f!

    I agree that the wording is ambiguous/incorrect... however this way it makes much more sense, more so because 0 is not in the domain.
    I think that we must answer the question as asked.
    If the statement says: f assigns 2 to 3 then that means f(2)=3.
    Otherwise, we have no common language for communication at this site.
    If we try to second guess what is actually meant, that will lead to a huge waste of time.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Plato View Post
    I think that we must answer the question as asked.
    If the statement says: f assigns 2 to 3 then that means f(2)=3.
    Otherwise, we have no common language for communication at this site.
    If we try to second guess what is actually meant, that will lead to a huge waste of time.
    I agree that a common terminology for communication is needed, however there are always exceptions... In my opinion, it is fairly obvious, (I really don't see any teacher giving such a question, in the way that you meant it) in this context, that f assigns 0 to both n and 1 means f(1)=f(n)=0.

    Yes, I agree that on a usual context it would not be correct to state it this way, however I see no point at all in asking this question if 0 is not even in the domain of f.

    I guess we should just wait for zpwnchen to clarify the question.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Sep 2009
    Posts
    129
    I checked the question word by word from the textbook and it was correct as it was.
    How many functions are there from the set {1,2,....,n}, where n is a positive integer, to the set {0,1}
    a) that assign 0 to both 1 and n?
    b) that assign 1 to exactly one of the positive integers less than n?
    The solution manual said...
    a) is 2^{n-2} if n>1; 1 if n=1;
    b) is 2(n-1)

    But no idea of b answer...
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1
    Quote Originally Posted by zpwnchen View Post
    I checked the question word by word from the textbook and it was correct as it was.
    How many functions are there from the set {1,2,....,n}, where n is a positive integer, to the set {0,1}
    a) that assign 0 to both 1 and n?
    b) that assign 1 to exactly one of the positive integers less than n?

    The solution manual said...
    a) is 2^{n-2} if n>1; 1 if n=1;
    b) is 2(n-1)
    My first question must be “Is the textbook written in English?”
    If not then I have no basis for my objections.
    But if it is written in English, then the author is abusing standard mathematical usage.
    It should read:
    a) assign or map both 1 and n to 0.
    b) assigns or maps exactly one of the positive integer less than n to 1.

    In standard mathematical usage saying F assigns x to y means F(x)=y.

    To answer the question correctly stated,
    “How many functions \{1,2,\cdots,n\}\mapsto \{0,1\} assign exactly one of the positive integer less than n to 1”?
    Answer
    If n=1 there are none.
    If n>1, we can chose n-1 integers to map to 1.
    The other n-2 must map to 0 while n itself may be assigned to either 0\text{ or }1.
    Therefore the answer is 2(n-1).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Sep 2009
    Posts
    129
    It was written in English and here is the text book.


    Thank you very much for the help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Riemann's Prime Counting Function
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: July 7th 2010, 11:51 AM
  2. Prime-counting function
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: October 25th 2009, 01:10 AM
  3. Riemann's prime counting function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 8th 2009, 05:31 PM
  4. Inequality with the prime-counting function
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 17th 2008, 12:07 PM
  5. Prime counting function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 11th 2006, 03:29 PM

Search Tags


/mathhelpforum @mathhelpforum