Let P be the set of all subsets of {1, 2, ... , n}. Show that there are 1^{n} + 2^{n} + ... + m^{n} functions f **:** P → {1, 2, ... , m} such that f(A ∩ B) = min( f(A), f(B) ) for all A, B.

**Solution**

*Easy.*

Let X = {1, 2, ... , n}, X_{i} = X \ {i}. Then f is completely determined by its value on X and the X_{i}. Its value on these sets can be any member of {1, 2, ... , m} except that we must have f(X_{i}) ≤ f(X). Thus there are k^{n} possible functions with f(X) = k and hence 1^{n} + 2^{n} + ... + m^{n} possible functions in all.

© John Scholes

jscholes@kalva.demon.co.uk

12 Dec 1998