Problem

Source: APMO 2014 Problem 2

Tags: induction



Let $S = \{1,2,\dots,2014\}$. For each non-empty subset $T \subseteq S$, one of its members is chosen as its representative. Find the number of ways to assign representatives to all non-empty subsets of $S$ so that if a subset $D \subseteq S$ is a disjoint union of non-empty subsets $A, B, C \subseteq S$, then the representative of $D$ is also the representative of one of $A$, $B$, $C$. Warut Suksompong, Thailand