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 ⊆ 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}. \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com