0,4

Words of length n in language defined by L = 1 + a + (L)L: L(0)=1, L(1)=a, L(2)=(), L(3)=(a)+()a, L(4)=(())+(a)a+()(), ...

G.f. A(x) satisfies the equation 0=1+x-A(x)+(xA(x))^2.

Series reversion of xA(x) is x*A082582(-x). - Michael Somos, Jul 22 2003

a(n) = number of Motzkin n-paths (A001006) in which no flatstep (F) is immediately followed by either an upstep (U) or a flatstep, in other words, each flatstep is either followed by a downstep (D) or ends the path. For example, a(4)=3 counts UDUD, UFDF, UUDD. - David Callan (callan(AT)stat.wisc.edu), Jun 07 2006

a(n) = number of Dyck (n+1)-paths (A000108) containing no UDUs and no subpaths of the form UUPDD where P is a nonempty Dyck path. For example, a(4)=3 counts UUUDDUUDDD, UUDDUUDDUD, UUUDDUDDUD. - David Callan (callan(AT)stat.wisc.edu), Sep 25 2006

N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 441

a(n)=sum(a(k)a(n-2-k)), n>1.

The g.f. satisfies A(x)-x^2A(x)^2 = 1+x. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Jun 30 2003

Comment from Gary W. Adamson (qntmpkt(AT)yahoo.com) and R. J. Mathar, Oct 27 2008: Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-1}*a_0 for n >= t. For example phi([1]) is the Catalan numbers A000108. The present sequence is (essentially) phi([0,1,1]).

G.f.: (1-sqrt(1-4x^2-4x^3))/(2x^2).

G.f.: (1+x)c(x^2(1+x)) where c(x) is g.f. of A000108. - Paul Barry (pbarry(AT)wit.ie), May 31 2006

A007477 := proc(n) option remember; local k; if n <= 1 then 1 else add(A007477(k)*A007477(n-k-2), k=0..n-2); fi; end;

Maple code from N. J. A. Sloane (njas(AT)research.att.com), Nov 02 2008:

unprotect(phi);

phi:=proc(t, u, M) local i, a;

a:=Array(0..M); for i from 0 to t-1 do a[i]:=u[i+1]; od:

for i from t to M do a[i]:=add(a[j]*a[i-1-j], j=0..i-1); od:

[seq(a[i], i=0..M)]; end;

phi(3, [0, 1, 1], 30);

(PARI) a(n)=polcoeff((1-sqrt(1-4*x^2-4*x^3+x^3*O(x^n)))/2, n+2)

Cf. A115178.

Sequence in context: A063895 A027214 A132831 this_sequence A096202 A036653 A123769

Adjacent sequences: A007474 A007475 A007476 this_sequence A007478 A007479 A007480

nonn,nice,easy

N. J. A. Sloane (njas(AT)research.att.com).

Additional comments from Michael Somos, Aug 03 2000.