Problem

Source: Moldova TST Problem 4, day 3

Tags: function, combinatorics



Let $n$ and $k$ be positive integers, and let be the sets $X=\{1,2,3,...,n\}$ and $Y=\{1,2,3,...,k\}$. Let $P$ be the set of all the subsets of the set $X$. Find the number of functions $ f: P \to Y$ that satisfy $f(A \cap B)=\min(f(A),f(B))$ for all $A,B \in P$.