|
| |
|
|
A007477
|
|
Shifts 2 places left when convolved with itself.
(Formerly M0789)
|
|
9
| |
|
|
1, 1, 1, 2, 3, 6, 11, 22, 44, 90, 187, 392, 832, 1778, 3831, 8304, 18104, 39666, 87296, 192896, 427778, 951808, 2124135, 4753476, 10664458, 23981698, 54045448, 122041844, 276101386, 625725936, 1420386363
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| 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
The Kn21(n) triangle sums of A175136 lead to A007477(n+1), while the Kn22(n) = A007477(n+3)-1, Kn23(n) = A007477(n+5)-(4+n) and Kn3(n) =A007477(2*n+1) triangle sums of A175136 are related to the sequence given above. For the definition of these triangle sums see A180662. [From Johannes W. Meijer, May 6 2011]
|
|
|
REFERENCES
| 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).
|
|
|
LINKS
| 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
|
|
|
FORMULA
| 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
G.f.: 1/(1-x/(1-x^2/(1-x^2/(1-x/(1-x^2/(1-x^2/(1-x/(1-x^2/(1-x^2/(1-... (continued fraction). [From Paul Barry (pbarry(AT)wit.ie), Jul 30 2010]
|
|
|
MAPLE
| 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);
|
|
|
MATHEMATICA
| f[x_] := (1 - Sqrt[1 - 4x^2 - 4x^3])/2; Drop[ CoefficientList[ Series[f[x], {x, 0, 32}], x], 2] (* From Jean-François Alcover, Nov 22 2011, after Pari *)
|
|
|
PROG
| (PARI) a(n)=polcoeff((1-sqrt(1-4*x^2-4*x^3+x^3*O(x^n)))/2, n+2)
|
|
|
CROSSREFS
| Cf. A115178.
Sequence in context: A027214 A192652 A132831 * A096202 A036653 A123769
Adjacent sequences: A007474 A007475 A007476 * A007478 A007479 A007480
|
|
|
KEYWORD
| nonn,nice,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Additional comments from Michael Somos, Aug 03 2000.
|
| |
|
|
