cp's OEIS Frontend

A007477 Shifts 2 places left when convolved with itself.

%I A007477 M0789 #116 Jan 25 2024 12:47:21
%S A007477 1,1,1,2,3,6,11,22,44,90,187,392,832,1778,3831,8304,18104,39666,87296,
%T A007477 192896,427778,951808,2124135,4753476,10664458,23981698,54045448,
%U A007477 122041844,276101386,625725936,1420386363,3229171828,7351869690,16760603722,38258956928,87437436916,200057233386,458223768512,1050614664580
%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 Series reversion of x*A(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_, 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_, Sep 25 2006
%C A007477 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
%C A007477 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
%C A007477 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
%D A007477 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007477 Reinhard Zumkeller, <a href="/A007477/b007477.txt">Table of n, a(n) for n = 0..1000</a>
%H A007477 Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
%H A007477 Andrei Asinowski, Cyril Banderier, and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).
%H A007477 J.-L. Baril and J.-M. Pallo, <a href="http://jl.baril.u-bourgogne.fr/Motzkin.pdf">Motzkin subposet and Motzkin geodesics in Tamari lattices</a>, 2013.
%H A007477 J.-L. Baril and S. Kirgizov, <a href="http://jl.baril.u-bourgogne.fr/Stirling.pdf">The pure descent statistic on permutations</a>, Preprint, 2016.
%H A007477 Paul Barry, <a href="https://arxiv.org/abs/1807.05794">Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences</a>, arXiv:1807.05794 [math.CO], 2018.
%H A007477 M. Bernstein and N. J. A. Sloane, <a href="https://arxiv.org/abs/math/0205301">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210; arXiv:math/0205301 [math.CO], 2002.
%H A007477 M. Bernstein and N. J. A. Sloane, <a href="/A003633/a003633_1.pdf">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
%H A007477 Carles Cardó, <a href="https://arxiv.org/abs/2401.07827">Growth and density in free magmas</a>, arXiv:2401.07827 [math.CO], 2024.
%H A007477 Justine Falque, Jean-Christophe Novelli, and Jean-Yves Thibon, <a href="https://arxiv.org/abs/2106.05248">Pinnacle sets revisited</a>, arXiv:2106.05248 [math.CO], 2021.
%H A007477 Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.
%H A007477 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=441">Encyclopedia of Combinatorial Structures 441</a>
%H A007477 Antti Karttunen, <a href="http://oeis.org/wiki/User:Antti_Karttunen/awkarttu.buffaloes.py">Python source code for parsing "Buffalo-variety" of sentences</a>
%H A007477 Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.
%H A007477 Wikipedia, <a href="http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo_buffalo_buffalo_Buffalo_buffalo ">Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo</a>
%F A007477 a(n) = sum( a(k) * a(n-2-k) ), n>1.
%F A007477 G.f. A(x) satisfies the equation 0 = 1 + x - A(x) + (x*A(x))^2.
%F A007477 The g.f. satisfies A(x)-x^2*A(x)^2 = 1+x. - _Ralf Stephan_, Jun 30 2003
%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_, May 31 2006
%F A007477 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
%F A007477 D-finite with recurrence: (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
%F A007477 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
%F A007477 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
%F A007477 a(n) ~ sqrt(3 - 4*r^2) * (4*r)^n * (1+r)^(n+1) / (sqrt(Pi)*n^(3/2)), where r = 0.41964337760708056627592628232664330021208937304879612338939... is the root of the equation 4*r^2*(1+r) = 1. - _Vaclav Kotesovec_, Jul 03 2021
%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 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);
%p A007477 # _N. J. A. Sloane_, Nov 02 2008
%t A007477 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 *)
%t A007477 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_ *)
%o A007477 (PARI) a(n)=polcoeff((1-sqrt(1-4*x^2-4*x^3+x^3*O(x^n)))/2,n+2)
%o A007477 (Haskell)
%o A007477 a007477 n = a007477_list !! n
%o A007477 a007477_list = 1 : 1 : f [1,1] where
%o A007477    f xs = y : f (y:xs) where y = sum $ zipWith (*) (tail xs) (reverse xs)
%o A007477 -- _Reinhard Zumkeller_, Apr 09 2012
%o A007477 (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 */
%Y A007477 Cf. A115178, A213705.
%K A007477 nonn,nice,easy
%O A007477 0,4
%A A007477 _N. J. A. Sloane_
%E A007477 Additional comments from _Michael Somos_, Aug 03 2000