Selecting r pairwise disjoint subsets from a set of n elements

Question

The question I have is as follows:

Assume that you have an $n$–element set $U$ and that you select $r$ independent random subsets $A_1, . . . , A_r ⊂ U$. All $A_i$ are chosen so that all $2^n$ choices are equally likely. Compute (in a simple closed form) the probability that the $A_i$ are pairwise disjoint.

My attempt:

My first thought was to use Stirling numbers of the second kind. However, the question doesn't say that the union of all subsets should be the entire set, so that doesn't work.

Next I tried to do via counting. We have to choose $r$ subsets from a total of $2^n$ subsets. For the sample space, we have that each one of the $r$ positions has $n$ choices. So, we have a total of $2^{nr}$ choices.

For the numerator, I attempted this: From the $2^n$ subsets, choose one. This can be done in $2^n \choose 1$ way, and then the second in $2^n-1 \choose 1$ and so on till we select $r$ subsets. However, I realised that not all of the subsets in this will be pairwise disjoint and I'll be over-counting.(we can select {1,2} in the first choice, {2,3} in the second choice).

So, I am stuck here.

I do have the solution, which gives the solution in terms of choosing a $r \times n$ matrix with $0$ or $1$ filled independently with probability $1/2$ and which has at most one $1$ in every column, which I am unable to understand.

Can someone help?

Answer 1

You want to count the $r$-tuples of subsets $(A_1,\ldots,A_r)$ of $U$ with the $A_i$ disjoint. Think of these $A_i$ as boxes in which you can throw the elements of $U$.

Let $u\in U$. Then you can throw $u$ into one of the $A_i$, or keep it and not throw it into any of the boxes. So you have $r+1$ options for $u$. As $U$ has $n$ elements, you have $(r+1)^n$ options overall.