GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
88 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)   | 88 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 Feb 2017
  1. Arjun

    5166 Points

  2. Bikram

    4204 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. sriv_shubham

    2298 Points

  6. Debashish Deka

    2234 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    1998 Points

  9. mcjoshi

    1626 Points

  10. sh!va

    1552 Points

Monthly Topper: Rs. 500 gift card

20,815 questions
25,974 answers
59,606 comments
22,025 users