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