The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A007564 Shifts left when INVERT transform applied thrice. (Formerly M3556) 23
 1, 1, 4, 19, 100, 562, 3304, 20071, 124996, 793774, 5120632, 33463102, 221060008, 1473830308, 9904186192, 67015401391, 456192667396, 3122028222934, 21467769499864, 148246598341018, 1027656663676600, 7148588698592956, 49884553176689584 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS 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 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 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 The Hankel transform of this sequence is 3^binomial(n+1,2). - Philippe Deléham, Oct 29 2007 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 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 From David Callan, Jun 21 2013: (Start) 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. 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. 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) REFERENCES N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS G. C. Greubel, Table of n, a(n) for n = 0..1000(terms 0 to 100 by T. D. Noe) C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating functions for generating trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55. Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4. P. Barry, A. Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations , J. Int. Seq. 14 (2011) # 11.3.8 Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8. 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] Z. Chen, H. Pan, Identities involving weighted Catalan-Schroder and Motzkin Paths, arXiv:1608.02448 (2016), eq. (1.13) a=1, b=3. C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250. Shishuo Fu, Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019. Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011. INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 443 Huyile Liang, Jeffrey Remmel, Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 11. N. J. A. Sloane, Transforms FORMULA G.f.: (1+2*x-sqrt(1-8*x+4*x^2))/(6*x). - Emeric Deutsch, Nov 03 2001 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 a(n) = Sum_{k=0..n} A088617(n, k)*3^k*(-2)^(n-k). - Philippe Deléham, Jan 21 2004 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 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 From Paul Barry, Dec 15 2008: (Start) G.f.: 1/(1-x/(1-3x/(1-x/(1-3x/(1-x/(1-3x/(1-x/(1-3x........ (continued fraction). 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) a(0) = 1, for n>=1, 3a(n) = A047891(n). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Dec 02 2009 a(n) = upper left term in M^n, M = the production matrix: 1, 1 3, 3, 3 1, 1, 1, 1 3, 3, 3, 3, 3 1, 1, 1, 1, 1, 1 ... - Gary W. Adamson, Jul 08 2011 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 a(n) ~ sqrt(6+4*sqrt(3))*(4+2*sqrt(3))^n/(6*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 07 2012 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 EXAMPLE 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 + ... MAPLE A007564_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1; 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; convert(a, list) end: A007564_list(21); # Peter Luschny, May 19 2011 MATHEMATICA 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 *) Table[Hypergeometric2F1[-n, 1 - n, 2, 3], {n, 0, 22}] (* Arkadiusz Wesolowski, Aug 13 2012 *) Table[(2^n (LegendreP[n+1, 2] - LegendreP[n-1, 2]) + 2 KroneckerDelta[n])/(6n+3), {n, 0, 20}] (* Vladimir Reshetnikov, Nov 01 2015 *) CoefficientList[Series[(1+2x-Sqrt[1-8x+4x^2])/(6x), {x, 0, 30}], x] (* Harvey P. Dale, Feb 07 2016 *) PROG (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 */ (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 */ (PARI) a(n) = (2^n*(pollegendre(n+1, 2)-pollegendre(n-1, 2)) + 2*(n==0))/(6*n+3); \\ Michel Marcus, Nov 02 2015 (PARI) x='x+O('x^100); Vec((1+2*x-sqrt(1-8*x+4*x^2))/(6*x)) \\ Altug Alkan, Nov 02 2015 CROSSREFS Cf. A047891, A054872. Sequence in context: A306511 A177249 A083882 * A218185 A086624 A307121 Adjacent sequences:  A007561 A007562 A007563 * A007565 A007566 A007567 KEYWORD nonn,nice,eigen AUTHOR 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 21 13:20 EDT 2020. Contains 337272 sequences. (Running on oeis4.)