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

Home > Just Math
Counting brackets (Posted on 2017-01-03) Difficulty: 2 of 5
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.)
Solution 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$


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)
 Next
 
 
 
 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 (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information