Suppose we have a game with probability for winning and for losing are $\frac{1}{2}$. We use Labouchère system with starting numbers $(1,2,3,4)$.
Note: this system goes like this: if win - wipe out first and last number of sequence you have. If lose - add the sum of first and last number in the sequence to the end of the sequence.
And the question is:
if we played $n$ times, how many possible sequences of W\L (Win\Lose) are they given that the number of plays was $n$?
I have no idea how to approach it directly so I started counting for some small $n$ to find any relation or formula for them.
- Firstly, $n=1$.
It is clearly impossible, we need at least $2$ plays to end the Labouchère system.
- $n=2$
Now if we ended in exactly two plays, it means we won both times, so the only possible sequence is $(WW).$
- $n=3$
Again impossible.
- $n=4$
$$(WLWW), (LWWW) $$
- $n=5$
Here we have some more possibilities $$(WLLWW), (WLWLW), (LWWLW), (LWLWW), (LLWWW) $$
- $n=6$
Again, nothing for $n=6$.
- $n=7$
EDIT: As @RossMillikan pointed I've missed some sequences in this case: $$(WLWLLWW), (LWWLLWW), (WLLWLWW), (LWLWLWW), (LLLWWWW),(LLWWLWW), (LLWLWWW), (LWLLWWW), (WLLLWWW) $$
And so on...
So what we can conclude for now, we need to find function $f$, such that $f:\mathbb{N}\to \mathbb{N_0}$ and: $f(1)=0,$ $f(2)=1,$ $f(3)=0,$ $f(4)=2,$ $f(5)=5,$ $f(6)=0,$ $f(7)=9...$ Then we see that $$(\forall k \in \mathbb{N}) \quad f(3k)=0.$$
And more for sequences: for any $m$ such that $n>m$ there can't be a sequence for $n$ such that starts with any sequence which already appear in the $m$ case.
For $n=3k+1$ we must have $k+2$ wins and $2k-1$ losses. For $n=3k+2$ we must have $k+2$ wins and $2k$ losses. As you say, we can accept any ordering of wins and losses that does not have a prefix of a shorter acceptable list. We can define $X(k)$ as the number of acceptable strings of length $3k+1$ and $Y(k)$ as the number of acceptable strings of length $3k+2$. We can write a recursive computation for these. We start with all strings with the right number of wins and losses, then subtract off the ones that start with a shorter string. For example, with $k=2$ and computing $X(2)$ we start with ${7 \choose 3}=35$ strings that have four wins and three losses. The string $WW$ that represents $Y(0)$ can be extended to our target composition in ${5 \choose 3}=10$ ways because we add two wins and three losses. Each of the two strings that represents $X(1)$ can be extended in three ways because we have to add two losses and a win, so we lose six strings. Each of the five strings that represents $Y(1)$ can be extended in two ways because we have to add one win and one loss, so we subtract $10$. That leaves us with $X(2)=35-10-6-10=9$ strings. The base case is $X(0)=0,Y(0)=1$, then the recurrences are $$X(k)={3k+1 \choose k+2}-\sum_{j=0}^{k-1}X(j){3(k-j) \choose k-j}-\sum_{j=0}^{k-1}Y(j){3(k-j)-1 \choose k-j}\\ Y(k)={3k+2 \choose k+2}-\sum_{j=0}^kX(j){3(k-j)+1 \choose k-j}-\sum_{j=0}^{k-1}Y(j){3(k-j) \choose k-j}$$ I implemented this in Python and find
$$\begin {array} {r r r r r}k&n&X(k)&n&Y(k)\\1&4&2&5&5\\2&7&9&8&23\\3&10&43&11&113\\4&13&218&14&585\\5&16&1155&17&3148\\6&19&6324&20&17442\\7&22&35511&23&98857\\8&25&203412&26&570515\\9&28&1184040&29&3341325\\10&31&6983925&32&19809465\\11&34&41652468&35&118657212\\12&37&250763464&38&717017228\\13&40&1521935948&41&4365748104\\14&43&9301989144&44&26758408510\\15&46&57203999295&47&1.64964E+11\\16&49&3.53702E+11&50&1.02225E+12\\17&52&2.1976E+12&53&6.36394E+12\\18&55&1.37133E+13&56&3.97823E+13\\19&58&8.59072E+13&59&2.49618E+14\\20&61&5.40072E+14&62&1.57156E+15 \end {array}$$ I didn't find these in OEIS