A107587 Number of Motzkin n-paths with an even number of up steps.

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

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

Gennady Eremin, Table of n, a(n) for n = 0..800

Gennady Eremin, Walking in the OEIS: From Motzkin numbers to Fibonacci numbers. The "shadows" of Motzkin numbers, arXiv:2108.10676 [math.CO], 2021.

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

a(n) = Sum_{k=0..n} binomial(n, 4*k) * A000108(2*k). - Gennady Eremin, Jan 19 2021

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)
A107587 = [1, 1, 1, 1, 3]
for n in range(5, 801):
    A107587.append(((5*n**2+n-3)*A107587[-1]-(10*n**2-16*n+3)*A107587[-2]
      +(10*n**2-34*n+27)*A107587[-3]+(11*n-5)*(n-3)*A107587[-4]
      -15*(n-3)*(n-4)*A107587[-5])//(n*n+2*n)) # Gennady Eremin, Mar 25 2021

Crossrefs

Cf. A000108, A001006, A048990.

Sequence in context: A097081 A093406 A376835 * A245931 A190590 A341705

Adjacent sequences: A107584 A107585 A107586 * A107588 A107589 A107590

Keyword

easy,nonn

Author

Paul Barry, May 16 2005

Extensions

New name (after email conversations with Gennady Eremin) from Sergey Kirgizov, Mar 25 2021

Status

approved