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$

1 Answer 1

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$
5
  • $\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
    Commented Nov 4, 2014 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$ Commented Nov 4, 2014 at 13:58
  • $\begingroup$ Sorry, $A$ is a specific set with $k$ elements. $\endgroup$
    – Cauthon
    Commented Nov 4, 2014 at 13:59
  • $\begingroup$ Thanks André, this completely cleared up my foggy mind. $\endgroup$
    – Cauthon
    Commented Nov 4, 2014 at 14:19
  • $\begingroup$ You are welcome. $\endgroup$ Commented Nov 4, 2014 at 14:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .