Difficult question about asymptotic notations and permutations Let $ S_n$ be all the permutations on $ [n]$. For every $ \sigma \in S_n $ let $L( \sigma)$ be the length of the longest increasing sub-series of the series: $ (\sigma(1),\sigma(2),...,\sigma(n))$.
I need to prove that $$ \sum_{\sigma \in S_n} L(\sigma) = \Omega(n^{n+1}e^{-n})$$
First of all, by using Stirling it will be enough to prove that $ \sum_{\sigma \in S_n} L(\sigma) = \Omega((n!)\sqrt n)$.
I tried about comparing it to the same sum but only with permutations that kept their order until k for $ 1 \le k \le n$ but the exponent didn't go well.
I tried also to use only permutations with fixed points (as those points are an increasing sub-series) but I wasn't sure how to do that.
 A: Disclaimer: this is strongly inspired by and follows the exposition of [1], specifically Section 1.3. I strongly suggest you read this book if you are interested in the topic. 
Recall the Erdős—Szekeres theorem:

Theorem. (Erdős—Szekeres)  For any integers $r, s\geq 0$, every sequence of length at least $(r - 1)(s - 1) + 1$ contains a monotonically increasing subsequence of length $r$ or a monotonically decreasing subsequence of length $s$. 

In particular, for any $r,s\geq 1$ such that $n> rs$, any permutation $\sigma\in\mathcal{S}_n$ satisfies $L(\sigma) \geq r$ or $D(\sigma)\geq r$ (where $D(\sigma)$ is the length of the longest decreasing subsequence); or, equivalently, 
$$
\forall \sigma\in\mathcal{S}_n,\quad L(\sigma)D(\sigma) > n \tag{1}
$$
By symmetry, the distributions of $L(\sigma)$ and $D(\sigma)$ when $\sigma$ is chosen uniformly at random from $\mathcal{S}_n$ are the same, and thus $\mathbb{E}_\sigma[L(\sigma)]=\mathbb{E}_\sigma[D(\sigma)]$. Therefore, we can write
$$
\frac{1}{n!}\sum_{\sigma\in\mathcal{S}_n} L(\sigma)=\mathbb{E}_\sigma[L(\sigma)] = \frac{\mathbb{E}_\sigma[L(\sigma)]+\mathbb{E}_\sigma[D(\sigma)]}{2}
= \frac{1}{n!}\sum_{\sigma\in\mathcal{S}_n} \frac{L(\sigma)+D(\sigma)}{2}\tag{2}
$$
By the AM-GM inequality, we get
$$
\frac{1}{n!}\sum_{\sigma\in\mathcal{S}_n} \frac{L(\sigma)+D(\sigma)}{2}
\geq \frac{1}{n!}\sum_{\sigma\in\mathcal{S}_n} \sqrt{L(\sigma)D(\sigma)} \tag{3}
$$
and, combining (1), (2), and (3), we obtain that for all $n\geq 1$,
$$
\frac{1}{n!}\sum_{\sigma\in\mathcal{S}_n} L(\sigma) \geq \frac{1}{n!}\sum_{\sigma\in\mathcal{S}_n} \sqrt{L(\sigma)D(\sigma)} \geq \frac{1}{n!}\sum_{\sigma\in\mathcal{S}_n} \sqrt{n}
$$
i.e. $\frac{1}{n!}\sum_{\sigma\in\mathcal{S}_n} L(\sigma) \geq \sqrt{n}$. $~~~\square$

[1] Romik, Dan. The surprising mathematics of longest increasing subsequences. Institute of Mathematical Statistics Textbooks. Cambridge University Press, New York, 2015. xi+353 pp. ISBN: 978-1-107-42882-9; 978-1-107-07583-2 Available freely on the author's website.
