# Find the number of ordered pairs (A,B) such that A∩B≠∅

Find the number of ordered pairs $(A,B)$ such that $A\subseteq S$ ($A$ is a subset of $S$), $B\subseteq S$, and $A\cap B\ne \emptyset$ (A,B≠∅).

Im sory in advance for my poor english and luck of mathematics signuters.

My answer is (Currect after some fixes): $4^{n}-3^n$

For every pair $(A,B)$ that $A,B \neq \emptyset$ , $B \in \mathscr{P}(S\setminus A) \cup (\mathscr{P}(A)\setminus \emptyset)$.
To count how many $B$ there are, I multiply:

1. All possible subgroups of A = 2^m -1 (|A|=m) that are not empty.

2. All possible subgroups of S\A = 2^(n-m) (It is important to save the empty set so with that we get : $(A,X \in A)$ as pairs!!)

So we get a total of $(2^m -1)\cdot(2^{n-m})$ subgroups of $S$ that are not foreign to $A$.

For every group that has $m$ elements, there exist ${n \choose m}$ subgroups.

So we get:

$\Sigma_{m=1}^n {n \choose m}\cdot(2^m)\cdot(2^{n-m} -1)$ which equals $4^n - 3^n$.

Thank you,

Stav.

I think you want to find the number of ordered pairs $(A,B)$ such that $A\subseteq S$ ($A$ is a subset of $S$), $B\subseteq S$, and $A\cap B\ne \emptyset$.

First we count the number of ordered pairs $(A,B)$ of subsets of $S$. There are $2^n$ choices for $A$, and for each such choice there are $2^n$ choices for $B$, for a total of $2^{2n}$, that is, $4^n$.

Now we count the bad ordered pairs, the ones where $A\cap B=\emptyset$.

To make such an ordered pair, for every $k\le n$ we have $3$ choices for what to do with $k$: (i) $k\in A$ and $k\not\in B$; (ii) $k\in B$ and $k\not\in A$; (iii) $k$ in neither $A$ nor $B$. So there are $3^n$ bad ordered pairs.

It follows that the required number of ordered pairs is $4^{n}-3^n$.

Remark: Your procedure is either correct or nearly correct. You also went after the "bad" pairs. Using the binomial theorem on your sum should give us $3^n$, or something close to that.

• First of all, thank you for your solution. Secondly- about that k, is it correct to say that: (i) k∈A and k∈!B; (ii) k∈B and k∈!A; (iii) k in neither A nor B ? Jun 9 '16 at 19:48
• Yes, I should have put it that way, but because I was looking only at the bads, it is automatic that if $k\in A$ then $k\not\in B$, But still, it would be better to be explicit. Will edit. Jun 9 '16 at 19:54
• Thank you agian. Anyway, I think my solution count how much pairs are foreign insted of not foreign to each other. Jun 9 '16 at 19:55
• Yes, I said in a comment that you also went after the bads (disjoints). But after you count those, it is easy to get the "not disjoints." I think the number of bads is actually $\sum_0^n \binom{n}{m}2^{n-m}$, which simplifies to $3^n$. Jun 9 '16 at 20:03
• If you could give another look on my updated solution, it would be great. Jun 9 '16 at 20:27