There is also the following combinatorial proof.
Let $S_n$ be a set of permutations of $n$ elements and $T_n$ be a set of sequences of length $a_1, a_2, \ldots, a_n$ with $1 \le a_i \le n$.
We will construct a surjective mapping from $S_n \times S_n$ to $T_n$. This will imply that $|S_n \times S_n| \ge |T_n|$ which is what we want. For $n \ge 3$ at least one element will also have more that one pre-image.
Consider a pair of two permutations $(\pi_1, \pi_2) \in S_n \times S_n$. Consider a cycle ($c_1 c_2 \ldots c_k$) of $\pi_1$ where $c_1$ is the smallest element of the cycle (that is $c_1 < c_i$). For each such cycle we set $a_{c_i}$ equal to $c_1$-th elements of $\pi_2$ (which we treat as a sequence). That way we produce a sequence {${a_k}$}.
For example, let $\pi_1 = (1) (2 5) (3 6) (4)$ and $\pi_2 = [3, 1, 2, 4, 5, 6]$. Note that we write $\pi_1$ in cycle notation while we treat $\pi_2$ as a sequence. Then $a = [3, 1, 2, 4, 1, 2]$. Note that $\pi_1$ has $4$ cycles hence $a$ has four sets of equal elements. The value for each set of equal elements is determined by $\pi_2$. Also note that last two elements of $\pi_2$ in our example are "ignored" during the construction of the sequence. That is $\pi_1 = (1) (2 5) (3 6) (4)$ and $\pi_2 = [3, 1, 2, 4, 6, 5]$ also maps to the same sequence.
Now it is quite easy to prove that every sequence $a_1, \ldots, a_n$ has at least one pre-image. The $\pi_1$ permutation consists of cycles of equal elements in $a$ and $\pi_2$ determines values of these sets of equal elements.
Also for $n \ge 3$ the sequence $1, 1, \ldots, 1$ has at least two pre-images: $\pi_1 = (1 2 \ldots n)$ and $\pi_2$ equal to any permutations which starts with $1$.