Number of functions from one set to another

[nicnicman]

Homework Statement

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?

Homework Equations

The Attempt at a Solution

Since every element in the domain {1, 2, . . . , n} has two options in the codomain {0, 1} there a total of 2^n functions from the domain to the codomain.
Also, I understand that to be a one-to-one relationship no element of the codomain is the image of more than one element in the domain.
However, I'm unsure how to solve the problems. Any suggestions would be appreciated.

 

[Dick]

Homework Statement

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?

Homework Equations

The Attempt at a Solution

Since every element in the domain {1, 2, . . . , n} has two options in the codomain {0, 1} there a total of 2^n functions from the domain to the codomain.
Also, I understand that to be a one-to-one relationship no element of the codomain is the image of more than one element in the domain.
However, I'm unsure how to solve the problems. Any suggestions would be appreciated.

Start with a). The answer will depend on n. Suppose n=1, n=2 and n=3. What do you get in those cases?

 

[nicnicman]

Sorry for the delay.

a) If n = 1 then there are two choices for the first and only element in the domain.
So, we have 2 functions if n = 1

If n = 2 then there are two choices for the first element in the domain. Then, since one choice is taken there is one choice for the second element in the domain.
So, we have 2 * 1 = 2 functions if n = 2.

If n >= 3 then there will always be elements in the domain with no images to map to.
So, we have 0 functions if n >= 3.

 

[dx]

I guess you know how to do part b.

Hint for part c: there are n - 1 ways to choose an element less than n, and once you assign that element to 1, all the other elements except n must go to 0. Then you can assign either 0 or 1 to n.

 

[nicnicman]

Actually I do need help with b). I don't understand what the problem is asking for.

 

[dx]

You said that the number of functions from {1, ..., n} to {0, 1} is 2ⁿ.

Part (b) is the same, except there are only n - 2 elements instead of n, since two of the elements must always go to 0.

If the function must assign 0 to both 1 and n then there are n - 2 numbers left which can be either 0 or 1.

Given n - 2 elements, how many ways are there to map them to {0, 1}?

 

[nicnicman]

2^n-2

 

[dx]

Yep, that's the answer.