A026107 Second differences of Motzkin numbers (A001006).

1, 3, 7, 18, 46, 120, 316, 841, 2257, 6103, 16611, 45475, 125139, 345957, 960417, 2676291, 7483299, 20989833, 59042805, 166520124, 470781528, 1333970190, 3787707322, 10775741271, 30711538351, 87677551081, 250704001213, 717923179762

Offset: 2

Author

Clark Kimberling

Keywords

• nonn

Comments

Number of (s(0), s(1), ..., s(n)) such that every s(i) is a nonnegative integer, s(0) = 0, s(1) = 1 = s(n), |s(i) - s(i-1)| <= 1 for i >= 2. Also a(n) = T(n,n-1), where T is array in A026105 and U(n,n+1), where U is array in A026120.

Also number of (s(0),s(1),...,s(n)) such that every s(i) is a nonnegative integer, s(0) = 1, s(n) = 0, |s(1) - s(0)| = 1, |s(i) - s(i-1)| <= 1 for i >= 2.

Number of Motzkin paths of length n+1 that start with a (1,1) step and end with a (1,-1) step. - Emeric Deutsch, Jul 11 2001

Equals iterates of M * [1,1,1,1,0,0,0,...] where M = an infinite tridiagonal matrix with [0,1,1,1,...] in the main diagonal and [1,1,1,...] in the super- and subdiagonals. - Gary W. Adamson, Jan 08 2009

Number of Motzkin paths of length n-1 that are allowed to go down to the line y=-1 [He-Shapiro, page 38]. - R. J. Mathar, Jul 23 2017

With offset 1, a[n] = [x^n](1 + x + x^2)^n - [x^(n-4)](1 + x + x^2)^n, that is, the difference between the n-th central trinomial coefficient and its fourth predecessor. For example, with n = 4, (1 + x + x^2)^4 = 1 + 4*x + 10*x^2 + 16*x^3 + 19*x^4 + 16*x^5 + 10*x^6 + 4*x^7 + x^8 and a(4) = 19 - 1. - David Callan, Dec 18 2021

Links

• T.-X. He and L. W. Shapiro, Fuss-Catalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group, Lin. Alg. Applic. 532 (2017) 25-41.

Crossrefs

Cf. A001006. First differences of A002026.

Cf. A026122.

Formula

a(n) = A001006(n+1) - 2*A001006(n) + A001006(n-1).

The sequence 1,1,3,7,18,... has a(n) = Sum_{k=0..n} binomial(n,2k)*A000108(k+1). - Paul Barry, Jul 18 2003

G.f.: ((1-z)^2*M - 1 + z - z^2)/z, where M is the generating function of the Motzkin sequence A001006 (M = 1 + z*M + z^2*M^2).

(n+3)*a(n) + 3*(-n-1)*a(n-1) + (-n-3)*a(n-2) + 3*(n-3)*a(n-3) = 0. - R. J. Mathar, Nov 26 2012

a(n) ~ 2 * 3^(n + 1/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 17 2019

With offset 0 and a(0) = 1 prepended (see Paul Barry's formula above), a(n) = hypergeom([3/2, (1 - n)/2, -n/2], [1/2, 3], 4). - Peter Luschny, Dec 19 2021

Extensions

Simpler definition from Ralf Stephan, Dec 16 2004