login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 02:52 EDT 2020. Contains 337950 sequences. (Running on oeis4.)