设集合 $A=\{1,2,\cdots,n\}$，$X,Y$ 均为 $A$ 的非空子集（允许 $X=Y$）．$X$ 中的最大元与 $Y$ 中的最小元分别记为 $\max X,\min Y$．求满足 $\max X>\min Y$ 的有序集合对 $(X,Y)$ 的数目．
【难度】
【出处】
2018年全国高中数学联赛（B卷加试试题）
【标注】
【答案】
略
【解析】
先计算满足 $\max X\leqslant \min Y$ 的有序集合对 $(X,Y)$ 的数目．对给定的 $m=\max X$，集合 $X$ 是集合 $\{1,2,\cdots,m-1\}$ 的任意一个子集与 $\{m\}$ 的并，故并有 $2^{m-1}$ 种取法．又 $\min Y\geqslant M$，故 $Y$ 是 $\{m,m+1,\cdots,n\}$ 的任意一个非空子集，共有 $2^{n+1-m}-1$ 种取法．因此，满足 $\max X\leqslant \min Y$ 的有序集合对 $(X,Y)$ 的数目是
$\displaystyle \sum\limits_{m=1}^n2^{m-1}(2^{n+1-m}-1)=\sum\limits_{m=1}^n2^n-\sum\limits_{m=1}^n2^{m-1}=n\cdot 2^n-2^n+1$．由于有序集合对 $(X,Y)$ 有 $(2^n-1)\cdot (2^n-1)=(2^n-1)^2$ 个，于是满足 $\max X>\min Y$ 的有序集合对 $(X,Y)$ 的数目是 $(2^n-1)^2-n\cdot 2^n+2^n-1=2^{2n}-2^n(n+1)$．
$\displaystyle \sum\limits_{m=1}^n2^{m-1}(2^{n+1-m}-1)=\sum\limits_{m=1}^n2^n-\sum\limits_{m=1}^n2^{m-1}=n\cdot 2^n-2^n+1$．由于有序集合对 $(X,Y)$ 有 $(2^n-1)\cdot (2^n-1)=(2^n-1)^2$ 个，于是满足 $\max X>\min Y$ 的有序集合对 $(X,Y)$ 的数目是 $(2^n-1)^2-n\cdot 2^n+2^n-1=2^{2n}-2^n(n+1)$．
答案
解析
备注
