如何证明原集合中每个元素在幂集中的出现次数为子集总数的一半？

这个问题其实可以用几种不同的思路来严谨证明，每种方法都很直观，我给你拆解一下：

方法1：直接构造计数法 #

假设我们有一个包含n个元素的集合A，现在固定其中任意一个元素，比如a。我们来数一下所有包含a的子集：

• 每个包含a的子集，都可以看作是「a加上A中去掉a后的集合的某个子集」。
• A去掉a后得到的集合有n-1个元素，它的幂集大小是2^(n-1)——这意味着有2^(n-1)种方式来搭配a形成新的子集。

而整个幂集P(A)的总子集数是2^n，2^(n-1)正好是2^n的一半。所以不管选哪个元素，它都恰好出现在半数子集中。

就像你举的例子：n=3时，2^(3-1)=4，正好对应x、y、z各出现4次。

方法2：数学归纳法 #

如果需要更严谨的形式化证明，数学归纳法是个好选择：

• 基例（n=1）：当A只有1个元素{a}时，幂集是{{}, {a}}，元素a出现在1个子集中，总子集数是2，1是2的一半，结论成立。
• 归纳假设：假设当集合有k个元素时，每个元素都出现在2^(k-1)个子集中（也就是总子集数2^k的一半）。
• 归纳步骤：考虑有k+1个元素的集合A = B ∪ {a}，其中B是k个元素的集合。
  • 幂集P(A)由两部分组成：B的所有子集，以及「B的子集加上a」形成的新子集。
  • 对于B中的每个元素，根据归纳假设，它在B的子集中出现2^(k-1)次，在带a的子集中也出现2^(k-1)次，总共是2^(k-1) + 2^(k-1) = 2^k次。而P(A)的总子集数是2^(k+1)，2^k正好是它的一半。
  • 对于新元素a，它只出现在「B的子集加上a」的那些子集中，数量是2^k，同样是总子集数的一半。
• 由此归纳可得，对任意正整数n，结论都成立。

方法3：组合数视角 #

从组合数学的角度看，包含固定元素a的子集数量，等价于「从剩下的n-1个元素中选任意数量的元素（包括0个），再和a组合」：

• 从n-1个元素中选i个元素的组合数是C(n-1, i)，那么所有包含a的子集数量就是求和：Σ（i从0到n-1）C(n-1, i)。
• 根据二项式定理，这个求和的结果就是2^(n-1)，而总子集数是Σ（i从0到n）C(n, i) = 2^n，显然2^(n-1)是2^n的一半。

不管用哪种方法，都能得出同一个结论：集合中的每个元素，恰好出现在幂集的半数子集中。

内容的提问来源于stack exchange，提问作者No Name QA