# Number of functions from one set to another

• nicnicman
In summary, there are 2n-2 functions from the set {1, 2, . . . , n}, where n is a positive integer, to the set {0, 1} that assign 0 to both 1 and n.
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?

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

nicnicman said:

## 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?

## 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?

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.

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.

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

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}?

2n-2

## 1. What is a function?

A function is a mathematical relationship between two sets, where each element in the first set (called the domain) is paired with exactly one element in the second set (called the range). It can be thought of as a rule that assigns each input value to a unique output value.

## 2. How do you calculate the number of functions from one set to another?

The number of functions from one set (A) to another set (B) can be calculated using the formula b^a, where b is the number of elements in set B and a is the number of elements in set A. For example, if set A has 3 elements and set B has 4 elements, the number of functions from A to B would be 4^3 = 64.

## 3. What is the difference between a one-to-one function and an onto function?

A one-to-one function is a function where each element in the domain is paired with a unique element in the range, and no two elements in the domain are paired with the same element in the range. An onto function, on the other hand, is a function where every element in the range is mapped to by at least one element in the domain. In other words, every element in the range has at least one pre-image in the domain.

## 4. Can a function have a different number of elements in the domain and range?

Yes, it is possible for a function to have a different number of elements in the domain and range. For example, a function that maps the set of positive integers to the set of even numbers would have an infinite number of elements in the domain, but a finite number of elements in the range.

## 5. How do you determine if a function is injective or surjective?

A function is injective (or one-to-one) if every element in the range has at most one pre-image in the domain. This can be determined by checking if any two elements in the domain map to the same element in the range. A function is surjective (or onto) if every element in the range is mapped to by at least one element in the domain. This can be determined by checking if there are any elements in the range that do not have a pre-image in the domain.

• Calculus and Beyond Homework Help
Replies
1
Views
759
• Calculus and Beyond Homework Help
Replies
2
Views
2K
• Calculus and Beyond Homework Help
Replies
12
Views
1K
• Calculus and Beyond Homework Help
Replies
5
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
985
• Calculus and Beyond Homework Help
Replies
2
Views
595
• Calculus and Beyond Homework Help
Replies
5
Views
1K
• Calculus and Beyond Homework Help
Replies
4
Views
662
• Calculus and Beyond Homework Help
Replies
14
Views
711
• Calculus and Beyond Homework Help
Replies
3
Views
766