3. Let the set $A=\{1,2, \cdots, n\}, X, Y$ be non-empty subsets of $A$ (allowing $X=Y$), the maximum element of $X$ and the minimum element of $Y$ are denoted as $\max X, \min Y$, respectively. Find the number of ordered pairs of sets $(X, Y)$ that satisfy $\max X>\min Y$.
First, calculate the number of ordered set pairs $(X, Y)$ that satisfy $\max X \leqslant \min Y$.
For a given $m=\max X$, the set $X$ is the union of any subset of $\{1,2, \cdots, m-1\}$ and $\{m\}$, which has $2^{m-1}$ possible choices.
Since $\min Y \geqslant m$, the set $Y$ is any non-empty subset of $\{m, m+1, \cdots, n\}$, which has $2^{n-m+1}-1$ possible choices. Therefore, the number of ordered set pairs $(X, Y)$ that satisfy $\max X \leqslant \min Y$ is $\sum_{m=1}^{n} 2^{m-1}\left(2^{n-m+1}-1\right)=\sum_{m=1}^{n} 2^{n}-\sum_{m=1}^{n} 2^{m-1}=n \cdot 2^{n}-2^{n}+1$.
Since the total number of ordered set pairs $(X, Y)$ is $\left(2^{n}-1\right)^{2}$, the number of ordered set pairs $(X, Y)$ that satisfy $\max X>\min Y$ is
$$
\left(2^{n}-1\right)^{2}-\left(n \cdot 2^{n}-2^{n}+1\right)=2^{2 n}-n \cdot 2^{n}-2^{n}=2^{2 n}-(n+1) 2^{n}
$$