Let P be the set of all subsets of {1, 2, ... , n}. Show that there are 1n + 2n + ... + mn 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}, Xi = X \ {i}. Then f is completely determined by its value on X and the Xi. Its value on these sets can be any member of {1, 2, ... , m} except that we must have f(Xi) ≤ f(X). Thus there are kn possible functions with f(X) = k and hence 1n + 2n + ... + mn possible functions in all.
© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998