login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007477 Shifts 2 places left when convolved with itself.
(Formerly M0789)
11
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, 3229171828, 7351869690, 16760603722, 38258956928, 87437436916, 200057233386, 458223768512, 1050614664580 (list; graph; refs; listen; history; text; 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+()(), ...

Series reversion of x*A(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, 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, Sep 25 2006

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]). - Gary W. Adamson and R. J. Mathar, Oct 27 2008

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. - Johannes W. Meijer, May 06 2011

For n>=2, a(n) gives number of possible, ways to parse an English sentence consisting of just n+1 copies of word "buffalo", with one particular "plausible" grammar. See the Wikipedia page and my Python source at OEIS Wiki. Whether these are really intelligible sentences is of course debatable. See A213705 for a more plausible example in the Finnish language. - Antti Karttunen, Sep 14 2012

REFERENCES

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

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

J.-L. Baril, J.-M. Pallo, Motzkin subposet and Motzkin geodesics in Tamari lattices, 2013.

J.-L. Baril, S. Kirgizov, The pure descent statistic on permutations, Preprint, 2016.

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

M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]

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

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 441

Antti Karttunen, Python source code for parsing "Buffalo-variety" of sentences

Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.

Wikipedia, Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo

FORMULA

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

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

The g.f. satisfies A(x)-x^2*A(x)^2 = 1+x. - Ralf Stephan, Jun 30 2003

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, 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). - Paul Barry, Jul 30 2010

Conjecture: (n+2)*a(n) +(n+1)*a(n-1) +4*(-n+1)*a(n-2) +2*(-4*n+9)*a(n-3) +2*(-2*n+7)*a(n-4)=0. - R. J. Mathar, Dec 02 2012

a(n) = sum_{k=0..n-2} binomial(2*k+2,n-k-2)*binomial(n-k-2,k)/(k+1), n>1, a(0)=1, a(1)=1. - Vladimir Kruchinin, Nov 22 2014

a(n) = sum_{k=0..n-1} (-1)^(n-1-k)*binomial(n-1,k)*A082582(k+2), for n>0. - Thomas Baruchel, Jan 22 2015

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;

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

# N. J. A. Sloane, Nov 02 2008

MATHEMATICA

f[x_] := (1 - Sqrt[1 - 4x^2 - 4x^3])/2; Drop[ CoefficientList[ Series[f[x], {x, 0, 32}], x], 2] (* Jean-François Alcover, Nov 22 2011, after Pari *)

a[n_] := Sum[Binomial[2*k+2, n-k-2]*Binomial[n-k-2, k]/(k+1), {k, 0, n-2}]; a[0] = a[1] = 1; Array[a, 40, 0] (* Jean-François Alcover, Mar 04 2016, after Vladimir Kruchinin *)

PROG

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

(Haskell)

a007477 n = a007477_list !! n

a007477_list = 1 : 1 : f [1, 1] where

   f xs = y : f (y:xs) where y = sum $ zipWith (*) (tail xs) (reverse xs)

-- Reinhard Zumkeller, Apr 09 2012

(Maxima) a(n):=if n<2 then 1 else sum((binomial(2*k+2, n-k-2)*binomial(n-k-2, k))/(k+1), k, 0, n-2); /* Vladimir Kruchinin, Nov 22 2014 */

CROSSREFS

Cf. A115178, A213705.

Sequence in context: A027214 A192652 A132831 * A274936 A244521 A096202

Adjacent sequences:  A007474 A007475 A007476 * A007478 A007479 A007480

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

Additional comments from Michael Somos, Aug 03 2000

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 18 20:32 EST 2018. Contains 299330 sequences. (Running on oeis4.)