I'm working on project Euler 151 which goes as follows:
A printing shop runs 16 batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A5.
Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.
He proceeds to cut it in half, thus getting two sheets of size A2. Then he cuts one of them in half to get two sheets of size A3 and so on until he obtains the A5-size sheet needed for the first batch of the week.
All the unused sheets are placed back in the envelope.
At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random. If it is of size A5, he uses it. If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.
Excluding the first and last batch of the week, find the expected number of times (during each week) that the foreman finds a single sheet of paper in the envelope.
Give your answer rounded to six decimal places using the format x.xxxxxx .
Now I know that Project Euler is old and there are answers readily available, but I'm not so much interested in the correct answer or how to find it, but rather in determining why my solution is incorrect.
Here was my reasoning: first of all the structure here is highly recursive, as is especially apparent when you consider the sheets as rooted trees, and the envelope as a forest. For convenience later on I reverse the labeling of sizes, considering A5 to be size $0$ and A1 to be size 4. Note that size in this case doesn't refer to the number of vertices, rather, a tree of size $n$ will have $2^n$ vertices. A tree of size $n>0$ will then consist of a root vertex connected to to the roots of $n$ smaller trees, one tree of size $k$ for every $k<n$. The process now involves removing the root from one of the trees in the forest, and our task is to determine the expected number of times (other than the first and last step) that the remaining forest consists of a single tree. If each vertex is considered unique based on it's position in the starting tree, let $a_n$ be the total number of ways the vertices can be removed if your starting tree is size $n$. Obviously $a_0=1$, and a stars-and-bars argument using the symmetry of the problem shows that it follows the recurrence $$a_{n+1}={a_n}^2{{2^{n+1}-1} \choose {2^n}}$$ Furthermore, for any $k<n$ a tree of size $n$ can be considered to be a tree of size $n-k$ whose vertices are all trees of size $k$, which gives rise to the more general recurrence $$a_n={2^n}!{a_{n-k} \over {2^{n-k}}!}\left(a_k \over 2^k!\right)^{2^{n-k}}$$
Now let $b_{n,k}$ be the number of ways to remove the vertices from an initial tree of size $n$ such that at some point your forest consists of a single tree of size $k$. Note that this can only happen once for any given $k$, so the expected value we are looking for is simply $$ \left(b_{4,1}+b_{4,2}+b_{4,3}\right)\over a_4$$
Now, the number of $k$-size subtrees in an $n$-size tree is $2^{n-k-1}$ and the number ways of removing its vertices are of course $a_k$. The remaining vertices form a tree of size $n-k-1$, one of whose vertices is a tree of size $k$, and the rest are trees of size $k+1$, so the number of ways to remove these vertices is $$\left(2^n-2^k\right)!{{a_{n-k-1}}\over 2^{n-k-1}!}{a_k \over 2^k!}\left({a_{k+1}\over2^{k+1}!}\right)^{2^{n-k-1}-1}$$Thus, for $0<k<n$, $$b_{n,k}={2^{n-k-1}}{a_k}{\left(2^n-2^k\right)!}{{{a_{n-k-1}}\over 2^{n-k-1}!}{a_k \over 2^k!}\left({a_{k+1}\over2^{k+1}!}\right)^{2^{n-k-1}-1}}$$$$={2^{n-k-1}}{a_k}{\left(2^n-2^k\right)!}{a_n \over {2^n!}}{{a_k} \over {a_{k+1}}}{2^{k+1}!\over2^k!} $$$$={{a_k}^2\over a_{k+1}}{2^{n-k-1}}{a_n{2^{k+1}!}{\left(2^n-2^k\right)!} \over {{2^n!}2^k!}}$$$$={{2^{n-k-1}}\over {{2^{k+1}-1}\choose 2^k}}{a_n{2^{k+1}!}{\left(2^n-2^k\right)!} \over {{2^n!}2^k!}}$$$$={{2^{n-k}}\over {{2^{k+1}}\choose 2^k}}{a_n{2^{k+1}!}{\left(2^n-2^k\right)!} \over {{2^n!}2^k!}}$$$$={2^{n-k}}{{a_n{2^k!}}{\left(2^n-2^k\right)!} \over {2^n!}}$$$$={{2^{n-k}{a_n}}\over{2^n \choose 2^k}}$$So our expected value should just be $${ \left(b_{4,1}+b_{4,2}+b_{4,3}\right)\over a_4}={2^3\over{2^4 \choose 2^1}}+{2^2\over{2^4 \choose 2^2}}+{2^1\over{2^4 \choose 2^3}}$$$$={8\over{16 \choose 2}}+{4\over{16 \choose 4}}+{2\over{16 \choose 8}}={1\over 15}+{1\over {5\times7\times13}}+{1\over{3\times11\times13\times15}}$$$$\approx 0.0690198690...$$ However, this is not accepted with standard rounding (to $0.069020$) or truncation (to $0.069019$). What am I doing wrong?
Based on the clarifications in the comments, $a_n$ is the number of ways to choose the sequence of sheets drawn from the envelope, assuming that the sheets are distinguishable (even if the same size). For example, $a_2=3$ counts the following 3 possibilities:
However, these outcomes need not have equal probabilities. In this case outcome 1 has probability $\frac12$, while outcomes 2 and 3 each have probability $\frac14$. So we can't compute the expectation by counting outcomes and dividing by $a_n$.