GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
99 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)   | 99 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 (3k points)  
edited by


Top Users Apr 2017
  1. akash.dinkar12

    3826 Points

  2. Divya Bharti

    2798 Points

  3. Deepthi_ts

    2294 Points

  4. rude

    2142 Points

  5. Prashant.

    1900 Points

  6. Tesla!

    1888 Points

  7. Kapil

    1842 Points

  8. Debashish Deka

    1830 Points

  9. Arjun

    1810 Points

  10. Sanjay Sharma

    1712 Points

Monthly Topper: Rs. 500 gift card

22,177 questions
28,201 answers
63,649 comments
24,364 users