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,3

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Index entries for sequences related to parenthesizing

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

Example

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

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 *)

Prog

(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 */

Crossrefs

Cf. A000108, A001003, A001006, A108447.

Sequence in context: A192324 A063579 A240085 * A198204 A099599 A085488

Adjacent sequences: A078620 A078621 A078622 * A078624 A078625 A078626

Keyword

nonn,easy

Author

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

Status

approved