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 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, \dots, 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, \dots, 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 .