Number of Ordered Pairs (A,B) Following a Set of Conditions How many ordered pairs $(A,B)$ of subsets of $\{1,2,...,20\}$ can we find such that each element of $A$ is larger than $|B|$ and each element of $B$ is larger than $|A|$?
Is there a way to do this without excessive casework?
 A: This is problem $A6$ of the $1990$ putnam. Here is a solution:
First of all the answer is $F_{42}=267,914,296$.
Proof: Let $a_{n,m}$ be the number of good pairs $A,B$ of subsets with $A\subseteq[n],B\subseteq [m]$. We have $a_{m,n}=a_{m-1,n}+a_{m-1,n-1}$.
Because there are clearly $a_{m-1,n}$ pairs where $A$ does not contain $m$.
In how many pairs does $A$ contain $m$? suppose $A,B$ is a pair containing $m$, then think of the pair $A',B'$ obtained by deleting $n$ from $A$ and shifting every element of $B$ down.
From here we have $0,1,a_{0,0},a_{1,0},a_{1,1},a_{2,1},\dots$ is the Fibonacci sequence.
A: So for $h=\lvert A\rvert, k=\lvert B\rvert$ we are looking for ways to choose $h$ elements from $\{k+1,...20\}$ and $k$ elements from $\{h+1,...20\}$ .   Which is to say:
$$\nu(h, k) = \binom{20-h}{k}\binom{20-k}{h}$$
So the answer is $$\sum_{h,k}\nu(h,k) ~=~ \sum_{k=0}^{20}\sum_{h=0}^{20-k}\binom{20-h}{k}\binom{20-k}{h}~=~267914296$$
A: Define $|A|=a, |B|=b$ and we can assume $a \le b$, then double the cases where $a \neq b$.  Start by picking middling $a,b$ and do it by hand to get some intuition.  If $a=4,b=8$, for example, we have to choose the elements of $A$ from the range $9$ to $20$, so there are ${12 \choose 4}$ choices.  Similarly for $B$ there are $16 \choose 8$ choices.  We can separate the terms where $a=b$ from those where $a \neq b$ and get $$\sum_{i=0}^{10} {20-i \choose i}^2+2\sum_{i=0}^{9}\sum_{j=i+1}^{20-i}{20-i \choose j}{20-j \choose i}$$
