Research Space for Linear Algebra & Discrete Mathematics
(1) 所有的pair數為: (2^n)^2 = 4^n(2) 考慮以下左邊的集合可以被多少個集合包含:{}: 2^n{x1}: 2^(n-1), {x1} 共有 c(n,1) 種取法{x1,x2}: 2^(n-2), {x1,x2} 共有 c(n,2) 種取法...{x1,...,xn}: 2^0, {x1,...,xn} 共有 c(n,n) 種取法上面的加總就是 3^n, 可是這 3^n 個有包含關係的pair, pair裡的element都可以左右互掉, 所以再乘以 2, 可是乘以2後會重複算了自己和自己成為一個pair的部分(共有 2^n), 所以有互相包含關係的ordered pair總數為 2(3^n)-2^n所以由(1),(2), 沒有互相包含關係的ordered pair總數為 4^n - (2(3^n)-2^n) = 4^n - 2(3^n) + 2^n
張貼留言
1 則留言:
(1) 所有的pair數為: (2^n)^2 = 4^n
(2) 考慮以下左邊的集合可以被多少個集合包含:
{}: 2^n
{x1}: 2^(n-1), {x1} 共有 c(n,1) 種取法
{x1,x2}: 2^(n-2), {x1,x2} 共有 c(n,2) 種取法
...
{x1,...,xn}: 2^0, {x1,...,xn} 共有 c(n,n) 種取法
上面的加總就是 3^n, 可是這 3^n 個有包含關係的pair, pair裡的element都可以左右互掉, 所以再乘以 2, 可是乘以2後會重複算了自己和自己成為一個pair的部分(共有 2^n), 所以有互相包含關係的ordered pair總數為 2(3^n)-2^n
所以由(1),(2), 沒有互相包含關係的ordered pair總數為
4^n - (2(3^n)-2^n) = 4^n - 2(3^n) + 2^n
張貼留言