Q26 Matemática  (IMO Longlists 1974)

Seja $g(k)$ o número de partições de um $k$-conjunto de elementos $M$, ou seja, o número de famílias $\{A_1,A_2,\dots ,A_s\}$ de subconjuntos não vazios de $M$ tal que $A_i\cap A_j=\varnothing$ para $i\ne j$ e ${\bigcup }_{i=1}^n{A}_i=M$. Prove que, para cada $n$, $$n^n\le g(2n)\le (2n{)}^{2n}$$