Suppose we use a simple uniform hash function h to hash n distinct keys of an array A into an array T (that is, the hash table) of size k . Answer the following questions:

Suppose A [ i ] and A [ j ] are two arbitrary elements in A. What's the probability that A [ i ] and A [ j ] are collided, that is, to hash into the same spot in T ? We say the event A i j occurs when A [ i ] and A [ j ] hash into a same spot in T. How many different events can be defined in this setting? What is the probability of event A i j occurs? If A [ i ] colliding with A [ j ] counts as one collision, what's the expected number of total collisions in this setting? Show your work.