2
$\begingroup$

$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.

$\endgroup$
3
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ I'm so sorry, I tried editing the question as quickly as possible, since I got mixed up by both questions and made some kind of composition of the two. I do understand now why it is $3^n - 2^n$, so thanks!, but my (newly edited) question it different. $\endgroup$ – Cauthon Nov 4 '14 at 13:50
  • $\begingroup$ You do not specify whether $A$ is a specific set (the natural interpretation of the wording, very easy answer) or you are looking for all ordered pairs $(A,B)$ with $A$ of cardinality $k$. I imagine the question will be modified again. $\endgroup$ – André Nicolas Nov 4 '14 at 13:58
  • $\begingroup$ Sorry, $A$ is a specific set with $k$ elements. $\endgroup$ – Cauthon Nov 4 '14 at 13:59
  • $\begingroup$ Thanks André, this completely cleared up my foggy mind. $\endgroup$ – Cauthon Nov 4 '14 at 14:19
  • $\begingroup$ You are welcome. $\endgroup$ – André Nicolas Nov 4 '14 at 14:20

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.