# Math Help - Number of functions from one set to another

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.

2. ## Re: Number of functions from one set to another

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

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

4. ## Re: Number of functions from one set to another

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

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

6. ## Re: Number of functions from one set to another

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