Find number of ordered sets

Question

Let $X$ and $Y$ be subsets of $S= \{1,2,3,4,5\}$ such that for each $x\in X$, $x\gt n(Y)$ and for each $y\in Y$, $y\gt n(X)$. Then find the number of ordered subsets $(X, Y)$.

Where $n(A)$ denotes number of elements in set A.

I am getting no idea where to start from. Using brute force I am getting $121$ but the answer given is $144$.

Answer 1

Suppose $X$ has $i$ elements and $Y$ has $j$ elements. Then the $i$ elements of $X$ must be picked from the $5-j$ elements of $S$ which are greater than $j$, and the $j$ elements of $Y$ must be picked from the $5-i$ elements of $S$ which are greater than $i$. So for any pair $(i,j)$ the number of possible pairs $(X,Y)$ is $$\binom{5-j}i\binom{5-i}j$$ Summing over all relevant pairs $(i,j)$, the answer is $144$.

 1  5 10 10  5  1
 5 16 18  8  1
10 18  9  1
10  8  1
 5  1
 1