(a) Show that
$$\underline{M}(n) \geqslant \frac{n^{2}}{2^{n-1}} \binom{n-1}{\left\lfloor \frac{n}{2} \right\rfloor}.$$
(b) Show next, using Stirling's formula recalled in the preamble, that this lower bound is equivalent to $C n^{\alpha}$ as $n$ tends to infinity, for constants $C$ and $\alpha > 0$ that one will make explicit. Compare with the upper bound for $\underline{M}(n)$ obtained in question 6 of Part II.