每日一题[430]给我一个合理的解释

这是我在QQ群中国数学解题研究会中看到的问题：

设集合$I=\{1,2,3,4,5\}$，选择$I$的两个非空子集$A,B$，要使$B$中最小的数大于$A$中最大的数，则不同的选择方法共有_______种．

---

解    考虑$A$中最大的数为$k$，那么$A$可以是$1,2,3,4,5$中比$k$小的数构成的集合的子集与$\{k\}$的并集，而$B$可以是$1,2,3,4,5$中比$k$大的数构成的集合的非空子集，因此不同的选择方法数按$k$分为$4$类，总数为

$$2^0(2^4-1)+2^1(2^3-1)+2^2(2^2-1)+2^3(2^1-1)=15+14+12+8=49.$$

一般的，对$n$元集合，有

$$2^0(2^{n-1}-1)+2^1(2^{n-2}-1)+\cdots+2^{n-2}\cdot (2^1-1)=(n-2)2^{n-1}+1$$ 个不同的选择方法．

如下，可以给通项一个解释．

先从$\{1,2,3,\cdots,n\}$中随意选择一个数$k$放入集合$A$中，然后用剩下的$n-1$个数挑出若干数，其中比$k$大的放在集合$B$中，比$k$小的放在集合$A$中，共有$n\cdot 2^{n-1}$种方法．但是此时会有集合$B$为空集的情形，其个数分别为集合$\{1,2,3,\cdots,n\}$的子集中最大元素为$k$的子集数，于是需要排除$2^n-1$种方法，总数为

$$n\cdot 2^{n-1}-(2^n-1)=(n-2)\cdot 2^{n-1}+1.$$