[组合] 来自某教师群的一道集合计数

茂名赵老师(3080*****)  21:28:19
请教一题：一个集 合I有1,2,3,4,5五个元素，选择I的两个非空子集A和B，要是B中最小的数大于A中最大的数，则不同的选择方法有多少种？

“要是”应该是“要使”。

这里将求解一般情况，记 $f(n)$ 为 $I$ 中有 $n$（$n\geqslant 2$）个元素时满足题意的方法数。

显然 $f(2)=1$。当 $n\geqslant 3$ 时，

（1）若 $B$ 不包含 $I$ 中的最大元素，则方法数等于 $f(n-1)$；

（2）当 $B$ 包含 $I$ 中的最大元素时，

    （2-1）若 $B$ 中至少两个元素，则方法数也等于 $f(n-1)$；

    （2-2）若 $B$ 中只有这个最大元素，则方法数等于余下 $n-1$ 个元素构成集合的非空子集个数，即 $2^{n-1}-1$。

综上，得到 $f(n)=2f(n-1)+2^{n-1}-1$，于是求通项易得 $f(n)=(n-2)2^{n-1}+1$。

回到原题 $f(5)=49$。

递推法计数搞得炉火纯青啊

2# yes94

又夸张了……这道应该算是比较基础的一类吧……

3# kuing
那道题“$50$个数排成一圈，其中一半是奇数一半是偶数，求证必有一数，它的两边都是偶数。 ”能否递推做？
改成：“$2n$个数排成一圈，其中一半是奇数一半是偶数，求证必有一数，它的两边都是偶数。 ”其中$n$从某个合适的正整数开始。

A中最大元素为1，A有1种选择，B有2^4-1=15种选择；
A中最大元素为2，A有2种选择，B有2^3-1=7种选择；
A中最大元素为3，A有2^2=4种选择，B有2^2-1=3种选择；
A中最大元素为4，A有2^3=8种选择，B有1种选择；
结果就是1*15+2*7+4*3+8*1=49.
如果改变所给集合的元素个数，
也可以据此算出通项公式

4# yes94
n是偶数的话结论不成立。反例就是2奇数2偶数依次排成一圈。

3# kuing
那道题“$50$个数排成一圈，其中一半是奇数一半是偶数，求证必有一数，它的两边都是偶数。 ”能否递推做？
改成：“$2n$个数排成一圈，其中一半是奇数一半是偶数，求证必有一数，它的两边都是偶数。 ” ...
yes94 发表于 2013-3-27 23:35

这个我觉得没法递推，这是明显数论题，感觉和抽屉原则，或者反证法有关。

如果谁去翻一下初中奥林匹克数学竞赛书，应该能得到答案

7# isea

跟数论没啥关系吧……

A中最大元素为1，A有1种选择，B有2^4-1=15种选择；
A中最大元素为2，A有2种选择，B有2^3-1=7种选择；
A中最大元素为3，A有2^2=4种选择，B有2^2-1=3种选择；
A中最大元素为4，A有2^3=8种选择，B有1种选择；
结果就是1*15+2*7+4*3+8*1=49.
如果改变所给集合的元素个数，
也可以据此算出通项公式
地狱的死灵 发表于 2013-3-27 23:48

嗯，这个不错，照你的方法写下。
设 $I=\{1,2,\ldots,n\}$，当 $A$ 最大元素为 $k$ 时，$A$ 有 $2^{k-1}$ 种选择，$B$ 有 $2^{n-k}-1$ 种选择，所以结果为
\[\sum_{k=1}^{n-1}2^{k-1}(2^{n-k}-1)=(n-2)2^{n-1}+1.\]

顺便也把这个链接记上 http://kkkkuingggg.5d6d.net/thread-1596-1-1.html

$\sum_{k = 2}^nC_n^k( k - 1) = \sum_{k = 0}^n C_n^k(k - 1) + 1=(n-2)2^{n-1}+1$

1# kuing


（2-1）没看懂

1楼问题穷举也可以,B中最小为1,无
B中最小为2,A={1},符合的B有$2^3$个
B中最小为3.......
似乎也可以推广到n.

$\sum_{k = 2}^nC_n^k( k - 1) = \sum_{k = 0}^n C_n^k(k - 1) + 1=(n-2)2^{n-1}+1$
呆呆 发表于 2013-5-30 08:39

嗯，10#的链接就是记录了这个方法