A014531 Form array in which n-th row is obtained by expanding (1+x+x^2)^n and taking the 2nd column from the center.

1, 3, 10, 30, 90, 266, 784, 2304, 6765, 19855, 58278, 171106, 502593, 1477035, 4343160, 12778152, 37616427, 110797569, 326527350, 962803170, 2840372304, 8383467708, 24755608584, 73133433800, 216143407675, 639062383401

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Number of "up" steps in all Motzkin paths of length n+1. E.g. a(2)=3 because in the four Motzkin paths of length 3, HHH, HUD, UDH and UHD, where H=(1,0), U=(1,1), D=(1,-1), we have altogether three U steps. - Emeric Deutsch, Dec 26 2003

a(n-1) = A111808(n,n-2) for n>1. - Reinhard Zumkeller, Aug 17 2005

a(n) = number of paths in the half-plane x>=0, from (0,0) to (n+1,2), and consisting of steps U=(1,1), D=(1,-1) and H=(1,0). For example, for n=2, we have the 3 paths: UUH, HUU, UHU. - José Luis Ramírez Ramírez, Apr 19 2015

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..200 from T. D. Noe)
• Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See pp. 21-22.
• Mark Shattuck, Subword Patterns in Smooth Words, Enum. Comb. Appl. (2024) Vol. 4, No. 4, Art. No. S2R32. See p. 6.
• Eric Weisstein's World of Mathematics, Trinomial Coefficient.

Crossrefs

Cf. A027907, A005717, A055151.

First differences are in A025180.

Programs

Maple

seq( add(binomial(i+1,k)*binomial(i-k+1,k+2), k=0..floor(i/2)), i=1..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
a := n -> simplify(GegenbauerC(n-1, -n-1, -1/2)):
seq(a(n), n=1..26); # Peter Luschny, May 09 2016

Mathematica

Table[Sum[Binomial[i + 1, k]*Binomial[i - k + 1, k + 2], {k, 0, Floor[i/2]}], {i, 30}] (* Michael De Vlieger, Apr 20 2015 *)
Table[GegenbauerC[n - 1, -n - 1, -1/2], {n,1,50}] (* G. C. Greubel, Feb 28 2017 *)

PARI

for(n=1,25, print1(sum(k=0,n+1, binomial(n+1,k)*binomial(n-k+1,k+2)), ", ")) \\ G. C. Greubel, Feb 28 2017

Sage

a = lambda n: n*(n+1)*hypergeometric([(1-n)/2, 1-n/2], [3], 4)/2
[simplify(a(n)) for n in (1..26)] # Peter Luschny, Nov 23 2014

Formula

a(n) = A002426(n+1)-A001006(n+1) = a(n-1)+A005717(n)+A014532(n-2) - Henry Bottomley, May 15 2001

E.g.f.: exp(x)*(2*x*BesselI(1, 2*x)+(x-2)*BesselI(2, 2*x))/x. - Vladeta Jovovic, Aug 21 2003

G.f.: [1-2z-z^2-(1-z)q]/(2z^3q), where q=sqrt(1-2z-3z^2). - Emeric Deutsch, Dec 26 2003

a(n) = Sum_{k=0..n+1} C(n+1,k)*C(n-k+1,k+2). - Paul Barry, Sep 20 2004

D-finite with recurrence (n+3)*(n-1)*a(n) -(n+1)*(2n+1)*a(n-2)-3*n*(n+1)*a(n-2)=0. - R. J. Mathar, Dec 08 2011

a(n) = n*(n+1)*hypergeom([(1-n)/2, 1-n/2], [3], 4)/2. - Peter Luschny, Nov 23 2014

G.f.: z*M(z)^2/(1-z-2*z^2*M(z)), where M(z) is the g.f. of Motzkin paths. - José Luis Ramírez Ramírez, Apr 19 2015

a(n) = GegenbauerC(n-1, -n-1, -1/2). - Peter Luschny, May 09 2016

a(n) = Sum_{k>0} k * A055151(n+1,k). - Alois P. Heinz, Mar 29 2020

Extensions

More terms from James Sellers, Feb 05 2000