How many ordered pairs (A, B) of subsets of {1, 2, ... , 10} can we find such that each element of A is larger than |B| and each element of B is larger than |A|.

**Solution**

Answer: 17711.

Evidently we are meant to solve the general case of subsets of {1, 2, ... , N}. But the choice of N = 10 is poor, because it is sufficiently small to be tractable and in an exam it is certainly safer to slog it out for the specific case, rather than to risk failing to find a more elegant solution in the limited time available. Thus if A has 0 elements, then B can be anything, so we have 1024 possibilities. If A has 1 element, then we have 10C1 9C0 + 9C1 9C1 + 8C1 9C2 + ... + 1C1 9C9 = 2816 possibilities. If A has 2 elements, then we have 10C2 8C0 + 9C2 8C1 + ... + 2C2 8C8 = 4096 possibilities and so on.

Let u_{N} be the solution for the general case. Let v_{N} be the solution with the restriction that B does not contain the element N. Let w_{N} be the solution with the restriction that B does contain the element N. We seek recurrence relations.

First observe that w_{N} = u_{N-1} because we have the correspondence (A, B) ↔ (A', B - {N}), where A' is the set derived from A by reducing each element by 1. Obviously u_{N} = v_{N} + w_{N}, so v_{N} = u_{N} - u_{N-1}.

Now consider u_{N+1}. There are four cases: (1) neither A nor B contains N+1, (2) A contains N+1, but B does not, (3) B contains N+1, but A does not, (4) both A and B contain N+1. Clearly, there are u_{N} possibilities in case (1). In case (2) we have the correspondence (A, B) ↔ (A - {N+1}, B'), where B' is derived from B by reducing each element by 1. This shows that there are v_{N} possibilities for case (2). Similarly for case (3). For case (4) we use the correspondence (A, B) ↔ (A', B') to show that there are u_{N-1} possibilities. Thus we have finally: u_{N+1} = u_{N} + 2v_{N} + u_{N-1} = 3u_{N} - u_{N-1}.

Clearly, u_{0} = 1, u_{1} = 3, so we may now use the relation to calculate successively 8, 21, 55, 144, 377, 987, 2584, 6765, 17711 (= u_{10}).

We may recognize these as alternate Fibonacci numbers and indeed a little thought shows that if a_{n+2} = a_{n+1} + a_{n} then a_{n+2} = 2a_{n} + a_{n-1} = 2a_{n} + (a_{n} - a_{n-2}) = 3a_{n} - a_{n-2}.

Alternatively, we may notice that the relations above may be rewritten as u_{N} = v_{N} + u_{N-1} and v_{N} = u_{N-1} + v_{N-1}, which (together with the starting values), shows that v_{0}, u_{0}, v_{1}, u_{1}, ... is Fibonacci.

© John Scholes

jscholes@kalva.demon.co.uk

1 Jan 2001