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.$$



Decaying of a certain ratio of binomial sums
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)$.


