MathDB
number of functions

Source: Taiwan 3rd TST 2005, final exam, first day, problem 3

August 12, 2005
functioncombinatorics proposedcombinatorics

Problem Statement

The set {1,2,… ,n}\{1,2,\dots\>,n\} is called PP. The function f:P→{1,2,… ,m}f: P \to \{1,2,\dots\>,m\} satisfies f(A∩B)=min⁡(f(A),f(B)).f(A\cap B)=\min (f(A), f(B)). What is the relationship between the number of possible functions ff with the sum ∑j=1mjn\displaystyle \sum_{j=1}^m j^n? There is a nice and easy solution to this. Too bad I did not think of it...
Back to ProblemsView on AoPS