A089372 Number of Motzkin paths of length n with no peaks at level 1.

1, 1, 1, 2, 5, 12, 29, 72, 183, 473, 1239, 3282, 8777, 23665, 64261, 175584, 482395, 1331795, 3692891, 10280190, 28719659, 80493514, 226268539, 637767720, 1802113489, 5103874135, 14485789561, 41194844114, 117366166381

Offset

0,4

Comments

Number of Motzkin paths starting with a maximal run of an even number of up-steps. - Alexander Burstein, Jan 30 2024

Number of compositions of n where there are [1, 0, 1, 2, 4, 9, 21, 51, 127, 323,...] (cf. A001006) sorts of part k (k>=1). - Joerg Arndt, Jan 31 2024

Links

Fung Lam, Table of n, a(n) for n = 0..2000

E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hill-free generalized Motzkin paths, Séminaire Lotharingien de Combinatoire, B46b (2001), 14 pp.

Qiang-Hui Guo, L. H. Sun, and J. Wang, Regular Simple Queues of Protein Contact Maps, Bulletin of Mathematical Biology, 2016, January 2017, Volume 79, Issue 1, pp 21-35.

Formula

G.f.: (1-z-q)/(z^2*(3-z-q)), where q = sqrt(1-2*z-3*z^2).

a(n) = sum(k=1..(n+3)/2, (k*sum(j=0..n-k+3, binomial(j,n-j+3)*binomial(n-k+3,j)))/(n-k+3)*(-1)^(k-1)). - Vladimir Kruchinin, Oct 22 2011

G.f.: 1/(1-z-z^3*M-z^4*M^2), where M is the g.f. of the Motzkin Numbers. - José Luis Ramírez Ramírez, Jan 28 2013

Recurrence: 2*(n+2)*a(n) = 3*(n-1)*a(n-4) + (4-n)*a(n-3) + 3*(n-3)*a(n-2) + (5*n+4)*a(n-1). - Fung Lam, Feb 03 2014

Asymptotics: a(n) ~ 3^(n+4)/(2^5*sqrt(3*Pi*n^3)). - Fung Lam, Mar 31 2014

From Alexander Burstein, Jan 30 2024: (Start)

G.f.: M/(1+z^2*M), where M = M(z) is the g.f. of the Motzkin numbers, A001006.

G.f.: (1+M)/(2-z+z^2), where M = M(z) is the g.f. of the Motzkin numbers, A001006.

2*a(n) - a(n-1) + a(n-2) = A001006(n) + (1 if n=0), where we let a(n)=0 if n<0. (End)

Example

a(4)=5 because the Motzkin paths of length 4 with no peaks at level 1 are: HHHH, HUHD, UHDH, UHHD, and UUDD, where H=(1,0), U=(1,1) and D=(1,-1).
a(4)=5 because the Motzkin paths of length 4 starting with a maximal run of an even number of up-steps U are: HHHH, HHUD, HUHD, HUDH, and UUDD, where H=(1,0), U=(1,1) and D=(1,-1). - Alexander Burstein, Jan 30 2024

Mathematica

CoefficientList[Series[(1-x-Sqrt[1-2*x-3*x^2])/(x^2*(3-x-Sqrt[1-2*x-3*x^2])), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 31 2014 *)

Prog

(Maxima)
a(n):=sum((k*sum(binomial(j, n-j+3)*binomial(n-k+3, j), j, 0, n-k+3))/(n-k+3)*(-1)^(k-1), k, 1, (n+3)/2); /* Vladimir Kruchinin, Oct 22 2011 */

Crossrefs

Cf. A001006.

Sequence in context: A307788 A025273 A217333 * A036671 A152171 A132807

Adjacent sequences: A089369 A089370 A089371 * A089373 A089374 A089375

Keyword

nonn

Author

Emeric Deutsch, Dec 27 2003

Status

approved