My goal is to find a lower bound for \begin{equation}\sum_{0\leq l\leq k\leq n}S(n,k)S(k,l)\end{equation}, where $S(n,k)$ denotes the Stirling numbers of the second kind. I first tried to use the maximum for the stirling number $S(n,k)$ which happens at $k=n/\log(n)$ but this decreases $k$ to much, and the second factor in the product gets pretty small, thus I tried $\sum_{0\leq l\leq k\leq n}S(n,k)S(k,l) \geq S(n,n/2)S(n/2,n/4)$. It turned out that an estimate for $\log(S(n,n/2))$ is given by \begin{equation}(n/2 +1)\log(n/2) - n/2\log(2) + 3/n \end{equation}
Therefore I get the following inequality: \begin{equation} \sum_{0\leq l\leq k\leq n}S(n,k)S(k,l)\geq e^{3n/4\log(n)- 3n/4\log(2) + 15/n} \end{equation} However I also now that $\sum_{k=0}^nS(n,k)=B_n$ ($B_n$= Bell number) grows as $e^{n\log(n)- n\log(\log(n))-n}$ and thus the leading order is $e^{n\log(n)}$ Shouldn't my sum grow faster? Was my attempt wrong, or what could be a better one?
Thanks a lot for any Inputs!
If we break this up as a double sum, we get $$\sum_{k=0}^n S(n,k) \sum_{\ell=0}^k S(k,\ell) = \sum_{k=0}^n S(n,k) B_k$$ The values of this sum as $n$ varies are sequence A000258 in the OEIS.
In the OEIS, we see the exponential generating function $\exp(\exp(\exp(x)-1)-1)$ which I'm sure follows from the exponential formula. This lets us hope to get asymptotics for the sequence by looking at the e.g.f., for example by Hayman's method: see Theorem 5.4.1 in Wilf's generatingfunctionology.
(I tried working on this for a bit. It's straightforward but painful, so I suggest looking through the references in the OEIS to see if anyone else has done it, first.)