Find the number of binary strings of length 2n with an equal number of 0s and 1s, and the property that every prefix of the string has at least as many 0s as 1s.

GATE 1991 · Discrete Mathematics · Combinatorics · medium

Answer: The number of valid binary strings is C_n = C(2n, n) / (n+1), the n-th Catalan number.

1. Model as a lattice path: Map each 0 to a +1 step and each 1 to a -1 step. The condition 'every prefix has >= as many 0s as 1s' means the path never goes below y=0. We need lattice paths from (0,0) to (2n,0) that stay >= 0.
2. Apply the reflection principle to count valid paths: Total paths with n ups and n downs = C(2n,n). Subtract invalid paths (those that go below 0) using the reflection principle: invalid count = C(2n, n-1). Valid = C(2n,n) - C(2n,n-1) = C(2n,n)*(1 - n/(n+1)) = C(2n,n)/(n+1) = C_n.