retagged by
740 views
4 votes
4 votes
The number of pairs of set (X, Y) are there that satisfy the condition X, Y ⊆ {1, 2, 3,
4, 5, 6} and X ∩ Y = Φ ________.
retagged by

1 Answer

Best answer
9 votes
9 votes
If we are counting ordered pairs $(X, Y)$, then for each element of the set we have three choices. Put it in set X, in Y or in none of them. So total ways = $3^n$.

If we are counting unordered pairs $(X, Y)$, then except for the pair $({}, {})$, all pairs have been counted twice. So toal ways are $\frac{3^n - 1}{2} + 1$.

Here $n = 6$, so answer for first case is $3^6 = 729$ and for second case $\frac{3^6 - 1}{2} + 1 = 365$.

Another method:

 

Suppose $X$ has 0 elements (which can be chosen in $\binom{n}{0}$ ways), then $Y$ can include or not include any of the $n$ elements of the give set.

Number of ways = $\binom{n}{0}2^n$

If $X$ has 1 element (which can be chosen in $\binom{n}{1}$ ways), then $Y$ can include or not include any of the remaining $n-1$ elements.

Number of ways = $\binom{n}{1}2^{n-1}$

and so on...

So final answer is $\sum_{i=0}^n \binom{n}{i}2^{n-i} = 3^n$
selected by

Related questions

1 votes
1 votes
1 answer
2
Lakshman Bhaiya asked Oct 24, 2018
542 views
A number of ways we can arrange letters of the word " TESTBOOK " such that E always comes between O's is ___________