cp's OEIS Frontend

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

%I A078623 #31 May 09 2019 08:29:08
%S A078623 1,0,2,1,9,11,56,106,421,1009,3565,9736,32594,95811,313535,961780,
%T A078623 3123577,9831373,31915121,102110314,332366526,1075228773,3513373374,
%U A078623 11456961550,37590603312,123327267531,406246177511,1339274997451,4427777075497,14655559052686
%N 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).
%C A078623 An unambiguous context-free grammar generating valid strings from S is S -> ( S ) S | [ T ] S | e T -> ( T | ( S ) T | [ T ] T | e
%H A078623 Alois P. Heinz, <a href="/A078623/b078623.txt">Table of n, a(n) for n = 0..1000</a>
%H A078623 <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>
%F A078623 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)).
%F A078623 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
%F A078623 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
%F A078623 From _Peter Bala_, Oct 23 2015: (Start)
%F A078623 Conjecturally, a(n-1) = (-1)^(n-1)*(1/n)*Sum_{k=1..n} binomial(n,k)*binomial(n - 2*k,k - 1).
%F A078623 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).
%F A078623 (End)
%F A078623 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
%e A078623 a(5) = 11 because the valid strings of length 5 are ()[(], [(](), [(][], [][(], ([(]), [(()], [()(], [(((], [([]], [[(]] and [[](].
%p A078623 a:= proc(n) option remember; `if`(n<4, [1, 0, 2, 1][n+1],
%p A078623       (4*(n+1)*(14*n^3-9*n^2-62*n+39) *a(n-1)
%p A078623       +(140*n^4-160*n^3-401*n^2+469*n-78) *a(n-2)
%p A078623       -12*(n-2)*(14*n^3-9*n^2-28*n-8) *a(n-3)
%p A078623       +23*(n-2)*(n-3)*(28*n^2+24*n-43) *a(n-4))/
%p A078623       ((n+2)*(n+1)*(28*n^2-32*n-39)))
%p A078623     end:
%p A078623 seq(a(n), n=0..40);  # _Alois P. Heinz_, May 19 2014
%t A078623 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_ *)
%t A078623 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 *)
%o A078623 (Maxima)
%o A078623 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 */
%Y A078623 Cf. A000108, A001003, A001006, A108447.
%K A078623 nonn,easy
%O A078623 0,3
%A A078623 Brian T. Howard (bhoward(AT)depauw.edu), Dec 11 2002