Finding all subsets $B \subseteq U$ such that $A \cap B \neq \emptyset$ $A$ is a specific set with $k$ elements, $A \subseteq U$, $U$ has $n$ elements. I would like to count all ways to choose subset $B \subseteq U$ where $A \cap B \neq \emptyset$.
I know that $B$ must have either one of $A$'s elements (and then it has another $2^{n-1}$ subsets of $U$, or two (and then we have $2^{n-2}$ of the rest), etc. until $k$. But I just don't see how to count all these possibilities for $B$s.
 A: Edit: The question was entirely changed while I was typing the answer below. We answer the new question in the "Added" part at the end.
Old answer: The expression $3^n-2^n$ that you give counts the number of ordered pairs $(A,B)$ such that $A\cap B\ne \emptyset$.  An adjustment of the type you are familiar with from the previous question takes care of unordered pairs.
We first count the ordered pairs with no restriction on $A\cap B$.  For any such ordered pair, let $f:U\to \{0,1,2\}$ be defined by $f(x)=0$ if $x\in A\setminus B$, $f(x)=1$ if $x\in \setminus A$, and $f(x)=2$ if $x\in A\cap B$.
The number of functions is the number of ordered pairs $(A,B)$ of subsets of $U$. So there are $3^n$ ordered pairs.  The ordered pairs $(A,B)$ with $A\cap B\ne \emptyset$ correspond to the functions $f$ that never take the value $2$. There are $2^n$ functions from $U$ to $\{0,1\}$.
So by simple Inclusion/Exclusion, our count is $3^n-2^n$.
Added: Suppose now that $A$ is a fixed $k$-element set, and we want to count the sets $B$ such that $A\cap B\ne \emptyset$. Such a $B$ is uniquely determined by the ordered pair $(A\cap B, U\setminus A)$.
We can chose $A\cap B$ in $2^k-1$ ways, since $A$ has $2^k-1$ non-empty subsets. For each such choice the part $B\setminus A$ can be any subset of $U\setminus A$. There are $2^{n-k}$ of these, for a total of $(2^k-1)(2^{n-k})$.
More simply, $U$ has $2^n$ subsets. The only "bad" $B$ are the subsets of $U\setminus A$, and there are $2^{n-k}$ of these, for a total of $2^n-2^{n-k}$.
