Probability that two sets do not intersect I'm trying to understand this simpler problem so I can apply the process to a more difficult homework problem.

Let $U$ be a set with $n$ elements. Select $2$ independent random subsets $A_1, A_2 \subset U.$ Both $A_i$ are chosen so that all $2^n$ choices are equally likely. I would like to compute the probability that $A_1, A_2$ are disjoint.

I am looking for a calculation based on counting. I have no idea how to compute this, and I would appreciate any help given.
 A: Take an element $i$. Let $p_i$ denote the probability that $i$ is not in the intersection of your two randomly chosen sets. It is in exactly $2^{n-1}$ subsets, hence the probability that it is in a randomly chosen subset is $\frac 12$.  It follows that the probability that it is in both of two randomly chosen subsets is $\frac 14$.  Therefore $p_i =\frac 34$.
Now, knowing that $i$ is in a subset tells you nothing about whether or not $j$ is (for $j≠i$)  Hence we have independence of the probabilities $p_i$ and $p_j$.  It follows that the probability that the sets are disjoint is $\left(\frac 34\right)^n$.
A: Assume that there are $k$ elements in $A_1$. There are $\binom{n}{k}$ ways of choosing such an $A_1$.
Now for a given $A_1$ count the number of admissible $A_2$. Well, $k$ elements must not belong to $A_2$, so the others can be chosen or not in $2^{n-k}$ ways.
Letting $k$ run from $0$ to $n$, we get the total number of possible combinations of $(A_1,A_2)$ that do not intersect as:
$$N=\sum_{k=0}^{n}{\binom{n}{k}2^{n-k}}=\sum_{k=0}^{n}{\binom{n}{k}2^{n-k}1^k}=3^n$$
by the binomial theorem.
Without regard to possible intersections, there are $2^n$ ways of choosing $A_1$ and $2^n$ ways of choosing $A_2$, so 
$$p=\frac{3^n}{2^n\cdot2^n}=\frac{3^n}{4^n}$$. 
A: Yet another way to think about it.
Each pair of subsets that do not intersect is uniquely described by a tuple of $n$ numbers: $-1$ if the elements with index $i$ is in the first subset, $1$ if it is in the second subset, and $0$ if it is outside of both subsets. 
There are $3^n$ such tuples. 
Also there are $4^n$ pairs of subsets in total.
So we get the same answer $(\frac34)^n$.
