The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+29 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.$
asked in Combinatory by Veteran (59.8k points)
retagged by | 1.2k views
sir , am not getting question... one side ,says no of 0 and 1 are equal then w and prefix ..not getting
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.
Sir...what is meaning of "every prefix of w...."
There are $2n$ positions out of which we need to select only n for $0's$ which makes it $2nCn$. But  why we are dividing it with $n+1$ that part is not clear and how do we know, how many strings are there in $2nCn$ which needs to be remove from counted strings.

Just thinking this problem in the terms of TOC

Is it possible to construct DFA for this or find a regular expression for it. As i have read one similar problem in TOC which has same wording for $\text{at least as many 0's as 1's }$.

1 Answer

+22 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

answered by Veteran (396k points)
edited by

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?

@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'.

a)even in length
b)equal no. of 0's and 1's
c) checking prefixes of 0011
All prefixes contain at least as many 0's as 1's.

w=0011 is a valid string.

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??
0011 is valid because {},{0},{00},{001},{0011} in all these prefixes number of 0's $\geq$ number of 1's
1100 is not valid because there exist prefixes like {11},{110},{1} which violate the condition mentioned

at least means$($Kam se kam  $0$ more than $1$ right$)$ but $0011$ violated the condition$?$

it simply means every prefix should follow this condition $\left | 0's \right | \geq \left | 1's \right |$
Yes utkarsh sir is right...0011 is valid 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

@Praveen Saini sir it means when n =1 we have 01 and for n=2 it's 0011 ,0101 for n=3 it's 000111,010101,001101,010011,001001? Sir please check if all strings are valid?


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
50,126 questions
53,252 answers
70,502 users