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.

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 $\displaystyle 2^n$ functions $\displaystyle \{1, 2, \cdots , n\}\to\{0,1\}$.

b) The answer is $\displaystyle 1$ if $\displaystyle n=1$, or $\displaystyle 2^{n-2}$ if $\displaystyle n\ge 2.$.

Now, you reply with an explication. If you do we can help with c).

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.

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 $\displaystyle \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?

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

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**

$\displaystyle 2^3$ is the correct answer.

Your difficulty requires live sit-down help. **Please see your instructor.**