Check all the statements that are true: A. A surjective function from a set of n
ID: 3317938 • Letter: C
Question
Check all the statements that are true:
A. A surjective function from a set of n elements to a set of n elements is automatically injective .
B. The cardinality of a cartesian product of sets is the product of the cardinalities of the individual sets.
C. If there are 2n+1 objects in n boxes, then at least one box must contain at least 3 objects.
D. If S is a finite set, S has 2|S| subsets.
E. If n is a nonnegative integer, then the alternating sums of all the C(n,k) are 0.
F. If n and r are nonnegative integers and rnrn, then C(n,r) = P(n,r)/r!.
G. 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.
H. Combinations C(n,r) are symmetrical in r with respect to the point r=n2r=n2.
I. If n is a nonnegative integer, then the sum of all the C(n,k) is 2n2n.
J. There are n! bijections from a set with n elements to itself.
K. An injective function from a set of n elements to a set of n elements is automatically surjective.
L. There are nmnm functions from a set of n elements to a set of m elements.
M. If n and k are positive integers with nknk, then C(n+1,k) = C(n,k) + C(n,k+1).
N. 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.
O. A finite set with n members has C(n,k) subsets of size k.
Explanation / Answer
a) True
b) true
by multiplication rule of sets
c) true
using the pigeon hole principle, since there will be atleast one box that will contains the 3 objects
i) true
the sum of all the C(n,k) is 2^n
use the binomial expansion of (1+x)^n, put x = 1