Which function grows at a faster rate? $n!$ or $2^{n^2}$ I have two functions:
$n!$
$2^{n^{2}}$
What is the difference between the growth of these two? My thought is that $2^{n^2}$ grows much faster than $n!$. 
 A: HINT:
$$\log 2^{n^2}=n^2\log 2$$
and 
$$\log n!<n\log n$$
A: Create a  sequence $\{a_n\} = \frac{2^{n^2}}{n!}$  and let $n$ get infinitely large. Upon using the ratio test:
$$
\frac {a_{n}}{ a_{n-1}}=\frac{2^{n^2}/n!}{2^{(n-1)^2}/(n-1)!}=\frac{2^{n^2}}{n2^{(n-1)^2}}=\frac{2^{2n-1}}{n}.
$$
What can one say about this?
A: There's a nice combinatorial relationship between the two: $n!$ is the number of $n\times n$ permutation matrices, and $2^{n^2}$ is the number of $n\times n$ binary matrices. Every permutation matrix is a binary matrix, so we immediately have $2^{n^2}\geq n!$.
Moreover, the probability that a random binary matrix is a permutation matrix is intuitively very small. Concretely, for each permutation matrix, we can form $2^{(n^2-n)/2}$ unique binary matrices by filling in the remaining spots to the right of the given 1s. So $2^{n^2}\geq n!2^{(n^2-n)/2}$.
A: We know $2^{n}$ grows much faster than $n$, so
$$2^{n^2}>2^{1+2+\cdots+n}$$
grows much faster than
$$n!=1\cdot 2\cdots n.$$
A: $$\frac{2^{n^2}}{n!}=\frac{2^n}1\cdot\frac{2^n}2\cdot\frac{2^n}3\cdot\cdots\cdot\frac{2^n}n\rightarrow\infty$$
