The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

I have a question regarding Catalan Number. The question is as follows,

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 as 0’s as 1’s.

Now i know the answer for this question is 2nCn/(n+1). I wanted to know how this question relates to Catalan number?

in Combinatory by (103 points) | 68 views

Check this if it helps -
Just replace open parenthesis or right steps with $0's$ and closed parenthesis or left steps with $1's$ in the given answer.

Hello Thank you for commenting......I know this interpretation of lattice paths, But my question is how is this generalization can be used for this question?

To find the ways without touching the diagonal is = 2nCn - 2nCn-1 where 2nCn-1 is the violating paths right??

so to find the answer for the sequence question we have to take all the length 2n strings with an equal number of 1’s and 0’s which is = 2nCn. But the answer is = 2nCn - 2nCn-1. we know for the lattice path problem that (2nCn-1) is the no of violating paths. but what is this (2nCn-1) for this particular question??
Here $\binom{2n}{n-1}$ includes those strings which have more no. of $1's$ than $0's$ in any of their prefix.
For ex. - 111000, 100110 etc.

Please log in or register to answer this question.

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
49,781 questions
53,593 answers
70,880 users