Three. (This question is worth $\mathbf{50}$ points) 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$.
Solution: First, calculate the number of ordered pairs of sets $(X, Y)$ that satisfy $\max X \leq \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\}$, hence there are $2^{m-1}$ ways to choose $X$. Since $\min Y \geq m$, $Y$ is any non-empty subset of $\{m, m+1, \cdots, n\}$, giving a total of $2^{n+1-m}-1$ ways to choose $Y$.
20 points
Therefore, the number of ordered pairs of sets $(X, Y)$ that satisfy $\max X \leq \min Y$ is
$$
\sum_{m=1}^{n} 2^{m-1}\left(2^{n+1-m}-1\right)=\sum_{m=1}^{n} 2^{n}-\sum_{m=1}^{n} 2^{m-1}=n \cdot 2^{n}-2^{n}+1 .
$$
................... 40 points
Since the number of ordered pairs of sets $(X, Y)$ is $\left(2^{n}-1\right) \cdot\left(2^{n}-1\right)=\left(2^{n}-1\right)^{2}$, the number of ordered pairs of sets $(X, Y)$ that satisfy $\max X>\min Y$ is
$$
\left(2^{n}-1\right)^{2}-n \cdot 2^{n}+2^{n}-1=2^{2 n}-2^{n}(n+1) \text {. }
$$