Nielsen & Chuang Exercise 3.15: Lower bound for compare-and-swap based sorts
$\Omega(\cdot)$ means “at least that many steps” _up to a multiplicative constant. There's a gap between $n!$ and $n^n$, and that gap is more than a multiplicative constant. But we aren't looking for an asymptotic bound on the number of length of the list that can be sorted in $k$ steps, but on the minimum number of steps $S(n)$ that it takes to sort a list of length $n$ in the worst case.
You've seen that after $k$ steps, it's only possible to distinguish between $2^k$ different orderings of the list. You've also seen that the total number of orderings of the list is $n!$. The number of steps must be sufficient to distinguish between all orderings, therefore $2^{S(n)} \ge n!$. This condition can equivalently be stated $S(n) \ge \lg(n!)$ where $\lg$ is the logarithm in base $2$.
You want to prove $S(n) \in \Omega(n \lg n)$. (Or maybe $\Omega(n \log n)$ for some different logarithm base, but logarithm bases are equivalent up to a multiplicative constant.) You know that $S(n) \ge \lg(n!)$. Therefore it is sufficient to prove that there is a multiplicative constant $C$ such that for large enough $n$, $\lg(n!) \ge C n \lg n$. Note that this is equivalent to $n! \ge 2^{C n \lg n}$, i.e. $n! \ge n^{C n}$, and the family of functions $n \mapsto n^{C n}$ is not the same as the family of functions $n \mapsto C n^n$.
Stirling's formula, obtained via calculus, can give you a precise approximation of $n!$ from which you can prove the desired asymptotic equality. But here we only need a weak version of it that can be proved more easily. For $n \ge 4$:
$$ \begin{align}
\lg(n!) &amp;= \lg(1) + \lg(2) + \ldots + \lg(n) \\
&amp;\ge \lg \lceil n/2 \rceil + \ldots + \lg(n) &amp;&amp; \text{(only sum the larger half of the terms)} \\
&amp;\ge (n/2 - 1) \lg(n/2) &amp;&amp; \text{(all terms are larger than the smaller term; count them and round down)} \\
&amp;\ge \left(\frac{1}{2} - \frac{1}{n}\right) \dfrac{\lg(n) - 1}{\lg(n)} \; n \lg(n) &amp;&amp; \text{(algebra)} \\
&amp;\ge \frac{1}{8} n \lg(n) &amp;&amp; \text{(approximate the complicated factor by a constant)} \\
\end{align} $$
For large enough $n$, $\lg(n!)$ is larger than $n \lg(n)$ multiplied by the constant $1/8$. This fits the definition of $\lg(n!) \in \Omega(n \lg(n))$.