70.0k views
3 votes
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?

User Albane
by
7.2k points

1 Answer

1 vote

Answer: a) To count the number of one-to-one functions from the set {1, 2,...,n} to the set {0, 1}, we can use the formula for the number of permutations of n distinct objects, which is n!.

However, since we are only considering one-to-one functions, we can only choose 0 or 1 for the image of each element of the domain. The first element can be assigned 2 choices, the second can be assigned 1 of the remaining 2 choices, the third can be assigned 1 of the remaining 1 choice, and so on. Therefore, the number of one-to-one functions from {1, 2,...,n} to {0, 1} is:

2 × 1 × 1 × ... × 1 = 2^(n-1)

b) To count the number of functions that assign 0 to both 1 and n, we can treat the remaining elements {2, 3,...,n-1} as a new set and count the number of functions from this set to {0, 1}. This is the same problem as in part (a), but with n-2 elements instead of n. Therefore, the number of functions from {1, 2,...,n} to {0, 1} that assign 0 to both 1 and n is:

2^(n-3)

c) To count the number of functions that assign 1 to exactly one of the positive integers less than n, we can choose which element of the domain is assigned 1 in n ways. The remaining elements can be assigned 0 or 1 independently, for a total of 2^(n-1) choices. Therefore, the number of functions from {1, 2,...,n} to {0, 1} that assign 1 to exactly one of the positive integers less than n is:

n × 2^(n-1)

Explanation:

User Serhii Kozachenko
by
7.8k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories