All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Counting brackets (Posted on 2017-01-03)
In how many ways can one insert n pairs of parentheses in a word of n+1 letters?

Not allowed: empty parentheses, such as a()b, or redundant parentheses such as in a((b))c.

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer exploration and solution Comment 1 of 1
The left column below shows the numbers required when redundant parentheses are not allowed. Both columns represent empty parentheses not being allowed.

redundant parentheses
not allowed          allowed
n number of ways   n number of ways
1 3                1 3
2 14               2 20
3 70               3 175
4 363              4 1764
5 1925             5 19404
6 10364            6 226512
7 56412            7 2760615

With redundant parentheses not allowed, as per the puzzle, the following are the ways spelled out, with x's representing whatever letters are present, for the first four n:

1
x(x)
(xx)
(x)x 3
2
x(x(x))
x(x)(x)
x((x)x)
(xx(x))
(xx)(x)
(x(xx))
(x(x)x)
(x(x))x
(x)x(x)
(x)(xx)
(x)(x)x
((xx)x)
((x)xx)
((x)x)x 14
3
x(x(x(x)))
x(x(x)(x))
x(x(x))(x)
x(x((x)x))
x(x)(x(x))
x(x)(x)(x)
x(x)((x)x)
x((x(x))x)
x((x)x)(x)
x((x)(x)x)
x(((x)x)x)
(xx(x(x)))
(xx(x)(x))
(xx(x))(x)
(xx((x)x))
(xx)(x(x))
(xx)(x)(x)
(xx)((x)x)
(x(xx(x)))
(x(xx)(x))
(x(xx))(x)
(x(x(xx)))
(x(x(x)x))
(x(x(x))x)
(x(x(x)))x
(x(x)x(x))
(x(x)x)(x)
(x(x)(xx))
(x(x)(x)x)
(x(x)(x))x
(x(x))x(x)
(x(x))(xx)
(x(x))(x)x
(x((xx)x))
(x((x)xx))
(x((x)x)x)
(x((x)x))x
(x)x(x(x))
(x)x(x)(x)
(x)x((x)x)
(x)(xx(x))
(x)(xx)(x)
(x)(x(xx))
(x)(x(x)x)
(x)(x(x))x
(x)(x)x(x)
(x)(x)(xx)
(x)(x)(x)x
(x)((xx)x)
(x)((x)xx)
(x)((x)x)x
((xx(x))x)
((xx)x)(x)
((xx)(x)x)
((x(xx))x)
((x(x)x)x)
((x(x))xx)
((x(x))x)x
((x)xx)(x)
((x)x(x)x)
((x)x)x(x)
((x)x)(xx)
((x)x)(x)x
((x)(xx)x)
((x)(x)xx)
((x)(x)x)x
(((xx)x)x)
(((x)xx)x)
(((x)x)xx)
(((x)x)x)x 70
4
x(x(x(x(x))))
x(x(x(x)(x)))
x(x(x(x))(x))
x(x(x(x)))(x)
x(x(x((x)x)))
x(x(x)(x(x)))
x(x(x)(x)(x))
x(x(x)(x))(x)
x(x(x)((x)x))
x(x(x))(x(x))
x(x(x))(x)(x)
x(x(x))((x)x)
x(x((x(x))x))
x(x((x)x)(x))
x(x((x)x))(x)
x(x((x)(x)x))
x(x(((x)x)x))
x(x)(x(x(x)))
x(x)(x(x)(x))
x(x)(x(x))(x)
x(x)(x((x)x))
x(x)(x)(x(x))
x(x)(x)(x)(x)
x(x)(x)((x)x)
x(x)((x(x))x)
x(x)((x)x)(x)
x(x)((x)(x)x)
x(x)(((x)x)x)
x((x(x(x)))x)
x((x(x)(x))x)
x((x(x))x)(x)
x((x(x))(x)x)
x((x((x)x))x)
x((x)x)(x(x))
x((x)x)(x)(x)
x((x)x)((x)x)
x((x)(x(x))x)
x((x)(x)x)(x)
x((x)(x)(x)x)
x((x)((x)x)x)
x(((x(x))x)x)
x(((x)x)x)(x)
x(((x)x)(x)x)
x(((x)(x)x)x)
x((((x)x)x)x)
(xx(x(x(x))))
(xx(x(x)(x)))
(xx(x(x))(x))
(xx(x(x)))(x)
(xx(x((x)x)))
(xx(x)(x(x)))
(xx(x)(x)(x))
(xx(x)(x))(x)
(xx(x)((x)x))
(xx(x))(x(x))
(xx(x))(x)(x)
(xx(x))((x)x)
(xx((x(x))x))
(xx((x)x)(x))
(xx((x)x))(x)
(xx((x)(x)x))
(xx(((x)x)x))
(xx)(x(x(x)))
(xx)(x(x)(x))
(xx)(x(x))(x)
(xx)(x((x)x))
(xx)(x)(x(x))
(xx)(x)(x)(x)
(xx)(x)((x)x)
(xx)((x(x))x)
(xx)((x)x)(x)
(xx)((x)(x)x)
(xx)(((x)x)x)
(x(xx(x(x))))
(x(xx(x)(x)))
(x(xx(x))(x))
(x(xx(x)))(x)
(x(xx((x)x)))
(x(xx)(x(x)))
(x(xx)(x)(x))
(x(xx)(x))(x)
(x(xx)((x)x))
(x(xx))(x(x))
(x(xx))(x)(x)
(x(xx))((x)x)
(x(x(xx(x))))
(x(x(xx)(x)))
(x(x(xx))(x))
(x(x(xx)))(x)
(x(x(x(xx))))
(x(x(x(x)x)))
(x(x(x(x))x))
(x(x(x(x)))x)
(x(x(x(x))))x
(x(x(x)x(x)))
(x(x(x)x)(x))
(x(x(x)x))(x)
(x(x(x)(xx)))
(x(x(x)(x)x))
(x(x(x)(x))x)
(x(x(x)(x)))x
(x(x(x))x(x))
(x(x(x))x)(x)
(x(x(x))(xx))
(x(x(x))(x)x)
(x(x(x))(x))x
(x(x(x)))x(x)
(x(x(x)))(xx)
(x(x(x)))(x)x
(x(x((xx)x)))
(x(x((x)xx)))
(x(x((x)x)x))
(x(x((x)x))x)
(x(x((x)x)))x
(x(x)x(x(x)))
(x(x)x(x)(x))
(x(x)x(x))(x)
(x(x)x((x)x))
(x(x)x)(x(x))
(x(x)x)(x)(x)
(x(x)x)((x)x)
(x(x)(xx(x)))
(x(x)(xx)(x))
(x(x)(xx))(x)
(x(x)(x(xx)))
(x(x)(x(x)x))
(x(x)(x(x))x)
(x(x)(x(x)))x
(x(x)(x)x(x))
(x(x)(x)x)(x)
(x(x)(x)(xx))
(x(x)(x)(x)x)
(x(x)(x)(x))x
(x(x)(x))x(x)
(x(x)(x))(xx)
(x(x)(x))(x)x
(x(x)((xx)x))
(x(x)((x)xx))
(x(x)((x)x)x)
(x(x)((x)x))x
(x(x))x(x(x))
(x(x))x(x)(x)
(x(x))x((x)x)
(x(x))(xx(x))
(x(x))(xx)(x)
(x(x))(x(xx))
(x(x))(x(x)x)
(x(x))(x(x))x
(x(x))(x)x(x)
(x(x))(x)(xx)
(x(x))(x)(x)x
(x(x))((xx)x)
(x(x))((x)xx)
(x(x))((x)x)x
(x((xx(x))x))
(x((xx)x)(x))
(x((xx)x))(x)
(x((xx)(x)x))
(x((x(xx))x))
(x((x(x)x)x))
(x((x(x))xx))
(x((x(x))x)x)
(x((x(x))x))x
(x((x)xx)(x))
(x((x)xx))(x)
(x((x)x(x)x))
(x((x)x)x(x))
(x((x)x)x)(x)
(x((x)x)(xx))
(x((x)x)(x)x)
(x((x)x)(x))x
(x((x)x))x(x)
(x((x)x))(xx)
(x((x)x))(x)x
(x((x)(xx)x))
(x((x)(x)xx))
(x((x)(x)x)x)
(x((x)(x)x))x
(x(((xx)x)x))
(x(((x)xx)x))
(x(((x)x)xx))
(x(((x)x)x)x)
(x(((x)x)x))x
(x)x(x(x(x)))
(x)x(x(x)(x))
(x)x(x(x))(x)
(x)x(x((x)x))
(x)x(x)(x(x))
(x)x(x)(x)(x)
(x)x(x)((x)x)
(x)x((x(x))x)
(x)x((x)x)(x)
(x)x((x)(x)x)
(x)x(((x)x)x)
(x)(xx(x(x)))
(x)(xx(x)(x))
(x)(xx(x))(x)
(x)(xx((x)x))
(x)(xx)(x(x))
(x)(xx)(x)(x)
(x)(xx)((x)x)
(x)(x(xx(x)))
(x)(x(xx)(x))
(x)(x(xx))(x)
(x)(x(x(xx)))
(x)(x(x(x)x))
(x)(x(x(x))x)
(x)(x(x(x)))x
(x)(x(x)x(x))
(x)(x(x)x)(x)
(x)(x(x)(xx))
(x)(x(x)(x)x)
(x)(x(x)(x))x
(x)(x(x))x(x)
(x)(x(x))(xx)
(x)(x(x))(x)x
(x)(x((xx)x))
(x)(x((x)xx))
(x)(x((x)x)x)
(x)(x((x)x))x
(x)(x)x(x(x))
(x)(x)x(x)(x)
(x)(x)x((x)x)
(x)(x)(xx(x))
(x)(x)(xx)(x)
(x)(x)(x(xx))
(x)(x)(x(x)x)
(x)(x)(x(x))x
(x)(x)(x)x(x)
(x)(x)(x)(xx)
(x)(x)(x)(x)x
(x)(x)((xx)x)
(x)(x)((x)xx)
(x)(x)((x)x)x
(x)((xx(x))x)
(x)((xx)x)(x)
(x)((xx)(x)x)
(x)((x(xx))x)
(x)((x(x)x)x)
(x)((x(x))xx)
(x)((x(x))x)x
(x)((x)xx)(x)
(x)((x)x(x)x)
(x)((x)x)x(x)
(x)((x)x)(xx)
(x)((x)x)(x)x
(x)((x)(xx)x)
(x)((x)(x)xx)
(x)((x)(x)x)x
(x)(((xx)x)x)
(x)(((x)xx)x)
(x)(((x)x)xx)
(x)(((x)x)x)x
((xx(x(x)))x)
((xx(x)(x))x)
((xx(x))x)(x)
((xx(x))(x)x)
((xx((x)x))x)
((xx)x)(x(x))
((xx)x)(x)(x)
((xx)x)((x)x)
((xx)(x(x))x)
((xx)(x)x)(x)
((xx)(x)(x)x)
((xx)((x)x)x)
((x(xx(x)))x)
((x(xx)(x))x)
((x(xx))x)(x)
((x(xx))(x)x)
((x(x(xx)))x)
((x(x(x)x))x)
((x(x(x))x)x)
((x(x(x)))xx)
((x(x(x)))x)x
((x(x)x(x))x)
((x(x)x)x)(x)
((x(x)x)(x)x)
((x(x)(xx))x)
((x(x)(x)x)x)
((x(x)(x))xx)
((x(x)(x))x)x
((x(x))xx)(x)
((x(x))x(x)x)
((x(x))x)x(x)
((x(x))x)(xx)
((x(x))x)(x)x
((x(x))(xx)x)
((x(x))(x)xx)
((x(x))(x)x)x
((x((xx)x))x)
((x((x)xx))x)
((x((x)x)x)x)
((x((x)x))xx)
((x((x)x))x)x
((x)xx)(x(x))
((x)xx)(x)(x)
((x)xx)((x)x)
((x)x(x(x))x)
((x)x(x)x)(x)
((x)x(x)(x)x)
((x)x((x)x)x)
((x)x)x(x(x))
((x)x)x(x)(x)
((x)x)x((x)x)
((x)x)(xx(x))
((x)x)(xx)(x)
((x)x)(x(xx))
((x)x)(x(x)x)
((x)x)(x(x))x
((x)x)(x)x(x)
((x)x)(x)(xx)
((x)x)(x)(x)x
((x)x)((xx)x)
((x)x)((x)xx)
((x)x)((x)x)x
((x)(xx(x))x)
((x)(xx)x)(x)
((x)(xx)(x)x)
((x)(x(xx))x)
((x)(x(x)x)x)
((x)(x(x))xx)
((x)(x(x))x)x
((x)(x)xx)(x)
((x)(x)x(x)x)
((x)(x)x)x(x)
((x)(x)x)(xx)
((x)(x)x)(x)x
((x)(x)(xx)x)
((x)(x)(x)xx)
((x)(x)(x)x)x
((x)((xx)x)x)
((x)((x)xx)x)
((x)((x)x)xx)
((x)((x)x)x)x
(((xx(x))x)x)
(((xx)x)x)(x)
(((xx)x)(x)x)
(((xx)(x)x)x)
(((x(xx))x)x)
(((x(x)x)x)x)
(((x(x))xx)x)
(((x(x))x)xx)
(((x(x))x)x)x
(((x)xx)x)(x)
(((x)xx)(x)x)
(((x)x(x)x)x)
(((x)x)xx)(x)
(((x)x)x(x)x)
(((x)x)x)x(x)
(((x)x)x)(xx)
(((x)x)x)(x)x
(((x)x)(xx)x)
(((x)x)(x)xx)
(((x)x)(x)x)x
(((x)(xx)x)x)
(((x)(x)xx)x)
(((x)(x)x)xx)
(((x)(x)x)x)x
((((xx)x)x)x)
((((x)xx)x)x)
((((x)x)xx)x)
((((x)x)x)xx)
((((x)x)x)x)x 363

Dim crlf\$, n, plevel, opensupply, closesupply, xsupply, s\$, ct,slvl\$

Form1.Visible = True

Text1.Text = ""
crlf = Chr\$(13) + Chr\$(10)

For n = 1 To 7
Text1.Text = Text1.Text & crlf & n
plevel = 0: xsupply = n + 1: opensupply = n: closesupply = n
s = "": ct = 0
Text1.Text = Text1.Text & Str(ct)
Next

Text1.Text = Text1.Text & crlf & " done"

End Sub

DoEvents
If Len(s) = 3 * n + 1 Then
If n < 4 Then
' Text1.Text = Text1.Text & crlf & s
End If
ct = ct + 1
Else
If xsupply > 0 Then
s = s + "x"
xsupply = xsupply - 1
xsupply = xsupply + 1
s = Left(s, Len(s) - 1)
End If
If opensupply > 0 Then
s = s + "("
opensupply = opensupply - 1
plevel = plevel + 1
plevel = plevel - 1
opensupply = opensupply + 1
s = Left(s, Len(s) - 1)
End If
If plevel > 0 And Right(s, 1) <> "(" Then
s = s + ")"
closesupply = closesupply - 1
plevel = plevel - 1
slv = slv + Chr(plevel)

good = 1
For i = Len(slv) - 1 To 1 Step -1
If Asc(Mid(slv, i, 1)) = plevel Then Exit For
Next i
If Right(s, 2) = "))" And Mid(s, i + 1, 2) = "((" Then good = 0

