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

Author

Paul Barry, May 16 2005

Keywords

• easy
• nonn

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

Examples

			G.f. = 1 + x + x^2 + x^3 + 3*x^4 + 11*x^5 + 31*x^6 + 71*x^7 + 155*x^8 + ...
		

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.

Crossrefs

Cf. A000108, A001006, A048990.

Programs

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

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

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

Extensions

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