题目

设集合$A={1,2,…,n}$,$X$和$Y$均为$A$的非空子集,允许$X=Y$。$X$中的最大元和$Y$中的最小元分别记为$max X$和$min Y$。求满足$max X \gt min Y$的有序集合对$(X,Y)$的个数。

解答

解法一:正向思路

对于给定的$max\ X\ =\ m$,集合$X$是集合${1,2,···,m-1}$的任意一个子集与${m}$的并.

故共有$2^{m-1}$种取法.

对于满足要求的$min\ Y\ =\ k,k\ \in {1,2,···,m-1}$,集合$Y$是集合${k+1,k+2,···,n}$的任意子集与${k}$的并.

故对于每个可能的$k$的取值,共有$2^{n-k}$种$Y$的取法.
因此,对于给定的$m$,其$Y$的数目是:

$$\begin{aligned}
&\sum_{k=1}^{m-1}2^{n-k}\
=&2^n·\sum_{k=1}^{m-1}\frac{1}{2^k}\
=&2^n-2^{n-m+1}
\end{aligned}$$

因此,满足$max\ X\ >\ min\ Y$的有序集合对$(X,Y)$的数目是:

$$\begin{aligned}
&\sum_{m=1}^{n}{2^{m-1}(2^n-2^{n-m+1})}\
=&2^n·\sum_{m=1}^{n}(2^{m-1}-1)\
=&2^n(2^n-n-1)
\end{aligned}$$

解法二:逆向思路

先计算$max\ X\ \le\ min\ Y$的有序集合对$(X,Y)$的数目.

对于给定的$max\ X\ =\ m$,集合$X$是集合${1,2,···,m-1}$的任意一个子集与${m}$的并.

故共有$2^{m-1}$种取法.

又由$min\ Y\ \geq\ m$,故$Y$是${m,m+1,···,n}$的一个任意非空子集.

共有$2^{n-m+1}-1$种取法.

因此,满足$max\ X\ \le\ min\ Y$的有序集合对$(X,Y)$的数目是:

$$\begin{aligned}
&\sum_{m=1}^{n}{2^{m-1}(2^{n-m+1}-1)}\
=&\sum_{m=1}^{n}2^n-\sum_{m=1}^{n}2^{m-1}\
=&n·2^n-2^n+1
\end{aligned}$$

由于有序集合对$(X,Y)$共有$(2^n-1)(2^n-1)=(2^n-1)^2$种.
故满足$max\ X\ >\ min\ Y$的有序集合对个数为:

$$\begin{aligned}
&(2^n-1)^2-n·2^n+2^n-1\
=&2^n(2^n-n-1)
\end{aligned}$$