A213705 -id:A213705 - cp's OEIS frontend

A007477 Shifts 2 places left when convolved with itself.

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

Offset: 0

N. J. A. Sloane

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

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

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
J.-L. Baril and J.-M. Pallo, Motzkin subposet and Motzkin geodesics in Tamari lattices, 2013.
J.-L. Baril and S. Kirgizov, The pure descent statistic on permutations, Preprint, 2016.
Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210; arXiv:math/0205301 [math.CO], 2002.
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]
Carles Cardó, Growth and density in free magmas, arXiv:2401.07827 [math.CO], 2024.
Justine Falque, Jean-Christophe Novelli, and Jean-Yves Thibon, Pinnacle sets revisited, arXiv:2106.05248 [math.CO], 2021.
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

Cf. A115178, A213705.

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

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

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

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 */

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

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

Additional comments from Michael Somos, Aug 03 2000

A007853 Number of maximal antichains in rooted plane trees on n nodes.

Original entry on oeis.org

1, 2, 5, 15, 50, 178, 663, 2553, 10086, 40669, 166752, 693331, 2917088, 12398545, 53164201, 229729439, 999460624, 4374546305, 19250233408, 85120272755, 378021050306, 1685406494673, 7541226435054, 33852474532769, 152415463629568, 688099122024944

Offset: 1

Martin Klazar

nonn

Also the number of initial subtrees (emanating from the root) of rooted plane trees on n vertices, where we require that an initial subtree contains either all or none of the branchings under any given node. The leaves of such a subtree comprise the roots of a corresponding antichain cover. Also, in the (non-commutative) multicategory of free pure multifunctions with one atom, a(n) is the number of composable pairs whose composite has n positions. - Gus Wiseman, Aug 13 2018

The g.f. is denoted by y_2 in Bacher 2004 Proposition 7.5 on page 20. - Michael Somos, Nov 07 2019

			G.f. = x + 2*x^2 + 5*x^3 + 15*x^4 + 50*x^5 + 178*x^6 + 663*x^7 + 2553*x^8 + ... - _Michael Somos_, Nov 07 2019

R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.
M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
Index entries for sequences related to rooted trees

Cf. A000081, A000108, A001003, A001006, A126120, A213705, A317713, A318046, A318048, A318049.

ie[t_]:=If[Length[t]==0,1,1+Product[ie[b],{b,t}]];
allplane[n_]:=If[n==1,{{}},Join@@Function[c,Tuples[allplane/@c]]/@Join@@Permutations/@IntegerPartitions[n-1]];
Table[Sum[ie[t],{t,allplane[n]}],{n,9}] (* Gus Wiseman, Aug 13 2018 *)

a(n):=1/(n+1)*binomial(2*n,n)+sum((k+2)/(n+1)*binomial(2*n-k-1,n-k-1)*(sum(((binomial(2*i,i))*(binomial(k+i,3*i)))/(i+1),i,0,floor(k/2))),k,0,n-1); /* Vladimir Kruchinin, Apr 05 2019 */

{a(n) = my(A); if( n<0, 0, A = sqrt(1 - 4*x + x * O(x^n)); polcoeff( (3 - 2*x - A - sqrt(2 - 16*x + 4*x^2 + (2 + 4*x) * A)) / 4, n))}; /* Michael Somos, Nov 07 2019 */

G.f.: (1/4) * (3 - 2*x - sqrt(1-4*x) - sqrt(2) * sqrt((1+2*x) * sqrt(1-4*x) + 1 - 8*x + 2*x^2)) [from Klazar]. - Sean A. Irvine, Feb 06 2018
a(n) = (1/(n+1))*C(2*n,n) + Sum_{k=0..n-1} ((k+2)/(n+1))*C(2*n-k-1,n-k-1)*Sum_{i=0..floor(k/2)} C(2*i,i)*C(k+i,3*i)/(i+1). - Vladimir Kruchinin, Apr 05 2019
Given the g.f. A(x) and the g.f. of A213705 B(x), then -x = A(-B(x)). - Michael Somos, Nov 07 2019

More terms from Sean A. Irvine, Feb 06 2018

cp's OEIS Frontend

A007477 Shifts 2 places left when convolved with itself.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

PARI

Formula

Extensions