冪集以及集合的子集個數

2020-01-12 本文已影响0人執迷_4869

集合 $A$ 的冪集記為 $P(A)$ ， $P(A)$ 是 $A$ 所有子集的集合。
例如，設集合 $A = \left\{1, 2 \right\}$ , 則 $A$ 的冪集為 $\left\{ \varnothing, \left\{1\right\}, \left\{2\right\}, \left\{1, 2\right\}\right\}$ . 於是 $\left| P(A)\right| = 4$ ，即 $A$ 有四個不同的子集。
一般的，設 $A = \left\{ a_1, a_2, a_3, \cdots a_n\right\}$ , 則
$P(A) = \left\{\varnothing, \left\{a_1\right\}, \left\{a_2\right\}, \cdots, \left\{a_1, a_2\right\}, \left\{a_1, a_3\right\},\cdots,\cdots, \left\{a_1, a_2, \cdots, a_n\right\}\right\}$
$P(A)$ 的元素中，元素數量為0的集合（空集）的數目為 $1=C_n^0$ ，
元素數量為1的集合的數目為 $1 = C_n^1$ ，
元素數量為2的集合的數目為 $2=C_n^2$ ，
$\cdots$
$\cdots$
$\cdots$
所以，
$\left| P(A)\right| = C_n^0 + C_n^1 + C_n^2 + \cdots + C_n^n$
因為
$(1+x)^n = C_n^0 x^0 + C_n^1 x^1 + C_n^2 x^2 + \cdots + C_n^n x^n$
故
$\left|P(A)\right| = (1 + 1)^n = 2^n$
以上是从二项式定理得到 $|P(A)|=2^n$ ，但也可以从组合分析的角度来理解这个问题：对于集合A的一个元素以及某一个A的子集，这个元素可以选择属于或者不属于这个子集，即每个元素都有两个选择。于是，所有选择的个数，即所有子集的个数等于 $2^n$ .
結論：若集合 $A$ 共有 $n$ 個互不相同的元素，則 $A$ 共有 $2^n$ 個互不相同的子集。

冪集以及集合的子集個數

猜你喜欢

热点阅读