Hashing functions:

Let A be a set with r elements, let B be the set {1, 2, 3, ..., 200000}, and assume that we have a randomly generated hashing function h: A -> B. In other words, we are aiming to find the probability that there exist x, y e A such that x * y and h(x) = h(y). The problem is divided into the following subproblems. (a) Let r be a positive integer. Determine a formula for the number of ways to create a sequence (an ordered list) of r numbers from B = {1, 2, 3, ..., 200000 } when repetitions are allowed. (b) Let r be a positive integer. Determine a formula for the number of ways to create a sequence (an ordered list) of r numbers from B = {1, 2, 3, ..., 200000 } when repetitions are not allowed. (c) Let r be a positive integer. Determine a formula for the probability, p(r), that h yields a collision. Hint: Calculate first the complement of this event using (a) and (b) above!]