perplexus.info :: Just Math : Counting brackets

Home > Just Math

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:

x(x)

(xx)

(x)x 3

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

x(x(x(x)))

x(x(x)(x))

x(x(x))(x)

x(x((x)x))

x(x)(x(x))

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

x(x(x(x(x))))

x(x(x(x)(x)))

x(x(x(x))(x))

x(x(x(x)))(x)

x(x(x((x)x)))

x(x(x)(x(x)))

x(x(x)(x)(x))

x(x(x)(x))(x)

x(x(x)((x)x))

x(x(x))(x(x))

x(x(x))(x)(x)

x(x(x))((x)x)

x(x((x(x))x))

x(x((x)x)(x))

x(x((x)x))(x)

x(x((x)(x)x))

x(x(((x)x)x))

x(x)(x(x(x)))

x(x)(x(x)(x))

x(x)(x(x))(x)

x(x)(x((x)x))

x(x)(x)(x(x))

x(x)(x)(x)(x)

x(x)(x)((x)x)

x(x)((x(x))x)

x(x)((x)x)(x)

x(x)((x)(x)x)

x(x)(((x)x)x)

x((x(x(x)))x)

x((x(x)(x))x)

x((x(x))x)(x)

x((x(x))(x)x)

x((x((x)x))x)

x((x)x)(x(x))

x((x)x)(x)(x)

x((x)x)((x)x)

x((x)(x(x))x)

x((x)(x)x)(x)

x((x)(x)(x)x)

x((x)((x)x)x)

x(((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$

Private Sub Form_Load()

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

addOn

Text1.Text = Text1.Text & Str(ct)

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

End Sub

Sub addOn()

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

addOn

xsupply = xsupply + 1

s = Left(s, Len(s) - 1)

End If

If opensupply > 0 Then

s = s + "("

opensupply = opensupply - 1

plevel = plevel + 1

addOn

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

If good Then addOn

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

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info