The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions.
test series counting
+4
votes
270
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 = Φ ________.
counting
permutationsandcombinations
asked
Jan 4, 2017
in
Combinatory
by
sanyam53
(
415
points)
retagged
Jun 27, 2017
by
Arjun

270
views
Facebook
Google+
Twitter
answer
comment
0
360?? (if repeatations not allowed)
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
1
Answer
+6
votes
Best answer
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 $n1$ elements.
Number of ways = $\binom{n}{1}2^{n1}$
and so on...
So final answer is $\sum_{i=0}^n \binom{n}{i}2^{ni} = 3^n$
answered
Jan 4, 2017
by
air1
Loyal
(
3.9k
points)
selected
Sep 7, 2017
by
Habibkhan
comment
0
@Habib ans given 729
0
Moreover another thing tell me why ordered or unordered pair required here?
Say one set contain X={ }
then other set contain Y={1,2,3,4,5,6} or {1,2,3,4,5} or {1,2,3,4} or ..........
Can somebody explain it in detail with example?
Please
log in
or
register
to add a comment.
← Prev. Qn. in Sub.
Next Qn. in Sub. →
← Prev.
Next →
Related questions
+1
vote
2
answers
1
Counting Kenneth Rosen Exercise
asked
2 days
ago
in
Combinatory
by
Abhinavg
(
57
points)

100
views
discretemathematics
kennethrosen
counting
permutationsandcombinations
+4
votes
1
answer
2
Discrete Mathematics By Kenneth H Rosen Counting
asked
4 days
ago
in
Combinatory
by
Sayed Athar
(
69
points)

62
views
discretemathematics
permutationsandcombinations
counting
+1
vote
2
answers
3
Counting problem
asked
Jan 11
in
Combinatory
by
AnilGoudar
Loyal
(
4.7k
points)

80
views
discretemathematics
counting
permutationsandcombinations
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
I have gate score of 719,and rank 491,which colleges should i apply for mtech cse,i dont intend to do ms research?
To GO Admins: Why does GO require access to my Google Contacts and other unnecessary information? (see image)
which should be a better choice among IIT roorkee,iit gandhinagar,IIIT delhi and IIIT bangalore for M.tech CSE?
If Admins can reply ?
ECIL GET INTERVIEW EXPERIENCE
All categories
General Aptitude
1.2k
Engineering Mathematics
4.8k
Discrete Mathematics
3.3k
Mathematical Logic
1.3k
Set Theory & Algebra
883
Combinatory
595
Graph Theory
562
Probability
608
Linear Algebra
503
Calculus
360
Digital Logic
2k
Programming & DS
3.5k
Algorithms
3k
Theory of Computation
3.8k
Compiler Design
1.5k
Operating System
2.7k
Databases
2.8k
CO & Architecture
2.5k
Computer Networks
2.9k
Non GATE
942
Others
1.2k
Admissions
345
Exam Queries
412
Tier 1 Placement Questions
17
Job Queries
52
Projects
8
Follow @csegate
Gatecse
Recent Blog Comments
@
I got 74.55% in BE(CS) and have 80% through out ...
Thank you bhai :)
satyajeet singh i guess u will be eligible for MS ...
GENERAL CATEGORY
34,295
questions
41,040
answers
116,531
comments
39,943
users