What is the number of ordered pairs (A, B) where A and B are subsets of {1, 2, ..., 5} such that neither A ⊆ B nor B ⊆ A?


Question and Answers Forum

All Questions Topic List
Relation and Functions Questions
Previous in All Question Next in All Question
Previous in Relation and Functions Next in Relation and Functions
Question Number 19982 by Tinkutara last updated on 19/Aug/17

$What is the number of ordered pairs$ $(A, B) where A and B are subsets of$ ${1, 2, . . ., 5} such that neither A \subseteq B$ $nor B \subseteq A ?$
Commented by mrW1 last updated on 22/Aug/17

$I got the answer 570, but I was$ $uncertain .$ $C_{1}^{5} \times (C_{1}^{4} + C_{2}^{4} + C_{3}^{4} + C_{4}^{4})$ $+ C_{2}^{5} \times (C_{1}^{3} + C_{2}^{3} + C_{3}^{3}) \times [1 + 2 (C_{1}^{1})]$ $+ C_{3}^{5} \times (C_{1}^{2} + C_{2}^{2}) \times [1 + 2 (C_{1}^{2} + C_{2}^{2})]$ $+ C_{4}^{5} \times (C_{1}^{1}) \times [1 + 2 (C_{1}^{3} + C_{2}^{3} + C_{3}^{3})]$ $= 570$
	Answered by Tinkutara last updated on 21/Aug/17
	$Using a similar method to below, we can derive a more general form for the number of ordered pairs (A, B) where A, B are subsets of {1, 2, 3, ..., n} such that neither A ⊆ B and B ⊆ A. Suppose that ∣A∣ = x where 0 ≤ x ≤ 5. There are^5 C_x ways to choose the elements of set {1, 2, 3, 4, 5} that belong to A. Furthermore, when picking the elements of B, there are 2^5 options without any restrictions. However, 2^x of these subsets fall under the condition B ⊆ A and 2^(5−x) fall under the condition A ⊆ B. However, these two cases double count the case where A = B. Thus, the total number of ways to pick our pair (A, B) when we have ∣A∣ = x are ^5 C_x ∙(2^5 − 2^x − 2^(5−x) + 1). However, since x can range from 0 to 5 our desired answer is the sum Σ_(x=0) ^5 ^5 C_x ∙ (2^5 − 2^x − 2^(5−x) + 1) = 570.$
	$Using a similar method to below, we$ $can derive a more general form for the$ $number of ordered pairs (A, B) where$ $A, B are subsets of {1, 2, 3, . . ., n} such$ $that neither A \subseteq B and B \subseteq A .$ $Suppose that ∣ A ∣ = x where 0 ⩽ x ⩽ 5 .$ $There are^{5} C_{x} ways to choose the$ $elements of set {1, 2, 3, 4, 5} that belong$ $to A .$ $Furthermore, when picking the elements$ $of B, there are 2^{5} options without any$ $restrictions . However, 2^{x} of these subsets$ $fall under the condition B \subseteq A and 2^{5 - x}$ $fall under the condition A \subseteq B .$ $However, these two cases double count$ $the case where A = B . Thus, the total$ $number of ways to pick our pair (A, B)$ $when we have ∣ A ∣ = x are$ $^{5} C_{x} \cdot (2^{5} - 2^{x} - 2^{5 - x} + 1) .$ $However, since x can range from 0 to 5$ $our desired answer is the sum$ $\underset{x = 0}{\sum^{5}}^{5} C_{x} \cdot (2^{5} - 2^{x} - 2^{5 - x} + 1) = 570 .$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum