Question

Let S={1,2,3,....,n}. the number of unordered pairs (A,B) of subsets S such tht A & B have no elements in common is (A or B or both may be empty)

Answer 1

@zepdrix

Answer 2

@3mar

Answer 3

Hint :
When \(A\) is empty, \(B\) can be any subset of \(S\).
Next recall that number of subsets of a set with \(n\) elements is \(2^n\).

Answer 4

I am sorry for late!

+I really don't know.
It is not from honesty to answer a question I do not know.

Answer 5

It’s common knowledge that S has 2^n different subsets. So there are 2^n•(2^n-1) /2=(2^n-1)•2^(n-1) ways to choose a pair of 2 different subsets;
Now we count C(n) - how many ways a pair of subsets may have no common elements. Given any two such subsets S1 and S2, consider any elements A in S

A is neither in S1 or S2. So S1 and S2 are subsets of S-{A} and have no common elements. We have C(n-1) ways to pick the 2 subsets;
A is either in S1 or S2. If A is in S1, S1-{A} and S2 are different subsets of S-{A} with no common elements unless S1-{A}=S2=empty; If A is in S2, S1 and S2-{A} are different subsets of S-{A} with no common elementsunless S1=S2-{A}=empty; either case again reduces to C(n-1), except for the empty sets situation. So we have 2•C(n-1) ways for non empty cases;. Adding the single empty set case we get 2•C(n-1) +1
Putting above two bullet points we have C(n)=3•C(n-1) +1; it's easy to solve this to get C(n)=(3^n-1)/2

Answer 6

The above is from
https://www.quora.com/In-how-many-ways-can-we-choose-two-subsets-from-an-n-elements-set-so-that-they-have-a-non-empty-intersection#!n=12

Answer 7

How many possibilities to choose B as a subset of the set of the n-3 remaining elements?
@ganeshie8 gave the hint: it is \(2^{n-3}\).

Also note that there are \(\binom{n}{3}\) ways to choose \(A\) as a subset containing exactly 3 elements.

Summary: among all choices of A and B, there are those with \(|A|=3\), and the number of terms related to this term is:
\[\binom{n}{3} 2^{n-3}.\]

What about the case \(|A|=0\), \(|A|=1\), …, \(|A|=n\) ?