1
$\begingroup$

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!

  • 0
    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.2012-07-27

0 Answers 0