离散数学拾趣（三）：集合的子集有多少个

集合广泛应用于计数问题，这类问题需要讨论集合的大小。

令S为集合。若S中恰有n个不同的元素，n是非负整数，就说S是有限集合，而n是S的基数，用|S|表示。若S={ 1, 2, 3 }，则|S| = 3。

有时候需要考虑一个集合的元素所有可能的组合，看它们是否具有某种性质。为此构造一个新的集合，它以S的所有子集作为它的元素，该集合称为S的幂集合，记为P(S)。

比如：

本文的主题也就是：对于集合S，P(S)的基数是多少？

方法一：首先观察上面例子中的三个集合，它们的基数分别是0、1、2，而它们的幂集合的基数分别是，于是可以猜想n个元素的集合有个子集，下面用数学归纳法证明。

基础步骤：由上面例子可知，当n=0时命题为真。

归纳步骤：假定当n=k时命题成立，即每个有k个元素的集合有个子集。设T是有k+1个元素的集合，那么T至少包含一个元素，任取其中的一个元素a，设，即，S有k个元素。对于S的每个子集X来说，恰好存在两个T的子集，即X和，这些子集构成了T的所有子集并且互不相等，因为S有个子集，所以T有个子集，也就是说当n=k+1时命题也成立，命题得证。

方法二：对于集合S，|S|=n。可以按任意顺序将这n个元素排成一个序列，要确定一个子集，也就是对于n个元素依次确定它是否属于该子集，如果属于记为1，否则记为0。这样，确定了一个集合之后，也确定了一个n位长的二进制串。（假设S有3个元素，其中的一个二进制串是110，它表示前两个元素属于相应的子集，而第三个元素不属于）可以得出，S的所有子集与所有n位的二进制串一一对应，而对于n位的二进制串，由乘积法则（或乘法原理）可知共有个，这样也可以证明。

方法三：对于集合S，|S|=n，该命题还可以使用组合证明。可以按如下顺序寻找S的子集：先找有0个元素的子集；再找有1个元素的子集；...；最后找有n个元素的子集()。它们的个数分别是，它们的和恰好是，命题得证。

对于这种方法，在离散数学中会比较常见，在计数的时候通过一一对应将问题转化为更简单的问题，比如二进制串、树的路径等。

在撰写本文内容时，也是在尝试OpenOffice Math和Live Writer结合使用，使用OO Math编写数学公式，最后文档可以直接导出为HTML，其中的公式以gif的格式创建，以Firefox打开生成的HTML文件，通过Blog This for Firefox插件可以将文件内容拷贝到一个新的Post中，然后微调，效果没有生成的HTML好，不过还可以接受。在Firefox浏览，默认情况下公式图片可能会有些模糊，可以将字体缩小一点儿。不知道怎样才能在HTML中更好地添加数学公式？清晰版的还是看PDF吧。

参考：