The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
963 views
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.$
asked in Combinatory by Veteran (59.6k points)
retagged by | 963 views
0
sir , am not getting question... one side ,says no of 0 and 1 are equal then w and prefix ..not getting
+1
it was a typo- the property must hold in every prefix of string- "100" is not allowed as for the prefix "1" the property is violated.
0
Sir...what is meaning of "every prefix of w...."

1 Answer

+21 votes
Best answer

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 5th proof here http://en.wikipedia.org/wiki/Catalan_number

answered by Veteran (363k points)
edited by
+1
00011,000011 these are not valid string @srestha as they don't satisfy the string property for the equal number of 0's & 1's. "at least as many as 0's as 1's" property is for prefixes of the obtained string.
0

bhuv so the question requirement is 

1) even length string
2) equal number of 0's and 1's
3) balanced parenthesis 0 is ( and 1 is )

am i right?

+1
@Mk Utkarsh

first two conditions are on string 'w' and
"at least as many as 0's as 1's" property is for prefixes of the obtained string 'w'.

w=0011
a)even in length
b)equal no. of 0's and 1's
c) checking prefixes of 0011
    {},{0},{00},{001},{0011}
All prefixes contain at least as many 0's as 1's.

w=0011 is a valid string.
0
@bhuv

i'm  not getting this line

please explain

All prefixes contain at least as many 0's as 1's.

{0011} this is valid why??
0
0011 is valid because {},{0},{00},{001},{0011} in all these prefixes number of 0's $\geq$ number of 1's
0
1100 is not valid because there exist prefixes like {11},{110},{1} which violate the condition mentioned
0
at least means(Kam se kam  one 0 more than 1 right) but 0011 violated the condition??
0
it simply means every prefix should follow this condition $\left | 0's \right | \geq \left | 1's \right |$
0
Yes utkarsh sir is right...0011 is valid string...here prefix can be 0,00,001 and in every prefixes here...we have atleast as many 0's as 1's...i.e #0's>=#1's
0
$S->0S1|SS|\epsilon$

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,599 questions
48,598 answers
155,653 comments
63,719 users