I assume that the probability to choose a bucket is uniformly distributed. Then, to compute entropy, you enumerate (in your mind) all possible outcomes and count the resulting sequences. Some sequences will appear more than once, see below. These counts are plugged into the calculation of the entropy.
In your experiment, the crucial point is the number of 'steps back' in the resulting sequence. A 'step back' must come with a bucket change by design of your experiment. In your example, be|acf|d
. there are two of those 'steps back', marked by |
. Such an outcome is possible only with the given distribution of the letters into the buckets. As @ShreevatsaR pointed out, f|e|d|c|b|a
is not possible at all. Why? Because the number of 'steps back' (5) is larger than the number of buckets, as a 'step back' can occur only when switching to the next bucket. In contrast, the sequence bef|acd
appears much more often: We'd have to insert one imaginary 'step back' that is not taken but corresponds to a bucket change. We can choose among $(3 + 1) + ((3 + 1) - 1) = 7$ positions (inserting after f
and before a
is equivalent), and this number does not depend on the position of the real 'step back'. For the sequence abcdef
, we have $\sum_{i=1}^7 i = \frac{7\cdot8}{2} = 28$ options to insert two |
.
What remains is the calculation of the number of sequences with zero, one or two 'steps back'. Obviously, there is only one sequence with zero 'steps back'. For one step back, it is the number of partitions of a six-element set excluding those that would lead to a sorted sequence: $2^6 - 7 = 57$. For two steps back, this gets more complicated if you try to solve it directly this way. However, a solution can be obtained by recurring over the sample size $n$.
Let $B_i^n$ be the number of sequences of length $n$ with $i$ steps back. $B_0^n = 1$, and $B_n^n = 0$ for all $n$. We try to derive $B_i^n$ from $B_i^{n-1}$ and $B_{i-1}^{n-1}$. There are two ways to obtain a sequence of length $n$ with $i$ steps back: Adding the $n$-th element to a sequence with $i$ steps back 'in order', or adding it to a sequence with $i-1$ steps back 'out of order'. Using this experiment, for each sequence there is only one possible way to construct it, so uniformity is maintained.
In a sequence of length $n-1$ with exactly $i$ steps back, we have exactly $i+1$ positions where we don't add a step back by placing the $n$-th element: After each existing step back, and at the end. For $i-1$ steps back, this is $i$, and leaves $n-i$ choices to place the $n$-th element so that one more step back is added. That is, $B_{i}^{n} = (i+1) \cdot B_{i}^{n-1} + (n-i)\cdot B_{i-1}^{n-1}.$
We compute $B_1^6$:
$ B_1^6 = 2 \cdot B_1^5 + 5 \cdot B_0^5 = 2 \cdot 2 \cdot B_1^4 + 2 \cdot 4 \cdot B_0^4+5 = 8 \cdot B_1^3 + 12 \cdot B_3^0 + 13 $ $ = 16 \cdot B_1^2 + 16 \cdot B_0^5 + 25 = 32 \cdot B_1^1 + 16 \cdot B_0^1 + 41 = 57. $
There are $B_2^6=302$ different sequences with two steps back.
From this, you should be able to compute the entropy. Please notify me if something needs clarification.