Prove that the number of permutations of $\{1, ..., n\}$ containing a monotone increasing or decreasing subsequence of length at least $3\sqrt{n}$ is $o(n!)$. (Hint: pick a random permutation, and show that with probability tending to 1 it does not contain a monotone subsequence of length $3\sqrt{n}$.)
SOLUTION:
Let $k = 3\sqrt{n}$. Let $π$ be a random permutation of $\{1, ..., n\}$ and for a $k$-element subset $A ⊂ \{1, ..., n\}$, let $I(A)$ be the indicator random variable that $π$ is either monotone decreasing or increasing on $A$. Let $X = \sum_{|A| = k} I(A)$. We have $E(I(A)) = 2/k!$, so
$$ E(X) = \binom{n}{k} 2/k! \leq 2(en/k)^k(e/k)^k = 2(e^2n/k^2)^k < 2 (0.9)^k $$ But then, $P(X \geq 1) \leq E(X) < 2 (0.9)^k$, so as $n$ goes to infinity $P(X \geq 1) = 0$, which means that the number of permutations containing a monotone increasing or decreasing subsequence of length $k$ is $o(n!)$.
In the above solution, I understand everything perfectly except in the end how we decide the little-o. I see that for large $n$, a random permutation does not contain the subsequence we are looking for. However, how do we conclude that $\lim_{n \rightarrow \infty} f(n)/n! = 0$, $f(n)$ being the number of permutations with the property?