取 A 後, 有 2^|A| 個 [n] 的子集被 A 包含(其中包括空集合和 A 本身), 另外有 2^(n-|A|) 個 [n] 的子集包含 A (其中包括 A 本身, 不含空集合）, 所以共有 2^n-2^|A|-2^(n-|A|)+1 個 [n] 的子集和 A 沒有包含關係 (+1 是因為 A 本身被扣了兩次, sum 起來得到
取 A 後, 有 2^|A| 個 [n] 的子集被 A 包含(其中包括空集合和 A 本身), 另外有 2^(n-|A|) 個 [n] 的子集包含 A (其中包括 A 本身, 不含空集合）, 所以共有 2^n-2^|A|-2^(n-|A|)+1 個 [n] 的子集和 A 沒有包含關係 (+1 是因為 A 本身被扣了兩次, sum 起來得到
這就是 poset 裡最大 antichain 的數量囉.
回覆刪除to凱:
回覆刪除可以講清楚一點嗎？我理解比較差="=
我知道大概跟power set有關!!
可是我不太會算那個
A不包含於B且B不包含於A的個數!!
Hi, 我發現題目是要問number of order pairs, 所以應該是直接計算, 不是用 anti-chains.
回覆刪除Given A in [n], A 有 2^|A| 個子集, 除了空集合, 這些子集的補集和 A 都有 r 關係, 然後在計算有多少種 A, 你試試看, 這樣應該可以做.
Well, 應該沒錯. 以 n=3 為例
回覆刪除A={1}, B={2,3}
A={2}, B={1,3}
A={3}, B={1,2}
A={1,2}, B={2,3},{1,3},{3}
A={1,3}, B={2,3},{1,2},{2}
A={2,3}, B={1,3},{1,2},{1}
A=empty set or [n] 時不計算; fixed A 時, empty set 也不計算; 因為是 ordered pair, 所以 ({1},{2,3}) 和 ({2,3},{1}) 我當他們不同 (大不了除2), 所以, generally, 有 C(n,i) 種方法取 A 使得 |A|=i, 1 <=i <=n-1; fixed A with |A|=i, 有 2^i-1 種取 B, 所以是 Σ C(n,i)(2^i-1), 1 <=i <=n-1.
For n=3, we have
C(3,1)x1+C(3,2)x3=3+9=12,
which matches the example.
唷！了解了！
回覆刪除感謝你！
to 凱
回覆刪除我睡覺的時候想到!!
當A={1} B={2,3}
這樣是不是少取了B={2}或{3}??
嗯 對！想到對稱差去了.
回覆刪除取 A 後, 有 2^|A| 個 [n] 的子集被 A 包含(其中包括空集合和 A 本身), 另外有 2^(n-|A|) 個 [n] 的子集包含 A (其中包括 A 本身, 不含空集合）, 所以共有 2^n-2^|A|-2^(n-|A|)+1 個 [n] 的子集和 A 沒有包含關係 (+1 是因為 A 本身被扣了兩次, sum 起來得到
Σ C(n,i)(2^n-2^i-2^{n-i})+1, 1 <=i<=n.
For n=3, 3x(8-2-4+1)+3x(8-2-4+1)=18.
A={1}, B={2},{3},{2,3}
A={2}, B={1},{3},{1,3}
A={3}, B={1},{2},{1,2}
A={1,2}, B={2,3},{1,3},{3}
A={1,3}, B={2,3},{1,2},{2}
A={2,3}, B={1,3},{1,2},{1}
Match!! 這樣應該對了！ 那個 sum 也許可以整理一下..
嗯 對！想到對稱差去了.
回覆刪除取 A 後, 有 2^|A| 個 [n] 的子集被 A 包含(其中包括空集合和 A 本身), 另外有 2^(n-|A|) 個 [n] 的子集包含 A (其中包括 A 本身, 不含空集合）, 所以共有 2^n-2^|A|-2^(n-|A|)+1 個 [n] 的子集和 A 沒有包含關係 (+1 是因為 A 本身被扣了兩次, sum 起來得到
Σ C(n,i)(2^n-2^i-2^{n-i})+1, 1 <=i<=n.
For n=3, 3x(8-2-4+1)+3x(8-2-4+1)=18.
A={1}, B={2},{3},{2,3}
A={2}, B={1},{3},{1,3}
A={3}, B={1},{2},{1,2}
A={1,2}, B={2,3},{1,3},{3}
A={1,3}, B={2,3},{1,2},{2}
A={2,3}, B={1,3},{1,2},{1}
Match!! 這樣應該對了！ 那個 sum 也許可以整理一下..
好像是95成大電機的題目, 用排容蠻快的.
回覆刪除let N = u
a1: A包含於B的性質
a2: B包含於A的性質
=> N(a1'a2') = ...
這樣算就可以跳過不用想
"A不包含於B且B不包含於A的個數"
我最新的 post 精神上就是排容。
回覆刪除題庫班有提到一個A in B in U的
回覆刪除ordered pair (A, B)個數為3^n
當你有這個題目當基礎時, 會想到的
就是排容了
U : all ordered pair (A, B)
a1 : A in B
a2 : B in A
答案就會是計算N(a1'a2')
= S0 - S1 + S2
= 4^n - 2(3^n) + 2^n
S0 = |U| = (2^n)(2^n)
S2 = N(a1a2): all order pair (A,A)
N(a1a2) = 2^n