%I M3556 #130 Aug 03 2024 04:17:10
%S 1,1,4,19,100,562,3304,20071,124996,793774,5120632,33463102,221060008,
%T 1473830308,9904186192,67015401391,456192667396,3122028222934,
%U 21467769499864,148246598341018,1027656663676600,7148588698592956,49884553176689584
%N Shifts left when INVERT transform applied thrice.
%C More generally, coefficients of (1+m*x-sqrt(m^2*x^2-(2*m+2)*x+1))/(2*m*x) are given by a(n) = Sum_{k=0..n} (m+1)^k*N(n,k) where N(n,k) = (1/n)*binomial(n,k)*binomial(n,k+1) are the Narayana numbers (A001263). - _Benoit Cloitre_, May 24 2003
%C If y = x*A(x) then 3*y^2 - (1+2*x)*y + x = 0 and x = y*(1-3*y)/(1-2*y). - _Michael Somos_, Sep 28 2003
%C The sequence 0,1,4,19,... with g.f. (1-4*x-sqrt(1-8*x+4*x^2))/(6*x) and has a(n) = Sum_{k=0..floor((n-1)/2)} binomial(n-1,2k)*C(k)*4^(n-1-2*k)*3^k. a(n+1) = Sum_{k=0..floor(n/2)} binomial(n,2*k)*C(k)*4^(n-2*k)*3^k counts Motzkin paths of length n in which the level steps have 4 colors and the up steps have 3. It is the binomial transform of A107264 and corresponds to the series reversion of x/(1+4*x+3*x^2). - _Paul Barry_, May 18 2005
%C The Hankel transform of this sequence is 3^binomial(n+1,2). - _Philippe Deléham_, Oct 29 2007
%C a(n) is the number of Schroder paths of semilength n in which there are no (2,0)-steps at level 0 and at a higher level they come in 2 colors. Example: a(2)=4 because we have UDUD, UUDD, UBD, and URD, where U=(1,1), D=(1,-1), while B (R) is a blue (red) (2,0)-step. - _Emeric Deutsch_, May 02 2011
%C a(n) is the number of Schroder paths of semilength n-1 in which the (2,0)-steps at level 0 come in 3 colors and those at a higher level come in 2 colors. Example: a(3)=19 because, denoting U=(1,1), H=(1,0), and D=(1,-1), we have 3^2 = 9 paths of shape HH, 3 paths of shape HUD, 3 paths of shape UDH, 2 paths of shape UHD, and 1 path of each of the shapes UDUD and UUDD. - _Emeric Deutsch_, May 02 2011
%C From _David Callan_, Jun 21 2013: (Start)
%C a(n) = number of (left) planted binary trees with n edges in which each vertex has a designated favorite neighbor. Planted binary trees are counted by the Catalan numbers A000108.
%C Example: for n=2, there are 2 planted binary trees: edges LL and LR from the root (L=left, R=right). Each has just one vertex with 2 neighbors, and so a(2)=4.
%C Proof outline: each vertex has 1,2 or 3 neighbors. Let X (resp. Y) denote the number of vertices with 2 (resp. 3) neighbors. Then X + 2Y = n - 1 (split the non-root edges into pairs with a common parent vertex and singletons). Thus the number of choices for designating favorite neighbors is 2^X * 3^Y = 2^(n-1)(3/4)^Y. The distribution for Y is known because, under the rotation correspondence, a.k.a. the deBruijn-Morselt bijection, vertices with 2 children in an n-edge planted binary tree correspond to DDUs in a Dyck path, and DDUs have the Touchard distribution (A091894) with gf F(x,y) = (1-2x+2xy - sqrt(1-4x+4x^2-4x^2 y))/(2xy). The desired g.f., Sum_{n>=1} a(n)*x^n, is therefore 1/2*(F(2x,3/4)-1). (End)
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H G. C. Greubel, <a href="/A007564/b007564.txt">Table of n, a(n) for n = 0..1000</a> (terms 0 to 100 by T. D. Noe)
%H C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00250-3">Generating functions for generating trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Barry/barry91.html">On Integer-Sequence-Based Constructions of Generalized Pascal Triangles</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
%H Paul Barry and Aoife Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry2/barry126.html">A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations</a>, J. Int. Seq. 14 (2011), Article 11.3.8.
%H Paul Barry and Aoife Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry2/barry190r.html">Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths</a>, Journal of Integer Sequences, Vol. 15 (2012), Article 12.4.8.
%H 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. [Link to arXiv version]
%H 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 Z. Chen and H. Pan, <a href="http://arxiv.org/abs/1608.02448">Identities involving weighted Catalan-Schroder and Motzkin Paths</a>, arXiv:1608.02448 arXiv:1608.02448 [math.CO], 2016. Eq. (1.13) a=1, b=3.
%H C. Coker, <a href="http://dx.doi.org/10.1016/j.disc.2003.12.008">A family of eigensequences</a>, Discrete Math. 282 (2004), 249-250.
%H Shishuo Fu and Yaling Wang, <a href="https://arxiv.org/abs/1908.03912">Bijective recurrences concerning two Schröder triangles</a>, arXiv:1908.03912 [math.CO], 2019.
%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=443">Encyclopedia of Combinatorial Structures 443</a>
%H Huyile Liang, Jeffrey Remmel, and Sainan Zheng, <a href="https://arxiv.org/abs/1710.05795">Stieltjes moment sequences of polynomials</a>, arXiv:1710.05795 [math.CO], 2017, see page 11.
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%F G.f.: (1+2*x-sqrt(1-8*x+4*x^2))/(6*x). - _Emeric Deutsch_, Nov 03 2001
%F a(0)=1; for n>=1, a(n) = Sum_{k=0..n} 3^k*N(n,k) where N(n,k) = (1/n)*binomial(n, k)*binomial(n, k+1) are the Narayana numbers (A001263). - _Benoit Cloitre_, May 24 2003
%F a(n) = Sum_{k=0..n} A088617(n, k)*3^k*(-2)^(n-k). - _Philippe Deléham_, Jan 21 2004
%F With offset 1: a(1) = 1, a(n) = -2*a(n-1) + 3*Sum_{i=1..n-1} a(i)*a(n-i). - _Benoit Cloitre_, Mar 16 2004
%F D-finite with recurrence a(n) = (4*(2n-1)*a(n-1) - 4*(n-2)*a(n-2)) / (n+1) for n>=2, a(0) = a(1) = 1. - _Philippe Deléham_, Aug 19 2005
%F From _Paul Barry_, Dec 15 2008: (Start)
%F G.f.: 1/(1-x/(1-3x/(1-x/(1-3x/(1-x/(1-3x/(1-x/(1-3x........ (continued fraction).
%F The g.f. of a(n+1) is 1/(1-4x-3x^2/(1-4x-3x^2/(1-4x-3x^2/(1-4x-3x^2.... (continued fraction). (End)
%F a(0) = 1, for n>=1, 3a(n) = A047891(n). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Dec 02 2009
%F a(n) = upper left term in M^n, M = the production matrix:
%F 1, 1
%F 3, 3, 3
%F 1, 1, 1, 1
%F 3, 3, 3, 3, 3
%F 1, 1, 1, 1, 1, 1
%F ...
%F - _Gary W. Adamson_, Jul 08 2011
%F G.f.: A(x)= (1+2*x-sqrt(1-8*x+4*x^2))/(6*x)= 1/G(0); G(k)= 1 + 2*x - 3*x/G(k+1); (continued fraction, 1-step ). - _Sergei N. Gladkovskii_, Jan 05 2012
%F a(n) ~ sqrt(6+4*sqrt(3))*(4+2*sqrt(3))^n/(6*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 07 2012
%F a(n) = 2^n/sqrt(3)*LegendreP(n,-1,2) for n >= 1, where LegendreP is the associated Legendre function of the first kind, in Maple's notation. - _Robert Israel_, Mar 24 2015
%e G.f. = 1 + x + 4*x^2 + 19*x^3 + 100*x^4 + 562*x^5 + 3304*x^6 + 20071*x^7 + 124996*x^8 + ...
%p A007564_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
%p for w from 1 to n do a[w] := a[w-1]+3*add(a[j]*a[w-j-1],j=1..w-1) od;
%p convert(a, list) end: A007564_list(21); # _Peter Luschny_, May 19 2011
%t a[0]=1; a[1]=1; a[n_]/;n>=2 := a[n] = a[n-1] + 3 Sum[a[k-1]a[n-k],{k,n-1}] ; Table[a[n],{n,0,10}] (* _David Callan_, Aug 25 2009 *)
%t Table[Hypergeometric2F1[-n, 1 - n, 2, 3], {n, 0, 22}] (* _Arkadiusz Wesolowski_, Aug 13 2012 *)
%t Table[(2^n (LegendreP[n+1, 2] - LegendreP[n-1, 2]) + 2 KroneckerDelta[n])/(6n+3), {n, 0, 20}] (* _Vladimir Reshetnikov_, Nov 01 2015 *)
%t CoefficientList[Series[(1+2x-Sqrt[1-8x+4x^2])/(6x),{x,0,30}],x] (* _Harvey P. Dale_, Feb 07 2016 *)
%o (PARI) {a(n) = if( n<1, n==0, sum( k=0, n, 3^k * binomial( n, k) * binomial( n, k+1)) / n)} /* _Michael Somos_, Sep 28 2003 */
%o (PARI) {a(n) = if( n<0, 0, n++; polcoeff( serreverse( x * (1 - 3*x) / (1 - 2*x) + x * O(x^n)), n))} /* _Michael Somos_, Sep 28 2003 */
%o (PARI) a(n) = (2^n*(pollegendre(n+1,2)-pollegendre(n-1,2)) + 2*(n==0))/(6*n+3); \\ _Michel Marcus_, Nov 02 2015
%o (PARI) x='x+O('x^100); Vec((1+2*x-sqrt(1-8*x+4*x^2))/(6*x)) \\ _Altug Alkan_, Nov 02 2015
%Y Cf. A047891, A054872.
%K nonn,nice,eigen
%O 0,3
%A _N. J. A. Sloane_