%I A007477 M0789
%S A007477 1,1,1,2,3,6,11,22,44,90,187,392,832,1778,3831,8304,18104,
%T A007477 39666,87296,192896,427778,951808,2124135,4753476,10664458,
%U A007477 23981698,54045448,122041844,276101386,625725936,1420386363
%N A007477 Shifts 2 places left when convolved with itself.
%C A007477 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+()(), ...
%C A007477 G.f. A(x) satisfies the equation 0=1+x-A(x)+(xA(x))^2.
%C A007477 Series reversion of xA(x) is x*A082582(-x). - Michael Somos, Jul 22 2003
%C A007477 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
%C A007477 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
%D A007477 N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and 
               related issues, Discr. Math., 308 (2008), 1209-1221.
%D A007477 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A007477 M. Bernstein and N. J. A. Sloane, <a href="http://arXiv.org/abs/math.CO/
               0205301">Some canonical sequences of integers</a>, Linear Alg. Applications, 
               226-228 (1995), 57-72; erratum 320 (2000), 210.
%H A007477 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=441">
               Encyclopedia of Combinatorial Structures 441</a>
%F A007477 a(n)=sum(a(k)a(n-2-k)), n>1.
%F A007477 The g.f. satisfies A(x)-x^2A(x)^2 = 1+x. - Ralf Stephan (ralf(AT)ark.in-berlin.de), 
               Jun 30 2003
%F A007477 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]).
%F A007477 G.f.: (1-sqrt(1-4x^2-4x^3))/(2x^2).
%F A007477 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
%p A007477 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;
%p A007477 Maple code from N. J. A. Sloane (njas(AT)research.att.com), Nov 02 2008:
%p A007477 unprotect(phi);
%p A007477 phi:=proc(t,u,M) local i,a;
%p A007477 a:=Array(0..M); for i from 0 to t-1 do a[i]:=u[i+1]; od:
%p A007477 for i from t to M do a[i]:=add(a[j]*a[i-1-j],j=0..i-1); od:
%p A007477 [seq(a[i],i=0..M)]; end;
%p A007477 phi(3,[0,1,1],30);
%o A007477 (PARI) a(n)=polcoeff((1-sqrt(1-4*x^2-4*x^3+x^3*O(x^n)))/2,n+2)
%Y A007477 Cf. A115178.
%Y A007477 Sequence in context: A063895 A027214 A132831 this_sequence A096202 A036653 
               A123769
%Y A007477 Adjacent sequences: A007474 A007475 A007476 this_sequence A007478 A007479 
               A007480
%K A007477 nonn,nice,easy
%O A007477 0,4
%A A007477 N. J. A. Sloane (njas(AT)research.att.com).
%E A007477 Additional comments from Michael Somos, Aug 03 2000.