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,



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.

  • $\begingroup$ 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 ? $\endgroup$
    – Stav Alfi
    Jun 9 '16 at 19:48
  • $\begingroup$ 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. $\endgroup$ Jun 9 '16 at 19:54
  • $\begingroup$ Thank you agian. Anyway, I think my solution count how much pairs are foreign insted of not foreign to each other. $\endgroup$
    – Stav Alfi
    Jun 9 '16 at 19:55
  • $\begingroup$ 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$. $\endgroup$ Jun 9 '16 at 20:03
  • $\begingroup$ If you could give another look on my updated solution, it would be great. $\endgroup$
    – Stav Alfi
    Jun 9 '16 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.