I was trying to figure out the general formula for the number of distinct "paths"/ways a gambler could reach 0 wealth for the first time in exactly t steps, given that they start with wealth = 1, and at each step they gain +1 or -1 with 50/50 probability.
Here are a few simple cases as example (where we ignore even values of t, since there are clearly 0 paths):
t = 1: (-1) -> number of paths = 1
t = 3: (+1, -1, -1,) -> number of paths = 1
t = 5: (+1, +1, -1, -1, -1), (+1, -1, +1, -1, -1) -> number of paths = 2
I tried a number of approaches to find some general formula (mainly dynamic programming), but couldn't seem to find the proper solution. Then, after writing out the values of t and my manually calculated solutions for each (up to 11), I noticed a pattern.
Number of paths = ${t \choose t/2 + 1/2}/t$
That is, the number of paths equals the number of distinct orderings of the wins/losses divided by t. I tested this against a computer program and it seems to have held for a large variety of t values I tested, so I'm assuming this formula is correct.
However, I don't quite understand where exactly this formula is coming from. How would one construct this formula without simply guessing it from a pattern like I did?
You can recast this in terms of Bertrand's ballot theorem. Instead of saying that the gambler loses $k$ times and wins $k-1$ times, we consider an election where the winner gets $k$ votes and the loser $k-1$. By Bertrand's ballot theorem, the probability that the winner is always ahead, assuming the votes are counted in random order, is $$\frac1{2k-1}.$$ The number of possible orders is $$\binom{2k-1}{k}$$ so the number of possible paths is $$\frac1{2k-1}\binom{2k-1}{k}$$ which is the same as your result with $t=2k-1$.
The wiki article cited above actually mentions your problem.