closesupply = closesupply + 1
plevel = plevel + 1
s = Left(s, Len(s) - 1)
slv = Left(slv, Len(slv) - 1)
End If End If
End Sub

The bolded portion above is what disallows redundant parentheses.

The sequence matches A261207, "Expansion of (x-1)/8 - (x^2-4*x-1)/(8*sqrt(x^2-6*x+1))".

The OEIS gives formulae:

a(n) = Sum_{i=0..n-1}(2^i*(-1)^(n-i-1)*C(n+1,n-i-1)*C(n+i,n)).
a(n) = (-1)^(n+1)*(n*(n+1)/2)*hypergeom([1-n, 1+n], [3], 2)). - Peter Luschny, Aug 12 2015
a(n) = A010683(n-1)*(n+1)/2. - Peter Luschny, Aug 12 2015
a(n) ~ (3+2*sqrt(2))^n / (2^(9/4)*sqrt(Pi*n)). - Vaclav Kotesovec, Aug 17 2015

and indeed

10   for N=1 to 10
20     Tot=0
30     for I=0 to N-1
40         Tot=Tot+2^I*(-1)^(N-I-1)*combi(N+1,N-I-1)*combi(N+I,N)
50     next
60     print N,Tot
70   next N

produces

1 1
2 3
3 14
4 70
5 363
6 1925
7 10364
8 56412
9 309605
10 1710247

