Let $A$ be the set of binary functions $f : \{0,1\}^n \to \{0,1\}^n$ such that
$A = \{f|f(m_1) = f(m_2)\}$
for some input $m_1, m_2 \in \{0,1\}^n.$ Further let $FUNC_n$ be the set of all binary functions over $n$ bit.
$FUNC_n := \{f | f : \{0,1\}^n \to \{0,1\}^n\}$
Then $|FUNC_n| = 2^{n\cdot2^n}$
I want to prove that $\frac{|A|}{|FUNC_n|}$ is neglectable. My suggestion was that $|A| = (2^n-1)!$, i.e. from the 2^n possible inputs I lock one and let the other be arranged "at random".
Since $|FUNC_n| = 2^{n\cdot2^n}$ I thought I can assume that $\lim_{n\to\infty}\frac{(2^n-1)!}{2^{n\cdot2^n}}=0$.
But is that correct? For $x!$ it is obvious that it grows slower than $n^n$, but does $2^n!$ also grow slower than $n^n$ (or $2^{n\cdot2^n}$)?
Thank you for any reply or input on how to prove this!
It appears that $\left(2^n\right)!$ does grow slower than $2^{n2^n}$:
$$\begin{align*} \ln\frac{\left(2^n\right)!}{2^{n2^n}}&=\sum_{k=1}^{2^n}\ln k-n2^n\ln 2\\ &<\int_1^{2^n+1}\ln x\,dx-n2^n\ln 2\\ &=[x\ln x-x]_1^{2^n+1}-n2^n\ln 2\\ &=\left(2^n+1\right)\ln\left(2^n+1\right)-2^n-n2^n\ln 2\\ &<\left(2^n+1\right)\ln\left(2^n+2^n\right)-2^n-n2^n\ln 2\\ &=(n+1)\left(2^n+1\right)\ln 2-2^n-n2^n\ln 2\\ &=\left(2^n+n+1\right)\ln 2-2^n\\ &=(n+1)\ln 2-(1-\ln 2)2^n\;, \end{align*}$$
so
$$\frac{\left(2^n\right)!}{2^{n2^n}}<\frac{2^{n+1}}{\frac{e}2+e^{2^n}}<\frac{2^{n+1}}{2^{2^n}}\underset{n\to\infty}\longrightarrow 0\;.$$