How Many Sequences of n 1's and n 0's Avoid Equal Counts Before the End?

[Adeimantus]

I've been thinking about sequences of length 2n, with n 1's and n 0's. In particular, I'm interested in such sequences that also have the following property: reading the sequence from left to right, at no point before the end of the sequence is the number of 1's and 0's equal. For example, a sequence with n=4 satisfying this requirement is 00101011. A sequence with n=4 that does not satisfy the requirement would be something like 01100011, because there are equal numbers of 1's and 0's up to the second and fourth positions (reading from left to right). I wanted to figure out the number A_n of such sequences there are for a given n, and I was able to calculate the first few with this recurrence relation:

$$A_n = _{2n}C_n - \sum_{k=1}^{n-1} _{2n-2k}C_{n-k}A_k$$

where $$_{r}C_s$$ is the binomial coefficient 'r choose s'.

Starting with A_1 = 2, the pattern of A_n's continued 2, 4, 10, 28, 84, 264, etc. I didn't see a pattern in the numbers themselves, but eventually I thought about looking at the fraction of the total number of sequences of length 2n with n 1's and n 0's, and was surprised to see that


$$f_1 = \frac{A_1} { _{2} C_1} = 1$$

$$f_2 = \frac{A_2} { _{4} C_2} = 1/3$$

$$f_3 = \frac{A_3} { _{6} C_3} = 1/5$$

$$f_4 = \frac{A_4} { _{8} C_4} = 1/7$$
...
$$f_n = \frac{A_n}{_{2n} C_n} = 1/(2n-1)$$

So my first question is...is this somehow obvious? With such a simple result, there must be some way to just 'see' the answer. If not, how might I go about showing that last formula to be generally true? What led me to consider the fraction rather than the absolute number of sequences was using the inclusion-exclusion formula for probabilities of disjunctions of events and considering all sequences with n 1's and n 0's to be equally likely. But that method took much more work than the recurrence relation method, which is already a lot to do by hand. I ran into this problem while trying to analyze what roulette players call the 'D'Alembert' betting system. I doubt the mathematician is responsible for it, but whatever...it sounds impressive. The idea is that, on even payout bets, you raise the bet one unit after each loss, and lower it one unit after each win. Hopefully *fingers crossed*, you will have a sequence of n wins and n losses before running out of money or encountering the min and max bets. If you succeed in this you will have gained n units. And then you start over. In the roulette manual I looked at, the author explained that this is a winning strategy, but only if you use 'good judgment'. That is, you have to know when your luck is about to run out.

 

[Adeimantus]

Darn. Thought I had discovered something there for a while. I was only a couple hundred years too late

http://en.wikipedia.org/wiki/Catalan_numbers#History