Number of functions from one set to another

  • Thread starter nicnicman
  • Start date
  • #1
136
0

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.
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,263
619

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?
 
  • #3
136
0
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.
 
  • #4
dx
Homework Helper
Gold Member
2,112
40
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.
 
  • #5
136
0
Actually I do need help with b). I don't understand what the problem is asking for.
 
  • #6
dx
Homework Helper
Gold Member
2,112
40
You said that the number of functions from {1, ..., n} to {0, 1} is 2n.

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}?
 
  • #8
dx
Homework Helper
Gold Member
2,112
40
Yep, that's the answer.
 

Related Threads on Number of functions from one set to another

Replies
1
Views
3K
Replies
2
Views
335
  • Last Post
Replies
10
Views
4K
Replies
17
Views
649
Replies
4
Views
1K
Replies
6
Views
2K
Replies
0
Views
935
Replies
8
Views
1K
Replies
3
Views
4K
Top