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: