login
A089372
Number of Motzkin paths of length n with no peaks at level 1.
7
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
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.
Emily Barnard, Colin Defant, and Eric J. Hanson, Pop-Stack for Cambrian Lattices, Ruhr-Univ. (FPSAC, Germany 2024). See slide 13.
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
MAPLE
gf := 2 / (x*(2*x - 1) + sqrt((1 - 3*x)*(x + 1)) + 1):
ser := series(gf, x, 30): seq(coeff(ser, x, n), n = 0..28);
# Peter Luschny, Oct 12 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 */
(Python)
import sympy as sp
def aupto(n):
x = sp.symbols('x')
expr = (1 - x - sp.sqrt(1 - 2*x - 3*x**2)) / (x**2 * (3 - x - sp.sqrt(1 - 2*x - 3*x**2)))
series_expr = sp.series(expr, x, 0, n).removeO()
return sp.Poly(series_expr, x).all_coeffs()[::-1] # Paul Muljadi, Oct 10 2024
(PARI) my(z='z+O('z^33), q=sqrt(1-2*z-3*z^2)); Vec((1-z-q)/(z^2*(3-z-q))) \\ Joerg Arndt, Oct 13 2024
CROSSREFS
Cf. A001006.
Sequence in context: A307788 A025273 A217333 * A036671 A152171 A132807
KEYWORD
nonn,changed
AUTHOR
Emeric Deutsch, Dec 27 2003
STATUS
approved