Enumerative Combinatorics Sam has $255$ cakes, each labeled with a unique non-empty subset of $\{1, 2, 3, 4, 5, 6, 7, 8\}$. Each day, he chooses one cake uniformly at random out of the cakes not yet eaten. Then, he eats that cake, and all remaining cakes that are labeled with a subset of that cake (for example, if he chooses the cake labeled with $\{1, 2\}$, he eats that cake as well as the cakes with $\{1\}$ and $\{2\}$). The expected number of days that Sam eats a cake before all cakes are gone can be expressed in the form ${p\over q}$, where $p$ and $q$ are relatively prime natural numbers. Find $p+q$.
 A: Fix $n>1$. Let $S=\{1,\ldots,n\}$.  In the end, we will set $n=8$ to solve the problem.
Let $\{X_i\}_{i\ge 1}$ be the sequence of random sets as described in the problem. $\{X_i\}$ is a random sequence with random finite length. Let $N$ be the number of days on which cake is eaten, i.e., the length of this sequence.
We will construct a different random sequence of sets $\{X'_i\}_{i\ge 1}$ that is equivalent to $\{X_i\}_{i\ge 1}$, but that is much easier to analyze.
Let $\{X'_i\}_{i\ge 1}$ be an i.i.d. sequence of random sets in which $X'_i$ is chosen uniformly from $2^S$, the power set of $S$ (null set included).  Define $I_i$ as follows:
\begin{eqnarray}
I_1 &=& \begin{cases} 1\text{ if } X'_1 \ne \emptyset\\
0 \text{ otherwise} \end{cases}\\
I_i &=& \begin{cases}1\text{ if } X'_i \not \subset X'_{j} \mbox{ for all } j<i \\
0 \text{  otherwise}.
\end{cases}
\end{eqnarray}
Let $M_i$ be the $i^{\text{th}}$ smallest index $j$ such that $I_j=1$. For example, if $I_1=I_2=I_4=I_6=0$ and $I_3=I_5=1$, then $M_1=3$ and $M_2=5$. Then the random sequence $\{X'_{M_i}\}$ has exactly the same probability distribution as $\{X_i\}$. 
Intuitively, $\{X'_i\}$ generates $\{X_i\}$ by repeatedly sampling $2^S$ until the next element of $X_i$ is found. At each step, if the generated $X'_i$ is a subset of some previous $X'_j$, $j<i$, then $X'_i$ is essentially ignored. This is reflected in setting $I_i=0$. Each time a new set $X'_i$ is generated with $I_i=1$, the next element of the sequence $X_j$ is generated.
Let
$$
N' = \sum_{i=1}^{\infty} I_i.
$$
Observe that, by the argument above, $N'$ has precisely the same distribution as $N$.
We will calculate $\mathbb{E}(N')$. By definition, we see
$$
\mathbb{E}(I_i) = \mathbb{P}(I_i=1).
$$
Thus,
$$
\mathbb{E}(I_1) = 1 - 2^{-n}.
$$
For $i>1$, we may condition on the size $s$ of $X'_i$ and use the facts that $X'_i$ are i.i.d. and that a subset of $S$ with $s$ elements has $2^{n-s}$ supersets in $S$, and so
$$
\mathbb{P}(X'_i\not \subset X'_j|X'_i\mbox{ has $s$ elements}) = 1 - 2^{-s} \ \mbox{ if $i\ne j$}.
$$
We have
\begin{eqnarray}
\mathbb{P}(X'_i\not\subset X'_j \mbox{ for all }j<i) &=& \sum_{s=0}^n 2^{-n} \left(\begin{array}{c}n\\s\end{array}\right) (1-2^{-s})^{i-1}.
\end{eqnarray}
Thus,
\begin{eqnarray}
\mathbb{E}(N) &=& \sum_{n=1}^{\infty} \mathbb{E}(I_i) \\
&=& 1 - 2^{-n} + \sum_{i=2}^{\infty} \sum_{s=0}^n 2^{-n} \left(\begin{array}{c}n\\s\end{array}\right) (1-2^{-s})^{i-1} \\
&=& 1 - 2^{-n} + \sum_{s=0}^n \sum_{i=2}^{\infty} 2^{-n} \left(\begin{array}{c}n\\s\end{array}\right) (1-2^{-s})^{i-1} \\
&=& 1 - 2^{-n} + \sum_{s=0}^n 2^{-n} \left(\begin{array}{c}n\\s\end{array}\right) (2^s - 1) \\
&=& \frac{3^n - 1}{2^n}.
\end{eqnarray}
For $n=8$, this reduces to
$$
\mathbb{E}(N) = \frac{205}{8} = 25.625.
$$
