Results 1 to 9 of 9

Thread: Counting question

  1. #1
    Newbie
    Joined
    May 2015
    From
    LA
    Posts
    4

    Counting question

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

    I have been working on this problem for a bit and the answer in the back of the book is not a solution I can arrive to.
    -in the case when n=1 there are 0 functions
    -in the case when n=2 I can only see one function that is possible and that is when (1,1) and (2,0). because 2 is n it can't be assigned 1. the question then becomes does (1,0) and (2,0) count as another possibility.
    - when n=3 I get 2 functions when in the book it tells me their should be 4
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,881
    Thanks
    2891
    Awards
    1

    Re: Counting question

    Quote Originally Posted by Dbarlam View Post
    How many functions are there from the set {1,2,...,n}, where n is a positive integer, to the set {0,1}.
    c)that assigns 1 to exactly one of the positive integers less than n?
    The way this question is written, I find it hard to read. The answers from the text agree with one possible reading.
    #$\displaystyle =\begin{cases}0 &: n=1 \\ 2^{n-1} &: n\ge 2\end{cases}$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,865
    Thanks
    3074

    Re: Counting question

    It looks to me like there are n- 1 "numbers less than 1" that can be assigned to 1 then all the rest are assigned to 0. So there are n- 1 such functions.

    That is the same as your
    -in the case when n=1 there are 0 functions
    -in the case when n=2 I can only see one function that is possible and that is when (1,1) and (2,0). because 2 is n it can't be assigned 1. the question then becomes does (1,0) and (2,0) count as another possibility.
    - when n=3 I get 2 functions when in the book it tells me their should be 4
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,881
    Thanks
    2891
    Awards
    1

    Re: Counting question

    Quote Originally Posted by HallsofIvy View Post
    It looks to me like there are n- 1 "numbers less than 1" that can be assigned to 1 then all the rest are assigned to 0. So there are n- 1 such functions. That is the same as your
    How do you account for the following;
    Quote Originally Posted by Dbarlam View Post
    - when n=3 I get 2 functions when in the book it tells me their should be 4 ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2015
    From
    LA
    Posts
    4

    Re: Counting question

    So the answer in the back of the book is for all n 2(n-1) possible functions. so when n is 1 according to the equation their are zero solutions which I agree with it is just when n>1 I can't account for the extra possible functions.

    suppose n=4
    set1 set2
    1 0
    2 1
    3
    4

    I know that I have n-1 possible options (1,2,3) in this case can be assigned to 1 because 4=n and 1 can be only assigned to less than n. where I get lost is when 1 is assigned 1 the rest have to be zero, and when 2 is assigned 1 the rest have to be zero, and finally when 3 is assigned 1 the rest have to be zero. in the end I end up with 3 possible functions when the back of the book says 2(n-1).

    according to another source other than my book
    the reasoning is
    IF 1 is assigned to only one element in A, then 0 has to be assigned to all the remaining n-2 elements in the case less than n.
    whereas in the case of n , there will be n functions from A to B.
    so in total there will be (n-2)+ n =2n-2 functions
    ( I don't follow this reasoning if this is correct can someone explain this)
    Last edited by Dbarlam; May 25th 2015 at 03:53 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,881
    Thanks
    2891
    Awards
    1

    Re: Counting question

    Quote Originally Posted by Dbarlam View Post
    So the answer in the back of the book is for all n 2(n-1) possible functions. so when n is 1 according to the equation their are zero solutions which I agree with it is just when n>1 I can't account for the extra possible functions.
    suppose n=4
    set1 set2
    1 0
    2 1
    3
    4

    I know that I have n-1 possible options (1,2,3) in this case can be assigned to 1 because 4=n and 1 can be only assigned to less than n. where I get lost is when 1 is assigned 1 the rest have to be zero, and when 2 is assigned 1 the rest have to be zero, and finally when 3 is assigned 1 the rest have to be zero. in the end I end up with 3 possible functions when the back of the book says 2(n-1).
    according to another source other than my book the reasoning is
    IF 1 is assigned to only one element in A, then 0 has to be assigned to all the remaining n-2 elements in the case less than n.
    whereas in the case of n , there will be n functions from A to B.
    so in total there will be (n-2)+ n =2n-2 functions( I don't follow this reasoning if this is correct can someone explain this)
    What is A?
    Quote Originally Posted by Dbarlam View Post
    How many functions are there from the set {1,2,...,n}, where n is a positive integer, to the set {0,1}.
    c)that assigns 1 to exactly one of the positive integers less than n?
    Please post the complete question! All parts!
    As posted it makes no sense.

    Quote Originally Posted by Dbarlam View Post
    when n=3 I get 2 functions when in the book it tells me their should be 4
    That answer is consistent with my reply in #2. Not with anything else posted. Please explain why it is not correct.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2015
    From
    LA
    Posts
    4

    Re: Counting question

    A I assume is the set {1,2,...,n}

    Full Question:
    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?

    As you can see from above I believe that parts a and b is not relevant to part c. I was able to figure out part a and part b.
    The back of my textbook says that the answer is 2(n-1). when I try to solve it I get n-1 but I have no idea why it is multiplied by 2...
    since the answer in the textbook says 2(n-1). I assume since their is no qualifiers other than n is a positive integer that it works for all positive integers. so according to the book it says when n=3 for example so come up with 2(3-1)=4 possible functions which is inconsistent with my own answer. curious if this is just an error in the book or I am missing something
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,881
    Thanks
    2891
    Awards
    1

    Re: Counting question

    Quote Originally Posted by Dbarlam View Post
    A I assume is the set {1,2,...,n} Full Question:
    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?
    As you can see from above I believe that parts a and b is not relevant to part c. I was able to figure out part a and part b.
    The back of my textbook says that the answer is 2(n-1). when I try to solve it I get n-1 but I have no idea why it is multiplied by 2...
    since the answer in the textbook says 2(n-1). I assume since their is no qualifiers other than n is a positive integer that it works for all positive integers. so according to the book it says when n=3 for example so come up with 2(3-1)=4 possible functions which is inconsistent with my own answer. curious if this is just an error in the book or I am missing something
    "As you can see from above I believe that parts a and b is not relevant to part c."
    Quite to the contrary. This completely changes the question. I gave an answer thinking that the question was written by someone who used standard definitions. That is not the case with the way this question is written.

    In any standard set of notes, a function assigns each member of the initial( the domain) set to exactly one member of the finial set( the range). Even the LaTeX symbol $\displaystyle x\mapsto x^2$ is read $x$ is mapped to or assigned to $x^2$. But in this case is appears that it is other way around.

    That is to say that "c) that assign 1 to exactly one of the positive integers less than n?" written in standard mathematical jargon should read "c) exactly one of the positive integers less than n is assigned to 1?"
    Thus, there are $n-1$ ways to select the one positive integer less than $n$ to map to 1. The other $n-2$ are all mapped to 0. The number $n$ is mapped to either 0 or 1. So $2(n-1)$ is the answer.

    If $n=1$ then $2(n-1)=0$. If $n=2$ then $2(n-1)=2$. If $n=4$ then $2(n-1)=6$.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    May 2015
    From
    LA
    Posts
    4

    Re: Counting question

    Ah I see. I was under the impression that n could no be mapped to one as I read the "assign 1 to exactly one of the positive integers less than n" meant that only one integer could be mapped to one and that n was not one of them. the reason I thought that A and B was not relevant was because it wasn't a multi step problem where it built off eachother, didn't realize that it gave so much context in this case thanks again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting Question
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Feb 28th 2015, 05:09 PM
  2. Counting Question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 7th 2010, 12:20 PM
  3. counting question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 7th 2010, 02:45 PM
  4. counting question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 8th 2009, 04:30 PM
  5. Another Set Counting Question
    Posted in the Pre-Calculus Forum
    Replies: 10
    Last Post: Jan 4th 2009, 07:42 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum