A107587 - OEIS

%I #81 Sep 19 2021 08:54:53

%S 1,1,1,1,3,11,31,71,155,379,1051,2971,8053,21165,56057,152881,425491,

%T 1186227,3287971,9102787,25346457,71111377,200425149,565676629,

%U 1597672277,4520632981,12827046181,36493762501,104027787451,296947847203,848765305351,2429671858671

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

%C 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]

%C 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

%H Gennady Eremin, <a href="/A107587/b107587.txt">Table of n, a(n) for n = 0..800</a>

%H Gennady Eremin, <a href="https://arxiv.org/abs/2108.10676">Walking in the OEIS: From Motzkin numbers to Fibonacci numbers. The "shadows" of Motzkin numbers</a>, arXiv:2108.10676 [math.CO], 2021.

%F G.f.: A(x) = (sqrt(1 - 2*x + 5*x^2) - sqrt(1 - 2*x - 3*x^2))/(4*x^2).

%F 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

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k) * A000108(k) * ((k+1) mod 2).

%F a(n) = Sum_{k=0..n} binomial(n, 4*k) * A000108(2*k). - _Gennady Eremin_, Jan 19 2021

%F 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]

%F 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]

%F 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

%F 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

%F Sum_{n>=0} 1/a(n) = 4.481162666556140691601309195776026399507565017... - _Gennady Eremin_, Jul 27 2021

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

%t CoefficientList[Series[(Sqrt[1 - 2*x + 5*x^2] - Sqrt[1 - 2*x - 3*x^2])/(4*x^2), {x, 0, 30}], x] (* or *)

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

%o (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

%o (Python)

%o A107587 = [1, 1, 1, 1, 3]

%o for n in range(5, 801):

%o     A107587.append(((5*n**2+n-3)*A107587[-1]-(10*n**2-16*n+3)*A107587[-2]

%o       +(10*n**2-34*n+27)*A107587[-3]+(11*n-5)*(n-3)*A107587[-4]

%o       -15*(n-3)*(n-4)*A107587[-5])//(n*n+2*n)) # _Gennady Eremin_, Mar 25 2021

%Y Cf. A000108, A001006, A048990.

%K easy,nonn

%O 0,5

%A _Paul Barry_, May 16 2005

%E New name (after email conversations with Gennady Eremin) from _Sergey Kirgizov_, Mar 25 2021