MathDB

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}

26