GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
76 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 (139 points)   | 76 views
360?? (if repeatations not allowed)

1 Answer

+1 vote
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 Jan 2017
  1. Debashish Deka

    8618 Points

  2. sudsho

    5402 Points

  3. Habibkhan

    4718 Points

  4. Bikram

    4522 Points

  5. Vijay Thakur

    4468 Points

  6. saurabh rai

    4222 Points

  7. Arjun

    4136 Points

  8. santhoshdevulapally

    3742 Points

  9. Sushant Gokhale

    3576 Points

  10. GateSet

    3398 Points

Monthly Topper: Rs. 500 gift card

19,188 questions
24,075 answers
52,997 comments
20,314 users