A325922 -id:A325922 - 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

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

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 14, 68, 274, 986, 3288, 10416, 31872, 95382, 281762, 827084, 2423078, 7102598, 20852296, 61323328, 180581128, 532199414, 1569071842, 4626551740, 13641716894, 40223795038, 118614194080, 349847093824, 1032173428200

Offset: 0

Andrei Asinowski, Jul 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.
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=5, the a(5)=2 paths are UDUHD and UHDUD (2 humps, 1 peak).
For n=6, we have a(6)=14 paths: 6 paths obtained by a permutation of {UD, UHD, H}, 6 paths obtained by a permutation of {UD, UHD, U}, and 2 paths obtained by a permutation of {UD, UHHD}.

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).

Motzkin meanders and excursions with restrictions on the number of humps and peaks:
A325921: Meanders, #humps=EVEN, #peaks=EVEN.
A325922: Excursions, #humps=EVEN, #peaks=EVEN.
A325923: Meanders, #humps=ODD, #peaks=EVEN.
A325924: Excursions, #humps=ODD, #peaks=EVEN.
A325925 (this sequence): Meanders, #humps=EVEN, #peaks=ODD.
A325926: Excursions, #humps=EVEN, #peaks=ODD.
A325927: Meanders, #humps=ODD, #peaks=ODD.
A325928: Excursions, #humps=ODD, #peaks=ODD.

CoefficientList[Series[(Sqrt[(1 + x)/(1 - 3*x)] - Sqrt[(1 + x + 2*x^2)/((1 - 2*x)*(1 - x))] + Sqrt[(1 + x^2)/(1 - 4*x + 5*x^2)] - Sqrt[(1 - x^2 + 2*x^3)/((1 - 2*x)*(1 - 2*x - x^2))])/(8*x), {x, 0, 20}], x] (* Vaclav Kotesovec, Aug 09 2019 *)

G.f.: ( sqrt((1+t)/(1-3*t)) - sqrt((1+t+2*t^2)/((1-2*t)*(1-t))) + sqrt((1+t^2)/(1-4*t+5*t^2)) - sqrt((1-t^2+2*t^3)/((1-2*t)*(1-t^2-2*t))) ) / (8*t).

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

A325926 Number of Motzkin excursions of length n with an even number of humps and an odd number of peaks.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 8, 26, 76, 212, 568, 1504, 3968, 10526, 28192, 76398, 209268, 578396, 1609376, 4499336, 12620080, 35482718, 99958776, 282107702, 797637908, 2259545652, 6413273704, 18238099464, 51963195440, 148315593178, 424034498656, 1214186436154

Offset: 0

Andrei Asinowski, Jul 14 2019

nonn

A Motzkin excursion is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), never goes below the x-axis, and terminates at the altitude 0.
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=5, the a(5)=2 paths are UDUHD and UHDUD (2 humps, 1 peak).
For n=6, we have a(6)=8 paths: 6 paths obtained by a permutation of {UD, UHD, H}, and 2 paths obtained by a permutation of {UD, UHHD}.

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).

Motzkin meanders and excursions with restrictions on the number of humps and peaks:
A325921: Meanders, #humps=EVEN, #peaks=EVEN.
A325922: Excursions, #humps=EVEN, #peaks=EVEN.
A325923: Meanders, #humps=ODD, #peaks=EVEN.
A325924: Excursions, #humps=ODD, #peaks=EVEN.
A325925: Meanders, #humps=EVEN, #peaks=ODD.
A325926 (this sequence): Excursions, #humps=EVEN, #peaks=ODD.
A325927: Meanders, #humps=ODD, #peaks=ODD.
A325928: Excursions, #humps=ODD, #peaks=ODD.

CoefficientList[Series[(1/(8*(1 - x)*x^2))* (-Sqrt[(1 - 3*x)*(1 - x)^2*(1 + x)] + Sqrt[(1 - 2*x)*(1 - x)^3*(1 + x + 2*x^2)] - Sqrt[(1 + x^2)*(1 - 4*x + 5*x^2)] + Sqrt[(1 - 2*x)*(1 - 2*x - x^2)*(1 - x^2 + 2*x^3)]), {x, 0, 20}], x] (* Vaclav Kotesovec, Aug 09 2019 *)

G.f.: ( -sqrt((1-t)^2*(1+t)*(1-3*t)) + sqrt((1-2*t)*(1+t+2*t^2)*(1-t)^3) - sqrt((1+t^2)*(1-4*t+5*t^2)) + sqrt((1-2*t)*(1-2*t-t^2)*(1-t^2+2*t^3)) ) / (8*t^2*(1-t)).

