

A007564


Shifts left when INVERT transform applied thrice.
(Formerly M3556)


21



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*xsqrt(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*(13*y)/(12*y).  Michael Somos, Sep 28 2003
The sequence 0,1,4,19,... with g.f. (14*xsqrt(18*x+4*x^2))/(6*x) and has a(n) = Sum_{k=0..floor((n1)/2)} binomial(n1,2k)*C(k)*4^(n12*k)*3^k. a(n+1) = Sum_{k=0..floor(n/2)} binomial(n,2*k)*C(k)*4^(n2*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 n1 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 nonroot 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^(n1)(3/4)^Y. The distribution for Y is known because, under the rotation correspondence, a.k.a. the deBruijnMorselt bijection, vertices with 2 children in an nedge planted binary tree correspond to DDUs in a Dyck path, and DDUs have the Touchard distribution (A091894) with gf F(x,y) = (12x+2xy  sqrt(14x+4x^24x^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. BousquetMélou, A. Denise, P. Flajolet, D. Gardy and D. GouyouBeauchamps, Generating functions for generating trees, Discrete Mathematics 246(13), March 2002, pp. 2955.
Paul Barry, On IntegerSequenceBased 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, 226228 (1995), 5772; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226228 (1995), 5772; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
Z. Chen, H. Pan, Identities involving weighted CatalanSchroder and Motzkin Paths, arXiv:1608.02448 (2016), eq. (1.13) a=1, b=3.
C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249250.
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
N. J. A. Sloane, Transforms


FORMULA

G.f.: (1+2*xsqrt(18*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)^(nk).  Philippe Deléham, Jan 21 2004
With offset 1: a(1) = 1, a(n) = 2*a(n1) + 3*Sum_{i=1..n1} a(i)*a(ni)).  Benoit Cloitre, Mar 16 2004
a(n) = (4*(2n1)*a(n1)  4*(n2)*a(n2)) / (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/(1x/(13x/(1x/(13x/(1x/(13x/(1x/(13x........ (continued fraction).
The g.f. of a(n+1) is 1/(14x3x^2/(14x3x^2/(14x3x^2/(14x3x^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*xsqrt(18*x+4*x^2))/(6*x)= 1/G(0); G(k)= 1 + 2*x  3*x/G(k+1); (continued fraction, 1step ).  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[w1]+3*add(a[j]*a[wj1], j=1..w1) 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[n1] + 3 Sum[a[k1]a[nk], {k, n1}] ; 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[n1, 2]) + 2 KroneckerDelta[n])/(6n+3), {n, 0, 20}] (* Vladimir Reshetnikov, Nov 01 2015 *)
CoefficientList[Series[(1+2xSqrt[18x+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(n1, 2)) + 2*(n==0))/(6*n+3); \\ Michel Marcus, Nov 02 2015
(PARI) x='x+O('x^100); Vec((1+2*xsqrt(18*x+4*x^2))/(6*x)) \\ Altug Alkan, Nov 02 2015


CROSSREFS

Cf. A047891, A054872.
Sequence in context: A211855 A177249 A083882 * A218185 A086624 A261490
Adjacent sequences: A007561 A007562 A007563 * A007565 A007566 A007567


KEYWORD

nonn,nice,eigen,changed


AUTHOR

N. J. A. Sloane


STATUS

approved



