ASSIGNMENT-4
CS 2214B: DISCRETE STRUCTURES FOR COMPUTING
Instructions: Please submit a single pdf file to gradescope. Each question is worth 25
points.
1. Let X be a finite set of cardinality n and 0 ≤ r ≤ n. Provide a bijection between
the sets A and B defined below. Prove that the function you provide is in fact a
bijection.
A = Set of all subsets of X of size r.
B = Set of all strings of length n with exactly r 1’s.
For example, when X = {a1, a2, a3} and r = 2, we have A = {{a1, a2}, {a1, a3}, {a2, a3}}
and B = {110, 101, 011}.
Hint: Give an inverse for your function instead of proving that it is 1 − 1 or onto.
2. Consider a square having sides of length 2 and let p1, . . . p5 be five distinct points in
the interior of the square. Prove that there are at least two distinct points pi and pj
such that the distance between them is at most √
2. Hint: What are the pigeons and
what are the holes?
3. Find the number of strings of length 7 with at most three 0’s.
4. Find the coefficient of x
94 in (x +
1
x2 )
100
.
1
