Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A(k)$ be the number of distinct binary strings of length $2k+1,$ for which the number of $1$s surpasses the number of $0$s for the first time at digit number $2k +1$, i.e., in the final digit in the string. (We'll call a binary string with such a property admissible.)

For example: $A(0) = 1$, because the only admissible string is $1.$

Similarly, $A(1) = 1$, because the only admissible string is $011.$

$A(2) = 2,$ because $00111$ and $01011$ are all the admissible strings.

Note that $A(3)$ is at least $5$, since $0001111, 0010111, 0011011, 0100111$ and $0101011$ are among the admissible strings. (Which is to say, this is not the Fibonacci sequence.)

What is a closed formula for $A(k)$? Alternatively, can anyone code up a program that calculates $A(k)$ for small values of $k$?

Thanks!

share|improve this question
1  
The count is given by the Catalan numbers. –  André Nicolas Jul 27 '12 at 6:33
    
I can see that the Catalan numbers are the first result on OEIS when I plug in 1, 1, 2, 5.... but how do you know? –  B D Jul 27 '12 at 6:35
    
In the article I cited, there is a partial derivation from a recurrence. You should be able to see that the recurrence applies in your case. How did I know? It is one of the most standard things that the Catalan numbers count. They show up in a ridiculously large number of counting problems. You will find a proof, or someone will write it up. If not, I will do it next morning. –  André Nicolas Jul 27 '12 at 6:44
    
Didn't realize that was a link! Thanks! –  B D Jul 27 '12 at 6:47
    
This also goes by the name of "the ballot problem", where you count the number of ways one candidate can be ahead or tied every step of the way in an election that ends in a tie. –  Gerry Myerson Jul 27 '12 at 12:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.