Menu Close

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-

Tinku Tara 0 Comments
Pin




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 ⊆ B nor B ⊆ A?
$$\mathrm{What}\:\mathrm{is}\:\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:\mathrm{ordered}\:\mathrm{pairs} \\ $$$$\left({A},\:{B}\right)\:\mathrm{where}\:{A}\:\mathrm{and}\:{B}\:\mathrm{are}\:\mathrm{subsets}\:\mathrm{of} \\ $$$$\left\{\mathrm{1},\:\mathrm{2},\:…,\:\mathrm{5}\right\}\:\mathrm{such}\:\mathrm{that}\:\mathrm{neither}\:{A}\:\subseteq\:{B} \\ $$$$\mathrm{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 ×(C_1 ^4 +C_2 ^4 +C_3 ^4 +C_4 ^4 ) +C_2 ^5 ×(C_1 ^3 +C_2 ^3 +C_3 ^3 )×[1+2(C_1 ^1 )] +C_3 ^5 ×(C_1 ^2 +C_2 ^2 )×[1+2(C_1 ^2 +C_2 ^2 )] +C_4 ^5 ×(C_1 ^1 )×[1+2(C_1 ^3 +C_2 ^3 +C_3 ^3 )] =570
$$\mathrm{I}\:\mathrm{got}\:\mathrm{the}\:\mathrm{answer}\:\mathrm{570},\:\mathrm{but}\:\mathrm{I}\:\mathrm{was} \\ $$$$\mathrm{uncertain}. \\ $$$$\mathrm{C}_{\mathrm{1}} ^{\mathrm{5}} ×\left(\mathrm{C}_{\mathrm{1}} ^{\mathrm{4}} +\mathrm{C}_{\mathrm{2}} ^{\mathrm{4}} +\mathrm{C}_{\mathrm{3}} ^{\mathrm{4}} +\mathrm{C}_{\mathrm{4}} ^{\mathrm{4}} \right) \\ $$$$+\mathrm{C}_{\mathrm{2}} ^{\mathrm{5}} ×\left(\mathrm{C}_{\mathrm{1}} ^{\mathrm{3}} +\mathrm{C}_{\mathrm{2}} ^{\mathrm{3}} +\mathrm{C}_{\mathrm{3}} ^{\mathrm{3}} \right)×\left[\mathrm{1}+\mathrm{2}\left(\mathrm{C}_{\mathrm{1}} ^{\mathrm{1}} \right)\right] \\ $$$$+\mathrm{C}_{\mathrm{3}} ^{\mathrm{5}} ×\left(\mathrm{C}_{\mathrm{1}} ^{\mathrm{2}} +\mathrm{C}_{\mathrm{2}} ^{\mathrm{2}} \right)×\left[\mathrm{1}+\mathrm{2}\left(\mathrm{C}_{\mathrm{1}} ^{\mathrm{2}} +\mathrm{C}_{\mathrm{2}} ^{\mathrm{2}} \right)\right] \\ $$$$+\mathrm{C}_{\mathrm{4}} ^{\mathrm{5}} ×\left(\mathrm{C}_{\mathrm{1}} ^{\mathrm{1}} \right)×\left[\mathrm{1}+\mathrm{2}\left(\mathrm{C}_{\mathrm{1}} ^{\mathrm{3}} +\mathrm{C}_{\mathrm{2}} ^{\mathrm{3}} +\mathrm{C}_{\mathrm{3}} ^{\mathrm{3}} \right)\right] \\ $$$$=\mathrm{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.
$$\mathrm{Using}\:\mathrm{a}\:\mathrm{similar}\:\mathrm{method}\:\mathrm{to}\:\mathrm{below},\:\mathrm{we} \\ $$$$\mathrm{can}\:\mathrm{derive}\:\mathrm{a}\:\mathrm{more}\:\mathrm{general}\:\mathrm{form}\:\mathrm{for}\:\mathrm{the} \\ $$$$\mathrm{number}\:\mathrm{of}\:\mathrm{ordered}\:\mathrm{pairs}\:\left({A},\:{B}\right)\:\mathrm{where} \\ $$$${A},\:{B}\:\mathrm{are}\:\mathrm{subsets}\:\mathrm{of}\:\left\{\mathrm{1},\:\mathrm{2},\:\mathrm{3},\:…,\:{n}\right\}\:\mathrm{such} \\ $$$$\mathrm{that}\:\mathrm{neither}\:{A}\:\subseteq\:{B}\:\mathrm{and}\:{B}\:\subseteq\:{A}. \\ $$$$\mathrm{Suppose}\:\mathrm{that}\:\mid{A}\mid\:=\:{x}\:\mathrm{where}\:\mathrm{0}\:\leqslant\:{x}\:\leqslant\:\mathrm{5}. \\ $$$$\mathrm{There}\:\mathrm{are}\:^{\mathrm{5}} {C}_{{x}} \:\mathrm{ways}\:\mathrm{to}\:\mathrm{choose}\:\mathrm{the} \\ $$$$\mathrm{elements}\:\mathrm{of}\:\mathrm{set}\:\left\{\mathrm{1},\:\mathrm{2},\:\mathrm{3},\:\mathrm{4},\:\mathrm{5}\right\}\:\mathrm{that}\:\mathrm{belong} \\ $$$$\mathrm{to}\:{A}. \\ $$$$\mathrm{Furthermore},\:\mathrm{when}\:\mathrm{picking}\:\mathrm{the}\:\mathrm{elements} \\ $$$$\mathrm{of}\:{B},\:\mathrm{there}\:\mathrm{are}\:\mathrm{2}^{\mathrm{5}} \:\mathrm{options}\:\mathrm{without}\:\mathrm{any} \\ $$$$\mathrm{restrictions}.\:\mathrm{However},\:\mathrm{2}^{{x}} \:\mathrm{of}\:\mathrm{these}\:\mathrm{subsets} \\ $$$$\mathrm{fall}\:\mathrm{under}\:\mathrm{the}\:\mathrm{condition}\:{B}\:\subseteq\:{A}\:\mathrm{and}\:\mathrm{2}^{\mathrm{5}−{x}} \\ $$$$\mathrm{fall}\:\mathrm{under}\:\mathrm{the}\:\mathrm{condition}\:{A}\:\subseteq\:{B}. \\ $$$$\mathrm{However},\:\mathrm{these}\:\mathrm{two}\:\mathrm{cases}\:\mathrm{double}\:\mathrm{count} \\ $$$$\mathrm{the}\:\mathrm{case}\:\mathrm{where}\:{A}\:=\:{B}.\:\mathrm{Thus},\:\mathrm{the}\:\mathrm{total} \\ $$$$\mathrm{number}\:\mathrm{of}\:\mathrm{ways}\:\mathrm{to}\:\mathrm{pick}\:\mathrm{our}\:\mathrm{pair}\:\left({A},\:{B}\right) \\ $$$$\mathrm{when}\:\mathrm{we}\:\mathrm{have}\:\mid{A}\mid\:=\:{x}\:\mathrm{are} \\ $$$$\:^{\mathrm{5}} {C}_{{x}} \centerdot\left(\mathrm{2}^{\mathrm{5}} \:−\:\mathrm{2}^{{x}} \:−\:\mathrm{2}^{\mathrm{5}−{x}} \:+\:\mathrm{1}\right). \\ $$$$\mathrm{However},\:\mathrm{since}\:{x}\:\mathrm{can}\:\mathrm{range}\:\mathrm{from}\:\mathrm{0}\:\mathrm{to}\:\mathrm{5} \\ $$$$\mathrm{our}\:\mathrm{desired}\:\mathrm{answer}\:\mathrm{is}\:\mathrm{the}\:\mathrm{sum} \\ $$$$\underset{{x}=\mathrm{0}} {\overset{\mathrm{5}} {\sum}}\:^{\mathrm{5}} {C}_{{x}} \:\centerdot\:\left(\mathrm{2}^{\mathrm{5}} \:−\:\mathrm{2}^{{x}} \:−\:\mathrm{2}^{\mathrm{5}−{x}} \:+\:\mathrm{1}\right)\:=\:\mathrm{570}. \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *