|
|
A187256
|
|
Number of peakless Motzkin paths of length n, assuming that the (1,0)-steps come in 2 colors.
|
|
3
|
|
|
1, 2, 4, 10, 28, 82, 248, 770, 2440, 7858, 25644, 84618, 281844, 946338, 3199728, 10885122, 37230352, 127951714, 441633812, 1530242954, 5320853260, 18560408050, 64932101224, 227767796482, 800928670232, 2822814469394, 9969770245948, 35280714655498
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Ordinary peakless Motzkin paths are counted by A004148.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: G(z) satisfies the equation G = 1 + 2*z*G + z^2*G*(G-1).
Conjecture: (n+2)*a(n) -2*(2*n+1)*a(n-1) +2*(n-1)*a(n-2) +2*(5-2*n)*a(n-3) +(n-4)*a(n-4) = 0. - R. J. Mathar, Nov 16 2011
a(n) = Sum_{i=0..n/2} ((-1)^i*binomial(n-i,i)*binomial(2*n-4*i+2,n-2*i))/(n-2*i+1)). - Vladimir Kruchinin, Jun 01 2014
a(n) ~ sqrt(24+14*sqrt(3)) * (2+sqrt(3))^n / (2*sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jun 02 2014
a(n) = 2^n*hypergeom([-n/2, (1 - n)/2, (1 - n)/2, 1 - n/2], [2, -n, -n + 1], 4). - Peter Luschny, Jan 25 2020
|
|
EXAMPLE
|
a(4)=28 because, denoting U=(1,1), D=(1,-1), and H=(1,0), we have 2^4=16 paths of shape HHHH, 2^2=4 paths of shape HUHD, 2^2 = 4 paths of shape UHDH, and 4 paths of shape UHHD.
|
|
MAPLE
|
eq := G = 1+2*z*G+z^2*G*(G-1): G := RootOf(eq, G): Gser := series(G, z = 0, 30): seq(coeff(Gser, z, n), n = 0 .. 27);
|
|
MATHEMATICA
|
CoefficientList[Series[(1 + (x-2)*x - Sqrt[(1 + (x-4)*x)*(1+x^2)])/(2*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Jun 02 2014 *)
a[n_] := 2^n HypergeometricPFQ[{-n/2, (1 - n)/2, (1 - n)/2, 1 - n/2}, {2, -n, -n + 1}, 4]; Array[a, 28, 0] (* Peter Luschny, Jan 25 2020 *)
|
|
PROG
|
(Maxima)
a(n):=sum(((-1)^i*binomial(n-i, i)*binomial(2*n-4*i+2, n-2*i))/(n-2*i+1), i, 0, (n)/2); /* Vladimir Kruchinin, Jun 01 2014 */
(PARI) my(x='x+O('x^50)); Vec((1 + (x-2)*x - sqrt((1 + (x-4)*x)*(1+x^2))) /( 2*x^2)) \\ G. C. Greubel, Feb 12 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|