A307555 -id:A307555 - cp's OEIS frontend

A325921 Number of Motzkin meanders of length n with an even number of humps and an even number of peaks.

1, 2, 4, 8, 17, 38, 92, 239, 653, 1832, 5192, 14726, 41683, 117822, 333312, 945952, 2698117, 7740920, 22337788, 64788768, 188683267, 551179370, 1613612996, 4731245903, 13888157307, 40804653640, 119984904744, 353085202434, 1039830559085, 3064566227434

Offset: 0

Andrei Asinowski, Jun 27 2019

nonn

A Motzkin meander is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), and never goes below the x-axis.
A peak is an occurrence of the pattern UD.
A hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).

			For n=0, 1, 2, 3 there are 2^n paths: all the paths without D (0 humps, 0 peaks).
For example, for n=3: UUU, UUH, UHU, UHH, HUU, HUH, HHU, HHH.
For n=4, the "extra" path is UDUD (2 humps, 2 peaks).
The smallest example with #(humps) <> #(peaks) is UHDUHD (2 humps, 0 peaks).

Alois P. Heinz, Table of n, a(n) for n = 0..2100
Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Algorithmica (2019).

Cf. A307572, A325922.

b:= proc(x, y, t, p, h) option remember; `if`(x=0, `if`(p+h=0, 1, 0),
      `if`(y>0, b(x-1, y-1, 0, irem(p+`if`(t=1, 1, 0), 2), irem(h+
      `if`(t=2, 1, 0), 2)), 0)+b(x-1, y, `if`(t>0, 2, 0), p, h)+
         b(x-1, y+1, 1, p, h))
    end:
a:= n-> b(n, 0$4):
seq(a(n), n=0..35);  # Alois P. Heinz, Jul 03 2019

CoefficientList[Series[(1/(8*x))*((-1 + 4*x - 3*x^2 + Sqrt[(-(-1 + x)^2)* (-1 + 2*x + 3*x^2)])/ (1 - 4*x + 3*x^2) - (-1 + 4*x - 5*x^2 + 2*x^3 + Sqrt[(-1 + x)^3*(-1 + x + 4*x^3)])/((-1 + x)^2* (-1 + 2*x)) + (-1 + 4*x - 5*x^2 + Sqrt[1 - 4*x + 6*x^2 - 4*x^3 + 5*x^4])/ (1 - 4*x + 5*x^2) + (-1 + 4*x - 3*x^2 - 2*x^3 + Sqrt[1 - 4*x + 2*x^2 + 8*x^3 - 11*x^4 + 4*x^5 + 4*x^6])/(1 - 4*x + 3*x^2 + 2*x^3)), {x, 0, 30}], x] (* Vaclav Kotesovec, Jul 03 2019 *)

G.f.: ( (-1+4*t-3*t^2+sqrt(-3*t^4+4*t^3+2*t^2-4*t+1))/(3*t^2-4*t+1) + (-1+4*t-5*t^2+2*t^3+sqrt(4*t^6-12*t^5+13*t^4-8*t^3+6*t^2-4*t+1))/(-2*t^3+5*t^2-4*t+1) + (-1+4*t-5*t^2+sqrt(5*t^4-4*t^3+6*t^2-4*t+1))/(5*t^2-4*t+1) + (-1+4*t-3*t^2-2*t^3+sqrt(4*t^6+4*t^5-11*t^4+8*t^3+2*t^2-4*t+1))/(2*t^3+3*t^2-4*t+1) ) / (8*t).
a(n) ~ 3^(n + 1/2) / (4*sqrt(Pi*n)). - Vaclav Kotesovec, Jul 03 2019
a(n) + A325923(n) = A307575(n). - R. J. Mathar, Jan 25 2023
a(n) + A325925(n) = A307555(n). - R. J. Mathar, Jan 25 2023

A307557 Number of Motzkin meanders of length n with no level steps at odd level.

Original entry on oeis.org

1, 2, 4, 9, 20, 47, 110, 264, 634, 1541, 3754, 9204, 22622, 55817, 138026, 342203, 849984, 2115245, 5271970, 13158944, 32886338, 82285031, 206101422, 516728937, 1296664512, 3256472235, 8184526438, 20584627358, 51805243138, 130456806425, 328703655114

Offset: 0

Andrei Asinowski, Apr 14 2019

nonn

A Motzkin meander is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), and never goes below the x-axis.

			For n = 3 the a(3) = 9 paths are UUU, UUH, UUD, UDU, UDH, HUU, HUD, HHU, HHH.

Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Algorithmica (2019).

Cf. A307555.

G.f.: ((1+t)/sqrt((t-1)*(4*t^2+t-1)) -1) / (2*t).
D-finite with recurrence (n+1)*a(n) +(-n-2)*a(n-1) +(-5*n+3)*a(n-2) +(n+4)*a(n-3) +2*(2*n-5)*a(n-4)=0. - R. J. Mathar, Jan 25 2023
a(n) ~ sqrt(13 + 53/sqrt(17)) * (1 + sqrt(17))^n / (sqrt(Pi*n) * 2^(n + 3/2)). - Vaclav Kotesovec, Jun 24 2023
a(n) = (A026569(n) + A026569(n+1))/2. - Mark van Hoeij, Nov 29 2024

cp's OEIS Frontend

A325921 Number of Motzkin meanders of length n with an even number of humps and an even number of peaks.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula