# Thread: Counting question

1. ## 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

2. ## Re: Counting question

Originally Posted by Dbarlam
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}$

3. ## 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

4. ## Re: Counting question

Originally Posted by HallsofIvy
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;
Originally Posted by Dbarlam
- when n=3 I get 2 functions when in the book it tells me their should be 4 ?

5. ## 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)

6. ## Re: Counting question

Originally Posted by Dbarlam
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?
Originally Posted by Dbarlam
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.

Originally Posted by Dbarlam
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.

7. ## 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

8. ## Re: Counting question

Originally Posted by Dbarlam
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$.

9. ## 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.

### counting question book

Click on a term to search for related topics.