a(n) ~ 3^(n + 3/2) / (8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 09 2019

A325927 Number of Motzkin meanders of length n with an odd number of humps and an odd number of peaks.

Original entry on oeis.org

0, 0, 1, 4, 13, 38, 105, 280, 737, 1942, 5183, 14100, 39151, 110642, 316751, 914248, 2650655, 7701562, 22400559, 65203428, 189970159, 554165922, 1619018259, 4737859512, 13887657307, 40769959314, 119849273449, 352716050428, 1039027117929

Offset: 0

Andrei Asinowski, Aug 10 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=3, the a(3)=4 paths are UDH, UDU, UUD, HUD (1 hump, 1 peak).

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).

Motzkin meanders and excursions with parity restrictions on the number of humps and peaks:
A325921: Meanders, #humps=EVEN, #peaks=EVEN.
A325922: Excursions, #humps=EVEN, #peaks=EVEN.
A325923: Meanders, #humps=ODD, #peaks=EVEN.
A325924: Excursions, #humps=ODD, #peaks=EVEN.
A325925: Meanders, #humps=EVEN, #peaks=ODD.
A325926: Excursions, #humps=EVEN, #peaks=ODD.
A325927  (this sequence): Meanders, #humps=ODD, #peaks=ODD.
A325928: Excursions, #humps=ODD, #peaks=ODD.

seq(n)={my(t='x + O('x*'x^n)); Vec(( sqrt((1+t)/(1-3*t)) - sqrt((1+t+2*t^2)/((1-2*t)*(1-t))) - sqrt((1+t^2)/(1-4*t+5*t^2)) + sqrt((1-t^2+2*t^3)/((1-2*t)*(1-t^2-2*t))) ) / (8*t), -n)} \\ Andrew Howroyd, Aug 12 2019

G.f.: ( sqrt((1+t)/(1-3*t)) - sqrt((1+t+2*t^2)/((1-2*t)*(1-t))) - sqrt((1+t^2)/(1-4*t+5*t^2)) + sqrt((1-t^2+2*t^3)/((1-2*t)*(1-t^2-2*t))) ) / (8*t).

A325928 Number of Motzkin excursions of length n with an odd number of humps and an odd number of peaks.

Original entry on oeis.org

0, 0, 1, 2, 4, 8, 17, 36, 83, 202, 519, 1382, 3766, 10352, 28551, 78756, 217224, 599542, 1657983, 4598766, 12803044, 35785664, 100412731, 282753476, 798690091, 2262087814, 6421507153, 18265543282, 52047980674, 148554917816, 424656556001, 1215691192244

Offset: 0

Andrei Asinowski, Aug 10 2019

nonn

A Motzkin excursion is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), never goes below the x-axis, and terminates at the altitude 0.
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=4, the a(4)=4 paths are UDHH, HUDH, HHUD, and UUDD (1 hump, 1 peak).

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).

Motzkin meanders and excursions with parity restrictions on the number of humps and peaks:
A325921: Meanders, #humps=EVEN, #peaks=EVEN.
A325922: Excursions, #humps=EVEN, #peaks=EVEN.
A325923: Meanders, #humps=ODD, #peaks=EVEN.
A325924: Excursions, #humps=ODD, #peaks=EVEN.
A325925: Meanders, #humps=EVEN, #peaks=ODD.
A325926: Excursions, #humps=EVEN, #peaks=ODD.
A325927: Meanders, #humps=ODD, #peaks=ODD.
A325928 (this sequence): Excursions, #humps=ODD, #peaks=ODD.

seq(n)={my(t='x + O('x*'x^n)); Vec(-1/2 + ( -sqrt((1-t)^2*(1+t)*(1-3*t)) + sqrt((1-2*t)*(1+t+2*t^2)*(1-t)^3) + sqrt((1+t^2)*(1-4*t+5*t^2)) - sqrt((1-2*t)*(1-2*t-t^2)*(1-t^2+2*t^3)) ) / (8*t^2*(1-t)), -n)} \\ Andrew Howroyd, Aug 12 2019

G.f.: -1/2 + ( -sqrt((1-t)^2*(1+t)*(1-3*t)) + sqrt((1-2*t)*(1+t+2*t^2)*(1-t)^3) + sqrt((1+t^2)*(1-4*t+5*t^2)) - sqrt((1-2*t)*(1-2*t-t^2)*(1-t^2+2*t^3)) ) / (8*t^2*(1-t))

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A325926 Number of Motzkin excursions of length n with an even number of humps and an odd number of peaks.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A325927 Number of Motzkin meanders of length n with an odd number of humps and an odd number of peaks.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A325928 Number of Motzkin excursions of length n with an odd number of humps and an odd number of peaks.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula