GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
92 views
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 = Φ ________.
asked in Combinatory by (199 points)   | 92 views
360?? (if repeatations not allowed)

1 Answer

+2 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$
answered by Loyal (2.9k points)  
edited by


Top Users Mar 2017
  1. rude

    4758 Points

  2. sh!va

    3014 Points

  3. Rahul Jain25

    2830 Points

  4. Kapil

    2636 Points

  5. Debashish Deka

    2442 Points

  6. 2018

    1514 Points

  7. Vignesh Sekar

    1416 Points

  8. Akriti sood

    1298 Points

  9. Bikram

    1286 Points

  10. Sanjay Sharma

    1076 Points

Monthly Topper: Rs. 500 gift card

21,471 questions
26,802 answers
61,040 comments
23,037 users