集合的子集问题由n个不同元素组成的集合,现在分成x个子集(子集不能为空),求有多少种分法下图为4个元素的1到4个子集的分法结构图
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/03 02:11:55
![集合的子集问题由n个不同元素组成的集合,现在分成x个子集(子集不能为空),求有多少种分法下图为4个元素的1到4个子集的分法结构图](/uploads/image/z/8562533-5-3.jpg?t=%E9%9B%86%E5%90%88%E7%9A%84%E5%AD%90%E9%9B%86%E9%97%AE%E9%A2%98%E7%94%B1n%E4%B8%AA%E4%B8%8D%E5%90%8C%E5%85%83%E7%B4%A0%E7%BB%84%E6%88%90%E7%9A%84%E9%9B%86%E5%90%88%2C%E7%8E%B0%E5%9C%A8%E5%88%86%E6%88%90x%E4%B8%AA%E5%AD%90%E9%9B%86%28%E5%AD%90%E9%9B%86%E4%B8%8D%E8%83%BD%E4%B8%BA%E7%A9%BA%29%2C%E6%B1%82%E6%9C%89%E5%A4%9A%E5%B0%91%E7%A7%8D%E5%88%86%E6%B3%95%E4%B8%8B%E5%9B%BE%E4%B8%BA4%E4%B8%AA%E5%85%83%E7%B4%A0%E7%9A%841%E5%88%B04%E4%B8%AA%E5%AD%90%E9%9B%86%E7%9A%84%E5%88%86%E6%B3%95%E7%BB%93%E6%9E%84%E5%9B%BE)
集合的子集问题由n个不同元素组成的集合,现在分成x个子集(子集不能为空),求有多少种分法下图为4个元素的1到4个子集的分法结构图
集合的子集问题
由n个不同元素组成的集合,现在分成x个子集(子集不能为空),求有多少种分法
下图为4个元素的1到4个子集的分法结构图
集合的子集问题由n个不同元素组成的集合,现在分成x个子集(子集不能为空),求有多少种分法下图为4个元素的1到4个子集的分法结构图
一个有着n个元素的集合,它共有多少个可能的子集呢?由于在组成一个子集的时候,每一个元素都有被取过来或者不被取过来两种可能,因此,n个元素的集合就有2^n个不同的构造子集的方法,也就是,它一共有2^n个不同的子集,包括空集和全集在内.空集与全集如果不考虑的话,就剩下2^n-2个非空真子集.
举例来说明,对於一个集合
A={a,b,c},他的部分集合共有下面8 个:
{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}
即2的3次方8个.
如果考虑x的变量
思路是这样的:把n个元素编号,对於最后那个n号元素,有两种情况.一种是独立组成一个集合,另一种是和别的元素混在一起.
对於第一种情况,等价于把前n-1个元素分成x-1份,然后n号元素单独放.
对於第二种情况,等价于把前n-1个元素分成x份,然后把n号元素放入这x个集合中的一个(也就是说有x种放法)
那麽总数就是
F(n,x) = F(n-1,x-1) + x* F(n-1,x)
实际数学上这个叫做“第二类Stirling数”,
有一个直接计算的公式,F(n,x) = 1/x!*sum((-1)^k * C(x,k)*(x−k)^n,k=1...x)
Cnx*(x^(x-n))
2的n次方减1
可以用排列组合方法求
插板法Cn-2(x-1)
N*(N-1)(N-2).....(N-X+1)
加上空集有2^n个子集,若不加空集则有2^n-1 个
2^n-1
(2^n-1)*(2^n-2)*...*(2^n-1-x)
首先这个集合有2^n-1个非空真子集,从中选择x个,第一次有2^n-1种选择,第二次有2^n-2种选择……第x次有2^n-1-x次种选择
乘起来就行了
很简单 想象一下n个球排成一列,有n-1个位置可以插入,要插入x-1快板,那么便分成x份了,所以答案是C(x-1,n-1)