ILL 1974 Problem 26

Let $g(k)$ be the number of partitions of a $k$ -element set $M$ , i.e., the number of families $\{ A_1,A_2,\ldots ,A_s\}$ of nonempty subsets of $M$ such that $A_i\cap A_j=\emptyset$ for $i\not= j$ and $\bigcup_{i=1}^n A_i=M$ . Prove that, for every $n$ , $$n^n\le g(2n)\le (2n)^{2n}$$