retagged by
6,337 views
52 votes
52 votes
Find the number of binary strings $w$ of length $2n$ with an equal number of $1's$ and $0's$ and the property that every prefix of $w$ has at least as many $0's$ as $1's.$
retagged by

2 Answers

Best answer
37 votes
37 votes

Answer to a is $\frac{^{2n}C_n}{(n+1)}$ which is the Catalan number. 

This is also equal to the number of possible combinations of balanced parenthesizes. 

See the $5^{\text{th}}$ proof here https://en.wikipedia.org/wiki/Catalan_number#Fifth_proof

edited by
5 votes
5 votes
  • Cn is the number of Dyck words[3] of length 2n. A Dyck word is a string consisting of nX's and n Y's such that no initial segment of the string has more Y's than X's. For example, the following are the Dyck words of length 6:

XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

  • Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, Cncounts the number of expressions containing n pairs of parentheses which are correctly matched:

((()))     ()(())     ()()()     (())()     (()()) 

  • Cn is the number of different ways n + 1 factors can be completely parenthesized (or the number of ways of associating napplications of a binary operator). For n = 3, for example, we have the following five different parenthesizations of four factors:

((ab)c)d     (a(bc))d     (ab)(cd)     a((bc)d)     a(b(cd))

source :- https://en.m.wikipedia.org/wiki/Catalan_number

Related questions

20 votes
20 votes
2 answers
1
43 votes
43 votes
4 answers
2
Kathleen asked Sep 12, 2014
4,894 views
Match the pairs in the following questions by writing the corresponding letters only.$$\begin{array}{|c|l|c|l|} \hline A. & \text{The number of distinct binary tree} & P....