很久沒有更新了...（主要是因為我懶qwq）

例 設 n 是正整數， S={1,2,cdots,n} ，設 A ， B 均為 S 的子集且 Acup B=S 。問：這樣的 A , B 構成的「有序對」（即當 A e B 時把 A , B 和 B ， A 視為兩對）有多少個？

解答1 設 |Acap B|=k ，容易知道 k=0,1,2,cdots ,n

此時滿足條件的「有序對」有 C_n^kcdot 2^{n-k}=C_n^{n-k}cdot 2^{n-k}

因此所有「有序對」的個數為 sum_{k=0}^nC_n^{n-k}cdot 2^{n-k}=sum_{k=0}^nC_n^{k}cdot 2^{k}

注意到 3^n=(1+2)^n=sum_{k=0}^nC_n^{k}cdot 2^{k} ，因此「有序對」有 3^n 個。

另外，還有一種比較快的辦法，由 @JZSAWYER 提供：

解答2 S 中的任意一個元素要麼只在集合 A 中，要麼只在集合 B 中，要麼同時在集合 A 和集合 B 中，因此「有序對」有 3^n 個。

推薦閱讀：

相关文章