Counting Balanced Brackets with a twist

916 Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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}$.