login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A107587 Number of Motzkin n-paths with an even number of up steps. 2
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,4,... (see A048990).

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

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

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: A071568 A097081 A093406 * 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 7 15:48 EDT 2021. Contains 343651 sequences. (Running on oeis4.)