老王的夢田

部分集合的個數

我們經常遇到的一個問題就是，給定A集合，然後問A有多少個部份集合？

這個問題的解法，基本都是由「A的部份集合中的元素，必然還是A的元素」這個觀點來看，那麼對於A中某個元素，可以有「選」和「不選」兩種情形，所以若A有n個元素，那麼就會有2ⁿ個部份集合。

也可以這樣看：「A的部份集合中的元素是從A的元素選出來的」，而元素個數必然不超過n，所以是：

0個元素有C₀ⁿ個

1個元素有C₁ⁿ個

2個元素有C₂ⁿ個

…………………………….

n個元素有C_nⁿ個

總共有C₀ⁿ＋C₁ⁿ＋C₂ⁿ＋…………＋C_nⁿ＝2ⁿ

或許這種方法不如第一種簡單漂亮，但是當你想不出簡單漂亮的解法時，何不試試這種基本的土法煉鋼。

如果現在問題改成：假設集合W有n個相異元素，若A、B都是W的部份集合，且滿足A⊂B⊂W，那麼(A，B)共有多少不同的解？

【解】

看不懂題目？？別放棄，通常如此。再看一遍，先從簡單情況下手。

例如W＝{1，2}，而B比較靠近W，所以從B下手。

若B＝Φ，那麼A也只能是Φ；（Φ表示空集合）

若B＝{1}，A可以是Φ或{1}；

若B＝{2}，A可以是Φ或{2}；

若B＝{1，2}，A可以是Φ或{1}或{2}或{1，2}。

從上面討論可以知道，一共有1＋2＋2＋4＝9組不同解。

所以針對W有n個相異元素時，先選B，再討論A時，就是一開始的問題。

若B＝Φ，那麼A有1種可能；

若B有1個元素，A有2種可能，此時B有C₁ⁿ種選取方式；

若B有2個元素，A有2²種可能，此時B有C₂ⁿ種選取方式；

若B有3個元素，A有2³種可能，此時B有C₃ⁿ種選取方式；

…………………………………………

若B有n個元素，A有2ⁿ種可能，此時B有C_nⁿ種選取方式。

1×1＋C₁ⁿ×2＋C₂ⁿ×2²＋C₃ⁿ×2³＋……………………＋C_nⁿ×2ⁿ＝(1＋2)ⁿ＝3ⁿ

很神奇的答案吧！！

畫個圖來解釋，

現在只要考慮W的n個元素所擺的位置：可以在A裡面（黃色區域）；或是在B裡面而不在A裡面（水藍色區域）；或是在W裡面而不在B裡面（綠色區域）。於是每個元素都有三種選擇，是以答案是3ⁿ

仿照上面的方法，可以得到一個無聊的公式：

集合W有n個相異元素，若有m個集合A₁，A₂，A₃，…………，A_m滿足A₁⊂A₂⊂A₃⊂…………⊂A_m⊂W，那麼（A₁，A₂，A₃，…………，A_m）共有多少不同的解？

答案就是(m＋1)ⁿ