Consider the two sequences $$a(n)=\sum_{k=1}^n\binom{n}k\sum_{j=1}^{k/2}\binom{k}{2j}\frac{(2j)!}{j!}$$ and $$b(n)=\sum_{k=0}^n\binom{n}k^2k!$$
QUESTION. Is this true? $$\frac{a(n)}{b(n)}\longrightarrow 0 \qquad \text{as} \qquad n\rightarrow\infty.$$
It is very much true. We may simplify the first sum by changing the order of summation: $$\sum_k \binom{n}k\binom{k}{2j}=\sum_k\binom{n}{2j}\binom{n-2j}{k-2j}=2^{n-2j}\binom{n}{2j}.$$
Now the summand for $a(n)$ is $$2^{n-2j}\binom{n}{2j}\frac{(2j)!}{j!}=2^{n-2j}\frac{n!}{(n-2j)!j!}.$$ The denominator is not less than, say, $(n/3)!$, so the fraction is less than $n!/100^n$ for large $n$, and even if we sum up $n$ such fractions we get much less than $n!<b(n)$.