showing the n they are using is one less than the n defined in the puzzle.

The result is that the formula for our n should be modified to

Sum_{i=0..n}(2^i*(-1)^(n-i)*C(n+2,n-i)*C(n+i+1,n+1))

so that

10   for N=1 to 10
20     Tot=0
30     for I=0 to N
40         Tot=Tot+2^I*(-1)^(N-I)*combi(N+2,N-I)*combi(N+I+1,N+1)
50     next
60     print N,Tot
70   next N

produces

1 3
2 14
3 70
4 363
5 1925
6 10364
7 56412
8 309605
9 1710247
10 9496746

Continuing:

1   3
2   14
3   70
4   363
5   1925
6   10364
7   56412
8   309605
9   1710247
10   9496746
11   52960674
12   296408847
13   1663998345
14   9365980152
15   52837614456
16   298676661129
17   1691325089867
18   9592607927750
19   54482777049918
20   309837754937843
21   1764046900535053
22   10054065679046004
23   57357471874390100
24   327507083273000813
25   1871559305305229295
26   10703157635913663074
27   61252223125211995162
28   350761642234091168535
29   2009849405937979048209
30   11522823167447160856560
31   66097138071772826050032
32   379333031546044047384081
33   2178010945008139983802515
34   12510916032616822557907326
35   71894733600471118955053878
36   413308289609672326556769147
37   2376901375769641330819950741
38   13674135145370968737329751660
39   78692351113720634892373948236
40   453003943995018749091196993653
41   2608564825679519197207800388407
42   15025375086466714962427442767386
43   86569981252104537288825694376850
44   498910104362046633758630937340959
45   2875976062021950436525180764765849
46   16582559470632495843103679197866984
47   95634991484290917398859514860529512
48   551666931720733934091213228861104025
49   3182937443102904866961069889020715227
50   18368202566398646881542215187779427126

Edited on January 3, 2017, 3:25 pm
 Posted by Charlie on 2017-01-03 15:22:32

 Search: Search body:
Forums (0)