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:
-
All possible subgroups of A = 2^m -1 (|A|=m) that are not empty.
-
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.
Best Answer
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.