# Counting Balanced Brackets with a twist

I have $n$ "1"s written as a sum: $1+1+1+\dots+1$, and proceed to add some brackets to the sum. Call the modified sum "good" if the brackets are balanced and not redundant*. [Since in fact placing any brackets is redundant, redundancy here is limited to brackets around a single "1", that is $(1)$ and more than one pair of brackets around the same sum, such as $((1+1))$.]

For example, if $n = 4$, then

$$(1+1)+(1+1)$$ $$(1+1+1)+1$$ $$(1+(1+1)+1)$$

are all good.

The full list (as far as I can see) of good sums for $n=4$ is

1+1+1+1, 1+1+(1+1), 1+(1+1+1), 1+(1+(1+1)), 1+((1+1)+1), (1+1+1)+1, (1+(1+1))+1, ((1+1)+1)+1, (1+1)+1+1, (1+1)+(1+1), and all those sums with an outermost pair of brackets added.

Edit: I missed out one of the good sums, namely 1+(1+1)+1.

How many good sums are there for each $n$?

My attempt at a solution is as follows. First, let a "spanning bracket pair" be a pair of open and close brackets that include the entire sum; for example $(1+1+1+1)$ contains a spanning bracket pair. Let $a_n$ and $b_n$ be respectively the number of sums for each $n$ with and without a spanning bracket pair respectively, and $c_n=a_n+b_n$. For convenience, we define $a_0=0, b_0=0$

For $n=1$, $a_1=0, b_1=1$, and for $n\geq 2$, $a_n=b_n$.

Edit: My initial recurrence relation was far more complicated than it had to be. The edited recurrence relation is as follows.

To set up a recurrence relation for $b_n$, we note that all good sums without a spanning bracket pair of length $n$ can be classified into exactly two types: those with an initial open bracket $($, and those without.

To count the number with an initial open bracket $($, we split each of the sums into two good sub-sums such that the first sum has a spanning bracket pair. For example, the sum (1+1)+1+(1+1) would be split into (1+1) and 1+(1+1). The number of sums with an initial open bracket is then just

$$a_2c_{n-2}+a_3c_{n-3}+a_4c{n_4}+\dots+a_{n-1}c_1=\sum_{i=2}^{n-1} a_ic_{n-i}$$

To count the number without an initial open bracket, we note that by removing the leading $1+$ term, we are simply left with a good sum of length $n-1$ (that may or may not have a spanning bracket pair). Thus, the number of such terms is simply

$$c_{n-1}$$

Thus, the required relation is just

$$b_n=c_{n-1}+\sum_{i=2}^{n-1} a_ic_{n-i}=\sum_{1=2}^{n-1} b_ic_{n-i}$$

Since $a_n=b_n$ for $n=2$, while $b_1=1$.

Calculating a few initial terms, I found that the values of $c_n$ were $1, 2, 6, 22, 90, 394, 1806, \dots$ and plugging this into OEIS as suggested, I found that this was just A006318, the large Schroeder numbers.

At the moment, though, I'm still trying to figure out how to produce the generating function for the large Schroeder numbers from this recurrence. For your reference,

$$f(x)=\frac{1-x-\sqrt{1-6x+x^2}}{2x}$$

is the generating function.

-
How do these numbers differ from the Catalan numbers? Also, you did not include all the possibilities for $n = 4$ – Tobias Kildetoft Mar 14 '13 at 14:24
@TobiasKildetoft yes, I did not include all as there are quite a number of possibilities. I was looking at the balanced-brackets interpretation of Catalan Numbers but I think they allow for brackets around a single term $(1)$ and double brackets that are redundant as I define it $((1+1))$. – Vincent Tjeng Mar 14 '13 at 14:26
If they did allow that, how could the number be finite? – Tobias Kildetoft Mar 14 '13 at 14:28
Sorry, what I really meant was that I'm not exactly sure how to map the bracket pairs counted by the Catalan Numbers bijectively to my situation. – Vincent Tjeng Mar 14 '13 at 14:30
Did you try to compute some terms and have a look at OEIS ? – Jean-Claude Arbaut Mar 14 '13 at 14:37

Let $$a_n'=a_{n+1}, b_n'=b_{n+1}, c_n'=c_{n+1}, a_0'=0, b_0'=c_0'=1$$ $$g(x)=\sum_{n=0}^{\infty}{a_n'x^n}, h(x)=\sum_{n=0}^{\infty}{b_n'x^n}, f(x)=\sum_{n=0}^{\infty}{c_n'x^n}=g(x)+h(x)$$ We have $g(0)=0, h(0)=1, g(x)+1=h(x)$ so $f(x)=2h(x)-1$.

Thus your recurrence gives $$b_{n+1}'=b_{n+2}=\sum_{i=1}^{n+1}{b_ic_{n+2-i}}=\sum_{i=0}^{n}{b_{i+1}c_{n+1-i}}=\sum_{i=0}^{n}{b_i'c_{n-i}'}$$

Thus $\frac{h(x)-h(0)}{x}=h(x)f(x)=h(x)(2h(x)-1)$.

$$2xh(x)^2-(x+1)h(x)+1=0$$

Solving the quadratic, $$h(x)=\frac{x+1 \pm \sqrt{1-6x+x^2}}{4x}$$

We are almost done.

Rewrite as $4xh(x)=x+1 \pm \sqrt{1-6x+x^2}$ and differentiate to get

$$4h(x)+4xh'(x)=1 \pm \frac{2x-6}{2\sqrt{1-6x+x^2}}$$

Substitute in $x=0$ and use $h(0)=1$ to get $4=1 \pm (-3)$, so we take the negative sign.

Finally, $$f(x)=2h(x)-1=\frac{1-x-\sqrt{1-6x+x^2}}{2x}$$

P.S. Note that this isn't exactly the generating function for $c_n$. There is an offset, and it is the generating function for $c_n'=c_{n+1}$.

-
Is it correct to say that we differentiate only to determine whether we are to take the negative or the positive sign? Also, is the central idea of the solution to express the generating function for $c_n$ as some function of $b_n$? – Vincent Tjeng Mar 20 '13 at 6:33
Yes I differentiated only to determine the sign. Well, you already know $a_n=b_n$ for $n \geq 2$, so clearly the generating function for $c_n$ can be expressed in terms of $b_n$ easily. You could have done it all in terms of $f(x)$ instead of $h(x)$, but that would have more fractions, so I decided not to. – Ivan Loh Mar 20 '13 at 6:40