# Number of functions from one set to another

• January 24th 2013, 12:59 PM
nicnicman
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.
• January 24th 2013, 01:16 PM
Plato
Re: Number of functions from one set to another
Quote:

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).
• January 24th 2013, 01:40 PM
nicnicman
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.
• January 24th 2013, 01:59 PM
Plato
Re: Number of functions from one set to another
Quote:

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?
• January 24th 2013, 02:38 PM
nicnicman
Re: Number of functions from one set to another
Quote:

How many ways can you map the 2, 3, & 4?
3; 2 to 1, 3 to 1, and 4 to 1
• January 24th 2013, 02:56 PM
Plato
Re: Number of functions from one set to another
Quote:

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.