|
|
A107587
|
|
Number of Motzkin n-paths with an even number of up steps.
|
|
5
|
|
|
1, 1, 1, 1, 3, 11, 31, 71, 155, 379, 1051, 2971, 8053, 21165, 56057, 152881, 425491, 1186227, 3287971, 9102787, 25346457, 71111377, 200425149, 565676629, 1597672277, 4520632981, 12827046181, 36493762501, 104027787451, 296947847203, 848765305351, 2429671858671
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Binomial transform of 1,0,0,0,2,0,0,0,14,0,0,0,132,... (see A048990). [Corrected by John Keith, May 10 2021]
Number of Motzkin n-paths with only steps F=(1,0) or with an even number of steps U=(1,1) and, accordingly, D=(1,-1) (see A001006). For example, there are 9 Motzkin 4-paths, namely: FFFF, FFUD, FUFD, FUDF, UFFD, UFDF, UUDD, UDFF, and UDUD. We have one path with only F's and two paths with two U's and two D's: UUDD, UDUD. So a(4) = 1 + 2 = 3. - Gennady Eremin, Jan 19 2021
|
|
LINKS
|
|
|
FORMULA
|
G.f.: A(x) = (sqrt(1 - 2*x + 5*x^2) - sqrt(1 - 2*x - 3*x^2))/(4*x^2).
G.f.: A(x) satisfies A(x) = 1 + x*A(x) + 2*x^2*A(x)*(M(x) - A(x)) where M(x) is the g.f. for Motzkin numbers A001006 (personal conversation with Gennady Eremin). - Sergey Kirgizov, Mar 23 2021
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k) * A000108(k) * ((k+1) mod 2).
Conjecture: n*(n+2)*a(n) + (-5*n^2-n+3)*a(n-1) + (10*n^2-16*n+3)*a(n-2) + (-10*n^2+34*n-27)*a(n-3) - (11*n-5)*(n-3)*a(n-4) + 15*(n-3)*(n-4)*a(n-5) = 0. - R. J. Mathar, Feb 20 2015 [conjecture is true for n = 0..800; checked by Gennady Eremin, Jan 25 2021]
Conjecture: n*(n-2)*(n+2)*a(n) - (2*n-1)*(2*n^2-2*n-3)*a(n-1) + 3*(n-1)*(2*n^2-4*n+1)*a(n-2) - 2*(n-1)*(n-2)*(2*n-3)*a(n-3) - 15*(n-1)*(n-2)*(n-3)*a(n-4) = 0. - R. J. Mathar, Feb 20 2015 [conjecture is true for n = 0..800; checked by Gennady Eremin, Jan 25 2021]
a(n) = hypergeom([1/4 - n/4, 1/2 - n/4, 3/4 - n/4, -n/4], [1/2, 1, 3/2], 16). - Vaclav Kotesovec, Feb 07 2021
G.f.: A(x) satisfies 2*x^2*A(x)^2 + sqrt(1-2*x-3*x^2)*A(x) = 1 (discussion with Sergey Kirgizov). - Gennady Eremin, Mar 30 2021
Sum_{n>=0} 1/a(n) = 4.481162666556140691601309195776026399507565017... - Gennady Eremin, Jul 27 2021
|
|
EXAMPLE
|
G.f. = 1 + x + x^2 + x^3 + 3*x^4 + 11*x^5 + 31*x^6 + 71*x^7 + 155*x^8 + ...
|
|
MATHEMATICA
|
CoefficientList[Series[(Sqrt[1 - 2*x + 5*x^2] - Sqrt[1 - 2*x - 3*x^2])/(4*x^2), {x, 0, 30}], x] (* or *)
Table[HypergeometricPFQ[{1/4 - n/4, 1/2 - n/4, 3/4 - n/4, -n/4}, {1/2, 1, 3/2}, 16], {n, 0, 30}] (* Vaclav Kotesovec, Feb 07 2021 *)
|
|
PROG
|
(PARI) my(x='x+O('x^35)); Vec((sqrt(1-2*x+5*x^2)-sqrt(1-2*x-3*x^2))/(4*x^2)) \\ Michel Marcus, Jan 20 2021
(Python)
for n in range(5, 801):
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
New name (after email conversations with Gennady Eremin) from Sergey Kirgizov, Mar 25 2021
|
|
STATUS
|
approved
|
|
|
|