题目

设集合A={1,2,...,n}A=\{1,2,...,n\}，XX和YY均为AA的非空子集，允许X=YX=Y。XX中的最大元和YY中的最小元分别记为maxXmax X和minYmin Y。求满足maxX>minYmax X \gt min Y的有序集合对(X,Y)(X,Y)的个数。

解答

解法一:正向思路

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

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

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

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

∑k=1m−12n−k=2n⋅∑k=1m−112k=2n−2n−m+1\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 Ymax\ X\ >\ min\ Y的有序集合对(X,Y)(X,Y)的数目是:

∑m=1n2m−1(2n−2n−m+1)=2n⋅∑m=1n(2m−1−1)=2n(2n−n−1)\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 ≤ min Ymax\ X\ \le\ min\ Y的有序集合对(X,Y)(X,Y)的数目.

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

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

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

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

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

∑m=1n2m−1(2n−m+1−1)=∑m=1n2n−∑m=1n2m−1=n⋅2n−2n+1\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)(X,Y)共有(2n−1)(2n−1)=(2n−1)2(2^n-1)(2^n-1)=(2^n-1)^2种.
故满足max X > min Ymax\ X\ >\ min\ Y的有序集合对个数为:

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