[比赛]求证:含n各元素的集合,其子集个数为2^n.1.不要求很高的严谨性,但必须要有道理.2.证明要有创新性,能够体现独特的思维风格.3.在以上前提下尽量做到简洁.谁的证明最好(必须比我的证
来源:学生作业帮助网 编辑:六六作业网 时间:2024/10/03 04:56:39
[比赛]求证:含n各元素的集合,其子集个数为2^n.1.不要求很高的严谨性,但必须要有道理.2.证明要有创新性,能够体现独特的思维风格.3.在以上前提下尽量做到简洁.谁的证明最好(必须比我的证
[比赛]求证:含n各元素的集合,其子集个数为2^n.
1.不要求很高的严谨性,但必须要有道理.
2.证明要有创新性,能够体现独特的思维风格.
3.在以上前提下尽量做到简洁.
谁的证明最好(必须比我的证明好),谁就可以获得100分悬赏,特别优秀者,还有10至50分的追加.
[比赛]求证:含n各元素的集合,其子集个数为2^n.1.不要求很高的严谨性,但必须要有道理.2.证明要有创新性,能够体现独特的思维风格.3.在以上前提下尽量做到简洁.谁的证明最好(必须比我的证
用二项式定理
n个元素集合的子集有nC0+nC1+nC2+nC3+...+nCn
(1+1)^n=nC0+nC1+nC2+nC3+...+nCn=2^n
所以n个元素集合的子集共有2^n个
每个元素有存在或不存在两种情况
2*2*2*......*2=2^n
若无空集,则2^n-1
根据排列组合的知识。含零个元素的子集数;含一个元素的子集数……含n个元素的子集数。然后相加。高中课本里都有;学到排列组合时就会讲到。
若A中有三个元素则它的子集有:它本身,空集,和三个元素单独构成得三个,两两配对成的三个,一共有2^3=8个子集。
其实,可以考虑:有几个元素,便用几来配对,把最后的结果加以总结,正好是2^n。
利用组合的方法证明
分n+1种情况讨论:
在n个元素中取0个元素组成的子集,即为空集
在n个元素中随意取1个元素组成的子集,
在n个元素中随意取2个元素组成的子集,
在n个元素中随意取3个元素组成的子集,
.....
在n个元素中随意取n个元素组成的子集
将以上n+1个组合数相加,即得2^n
事实上,2^n是二项式(a+b)^...
全部展开
利用组合的方法证明
分n+1种情况讨论:
在n个元素中取0个元素组成的子集,即为空集
在n个元素中随意取1个元素组成的子集,
在n个元素中随意取2个元素组成的子集,
在n个元素中随意取3个元素组成的子集,
.....
在n个元素中随意取n个元素组成的子集
将以上n+1个组合数相加,即得2^n
事实上,2^n是二项式(a+b)^n展开式的系数之和,并且令a=b=1
得证
收起
简单的计数问题
设集合A={a1,a2,a3,a4……an}
第一步:a1 在子集内;不在子集内 ,2种可能 ,子集数:2*=2^1
第二步:a2 在子集内;不在子集内 ,2种可能 ,子集数:2*2=2^2
第三步:a3 在子集内;不在子集内 ,2种可能 ,子集数:2*2*2=2^3
第四步:a4 在子集内;不在子集内 ,2种可能 ,子集...
全部展开
简单的计数问题
设集合A={a1,a2,a3,a4……an}
第一步:a1 在子集内;不在子集内 ,2种可能 ,子集数:2*=2^1
第二步:a2 在子集内;不在子集内 ,2种可能 ,子集数:2*2=2^2
第三步:a3 在子集内;不在子集内 ,2种可能 ,子集数:2*2*2=2^3
第四步:a4 在子集内;不在子集内 ,2种可能 ,子集数:2*2*2*2=2^4
……
第n步: an 在子集内;不在子集内 ,2种可能 ,子集数:2*2*……=2^n
搞定。
收起
每个元素有两种情况:存在\不存在
共有N个元素则子集有2^N
利用组合的方法证明
分n+1种情况讨论:
在n个元素中取0个元素组成的子集,即为空集 C0
在n个元素中随意取1个元素组成的子集,C1
在n个元素中随意取2个元素组成的子集,C2
...............
一直到Cn
C0+C1+C2+C3+...+Cn
这个式子就是一个特殊2项式(1+1)展开之后得到的所有项
全部展开
利用组合的方法证明
分n+1种情况讨论:
在n个元素中取0个元素组成的子集,即为空集 C0
在n个元素中随意取1个元素组成的子集,C1
在n个元素中随意取2个元素组成的子集,C2
...............
一直到Cn
C0+C1+C2+C3+...+Cn
这个式子就是一个特殊2项式(1+1)展开之后得到的所有项
所以=2^n
收起