Check all the statements that are true: A. There are n! bijections from a set wi
ID: 3005222 • Letter: C
Question
Check all the statements that are true:
A. There are n! bijections from a set with n elements to itself.
B. There are n^m functions from a set of n elements to a set of m elements.
C. If n is a nonnegative integer, then the sum of all the C(n,k) is 2^n.
D. If there are 2n+1 objects in n boxes, then at least one box must contain at least 3 objects.
E. If n is a nonnegative integer, then the alternating sums of all the C(n,k) are 0.
F. A finite set with n members has C(n,k) subsets of size k.
G. If a procedure can be broken down into a sequence of two tasks, and if there are n ways to do the first task, and m ways to do the second task, then there are nm ways to do the procedure.
H. If n and k are positive integers with nknk, then C(n+1,k) = C(n,k) + C(n,k+1).
I. An injective function from a set of n elements to a set of n elements is automatically surjective.
J. If S is a finite set, S has 2|S| subsets.
K. Combinations C(n,r) are symmetrical in r with respect to the point r=n/2.
L. If n and r are nonnegative integers and rnrn, then C(n,r) = P(n,r)/r!.
M. A surjective function from a set of n elements to a set of n elements is automatically injective .
N. The cardinality of a cartesian product of sets is the product of the cardinalities of the individual sets.
O. If a task can be done either in one of n ways or in one of m ways, then there are n+m ways to do the task.
Explanation / Answer
Posted the answer to the first 4 parts, post multilpe question to get the remaining answers
A) The statement A is TRUE
B) The statement is FALSE, since every element of set A with n elements can be mapped to any of the m element , hence number of possibilities will be m^n
C) The statemetn is TRUE
nC0 + nC1 + ... + nCn = 2^n
d) The statement is TRUE using the pigeon hole principle, since there will be atleast one box that will contains the 3 objects