IMO 1974 LL POL26

Let g(k) be the number of partitions of a k-element set M, i.e.,

imolonglistmathematicsolympiad

IMO 1974 LL POL26

Origin: POL

Problem

Let g(k) be the number of partitions of a k-element set M, i.e., the number of families {A1, A2, . . . , As} of nonempty subsets of M such that Ai \capAj = \emptysetfor i ̸= j and %n i=1 Ai = M. Prove that nn \leqg(2n) \leq(2n)2n for every n.