A078623 Number of matched parentheses and brackets of length n, where a closing bracket will close any remaining open parentheses back to the matching open bracket (as in some versions of LISP).

1, 0, 2, 1, 9, 11, 56, 106, 421, 1009, 3565, 9736, 32594, 95811, 313535, 961780, 3123577, 9831373, 31915121, 102110314, 332366526, 1075228773, 3513373374, 11456961550, 37590603312, 123327267531, 406246177511, 1339274997451, 4427777075497, 14655559052686

Offset: 0

Author

Brian T. Howard (bhoward(AT)depauw.edu), Dec 11 2002

Keywords

• nonn
• easy

Comments

An unambiguous context-free grammar generating valid strings from S is S -> ( S ) S | [ T ] S | e T -> ( T | ( S ) T | [ T ] T | e

Examples

			a(5) = 11 because the valid strings of length 5 are ()[(], [(](), [(][], [][(], ([(]), [(()], [()(], [(((], [([]], [[(]] and [[](].
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for sequences related to parenthesizing

Crossrefs

Cf. A000108, A001003, A001006, A108447.

Programs

Maple

a:= proc(n) option remember; `if`(n<4, [1, 0, 2, 1][n+1],
      (4*(n+1)*(14*n^3-9*n^2-62*n+39) *a(n-1)
      +(140*n^4-160*n^3-401*n^2+469*n-78) *a(n-2)
      -12*(n-2)*(14*n^3-9*n^2-28*n-8) *a(n-3)
      +23*(n-2)*(n-3)*(28*n^2+24*n-43) *a(n-4))/
      ((n+2)*(n+1)*(28*n^2-32*n-39)))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, May 19 2014

Mathematica

a[n_] := Sum[Binomial[n+1, j]*Sum[(-1)^(i+j)*Binomial[j, i]*Binomial[2*n-2*j-i, n-i-j], {i, 0, n-j}], {j, 0, n+1}]/(n+1); Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Apr 03 2015, after Vladimir Kruchinin *)
nmax = 40; A[] = 1; Do[A[x] = 1 - x*A[x] + x*(1 + 2*x)*A[x]^2 - x^3*A[x]^3 + O[x]^nmax // Normal, {nmax}]; CoefficientList[A[x], x] (* Vaclav Kotesovec, May 09 2019 *)

Maxima

a(n):=sum(binomial(n+1,j)*sum((-1)^(i+j)*binomial(j,i)*binomial(2*n-2*j-i,n-i-j),i,0,n-j),j,0,n+1)/(n+1); /* Vladimir Kruchinin, May 19 2014 */

Formula

a(0) = 1, a(n) = Sum_{i=0..n-2} a(n-2-i)*(a(i) + b(i)), where b(0) = 1, b(n) = b(n-1) + Sum_{i=0..n-2} b(n-2-i)*(a(i) + b(i)).

a(n) = (Sum_{j=0..n+1} C(n+1,j)*Sum_{i=0..n-j} (-1)^(i+j)*C(j,i)*C(2*n-2*j-i,n-i-j)) / (n+1). - Vladimir Kruchinin, May 19 2014

a(n) ~ c * ((1+sqrt(13+16*sqrt(2)))/2)^n / n^(3/2), where c = sqrt(1 + 9/(8*sqrt(2)) - sqrt(211/224 + 43/(7*sqrt(2)))/2) / sqrt(Pi) = 0.453452365404498112381472576661214848447318569684502125279149391488... . - Vaclav Kotesovec, Aug 25 2014, updated May 09 2019

From Peter Bala, Oct 23 2015: (Start)

Conjecturally, a(n-1) = (-1)^(n-1)*(1/n)*Sum_{k=1..n} binomial(n,k)*binomial(n - 2*k,k - 1).

The formula (1/n)*Sum_{k=1..n} binomial(n,k)*binomial(n + m*k,k - 1) gives A001006 (m = -1), A000108 (m = 0), A001003 (m = 1) and A108447 (m = 2).

(End)

G.f. A(x) satisfies -1 + (1+x)*A(x) - x*(1+2*x)*A(x)^2 + x^3*A(x)^3 = 0. - Vaclav Kotesovec, May 09 2019