# Constructing 2-Universal Families

Let H be a class of all functions, mapping M possible keys to N integers. Is it true that H is a 2-universal family? Is it a good idea to use H in applications?

I don't even know where and how to start. Can you give me a hint on how to prove this? Is it even possible to prove this?

Let $$H$$ be a class of all functions which map universe $$Z_n$$ to $$Z_m$$. We will assume that, any particular mapping is done by exactly one of the functions in the class.
Total functions in $$H$$ = number of all possible mappings = $$m^n$$
Given any distinct keys $$x$$ and $$y$$, we need to find number of all possible functions (mappings) in which they collide. The remaining $$n-2$$ keys have total mappings: $$m^{n-2}$$. The $$(x,y)$$ pair can collide by mapping to any of the $$m$$ slots. So,
Total functions in $$H$$ where $$(x,y)$$ collide = $$m^{n-2}\cdot m = m^{n-1}$$
Thus probability of collision = $$m^{n-1} / m^n = 1/m$$.