|
| |
|
|
A307555
|
|
Number of Motzkin meanders of length n with an even number of humps.
|
|
2
|
|
|
|
1, 2, 4, 8, 17, 40, 106, 307, 927, 2818, 8480, 25142, 73555, 213204, 615074, 1773036, 5121195, 14843518, 43190084, 126112096, 369264395, 1083378784, 3182684838, 9357797643, 27529874201, 81028448678, 238599098824, 702932296258, 2072003987285, 6111009331876
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
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 hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: (sqrt((-t^2+1)/(3*t^2-4*t+1))+sqrt((t^2+1)/(5*t^2-4*t+1))-2)/(4*t).
D-finite with recurrence -3*(n+1)*(n-2)*a(n) +12*(2*n^2-4*n-1)*a(n-1) +2*(-35*n^2+107*n-48)*a(n-2) +4*(21*n^2-89*n+80)*a(n-3) +4*(-5*n^2+32*n-43)*a(n-4) +4*(-8*n^2+62*n-115)*a(n-5) +2*(31*n^2-283*n+616)*a(n-6) -4*(23*n-97)*(n-6)*a(n-7) +15*(n-6)*(n-7)*a(n-8)=0. - R. J. Mathar, Jan 25 2023
|
|
|
EXAMPLE
|
For n = 3, the a(3) = 8 paths are HHH, HHU, HUH, HUU, UHH, UHU, UUU.
For n=5, there are a(5) = 40 paths: 32 paths with no humps, {H, U}^5; and 8 paths with two humps, HUDUD, UDHUD, UDUDH, UDUDU, UDUHD, UDUUD, UHDUD, UUDUD.
|
|
|
MAPLE
|
a:=gfun[rectoproc]({(15*n^2+45*n+30)*u(n)+(-92*n^2-532*n-696)*u(n+1)+(62*n^2+426*n+672)*u(n+2)+(-32*n^2-264*n-524)*u(n+3)+(-20*n^2-192*n-428)*u(n+4)+(84*n^2+988*n+2848)*u(n+5)+(-70*n^2-906*n-2864)*u(n+6)+(24*n^2+336*n+1140)*u(n+7)+(-3*n^2-45*n-162)*u(n+8), u(0) = 1, u(1) = 2, u(2) = 4, u(3) = 8, u(4) = 17, u(5) = 40, u(6) = 106, u(7) = 307}, u(n), remember):
seq(a(n), n=0..30);
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
