0
$\begingroup$

Need to find the number of balanced parentheses sequences in the length of 200, starts with (((.

First, I defined '(' as 0 and ')' as 1.

Then I defined S to be the group of all balanced sequences, according to Catalan numbers, |S| = $\frac{1}{101}$$200\choose100$.

After that, I wanted to subtract all the sequences that does not fit.

The first type is those starts with 0,1,....

So we want all the balanced sequences in the lentgh of 198, that is $\frac{1}{100}$$198\choose99$.

Now the second type I can think of is the sequences starts with 0,0,1..... because we want to ensure that 0,0 doesn't followed by another 0.

And there I got stuck. It is impossible to create a balanced sequence in the length of 197 so I can't use the previous method.

Maybe I'm not approching the problem the right way?

By-the-way, the correct answer is $\frac{1}{101}$$200\choose100$ - $\frac{1}{50}$$198\choose99$, which I assume to be $\frac{1}{101}$$200\choose100$ - $\frac{1}{100}$$198\choose99$ - $\frac{1}{100}$$198\choose99$.

$\endgroup$

1 Answer 1

1
$\begingroup$

After the initial $001$ you must have a balanced sequence followed by a $1$ followed by another balanced sequence. The first balanced sequence can be of any length $2k$ such that $0\le k\le 98$, and the second balanced sequence will then have length $196-2k$. There are

$$\sum_{k=0}^{98}C_kC_{98-k}$$

such pairs of balanced sequences, and you can now apply the standard Catalan recurrence to finish the problem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .