A343386 - OEIS

%I #31 Apr 27 2024 03:38:45

%S 0,0,1,3,6,10,20,56,168,456,1137,2827,7458,20670,57577,157691,427976,

%T 1170552,3248411,9096497,25505562,71436182,200338074,564083786,

%U 1595055520,4522769520,12842772295,36514010301,103995490758,296794937626,848620165860,2430089817720

%N Number of odd Motzkin n-paths, i.e., Motzkin n-paths with an odd number of up steps.

%C a(n) is the number of Motzkin n-paths with an odd number of U-steps (see A001006). For example, there are 9 Motzkin 4-paths, of which six have one U-step each, namely: 00UD, 0U0D, 0UD0, U00D, U0D0, and UD00. So a(4) = 6.

%C Number of Motzkin n-paths that, after removing the horizontal steps, are converted to Dyck (2m)-paths, where 2m <= n and m is odd (see A024492).

%H Gennady Eremin, <a href="/A343386/b343386.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 a(n) = Sum_{k=0..n} binomial(n, 4*k+2) * A000108(2*k+1).

%F a(n) = A001006(n) - A107587(n).

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

%F G.f. A(x) satisfies A(x) = x*A(x) + x^2*A(x)^2 + x^2*B(x)^2 where B(x) is the g.f. of A107587.

%F a(n) = A107587(n) - A100223(n+2). - _R. J. Mathar_, Apr 16 2021

%F D-finite with recurrence: 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, n >= 5. - _R. J. Mathar_, Apr 17 2021

%F D-finite with recurrence: 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, n >= 4. - _R. J. Mathar_, Apr 17 2021

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k) * A000108(k) * (k mod 2). - _Gennady Eremin_, May 03 2021 [after _Paul Barry_ (A107587)]

%F a(n) = ((n-1)*n*hypergeom([1/2-n/4, 3/4-n/4, 1-n/4, 5/4-n/4], [3/2, 3/2, 2], 16))/2. - _Peter Luschny_, Sep 24 2021

%F a(n) ~ 3^(n + 3/2) / (4*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Apr 27 2024

%e G.f. = x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 20*x^6 + 56*x^7 + 168*x^8 + ...

%t a[n_] := ((n - 1) n HypergeometricPFQ[{1/2 - n/4, 3/4 - n/4, 1 - n/4, 5/4 - n/4}, {3/2, 3/2, 2}, 16])/2;

%t Table[a[n], {n, 0, 31}] (* _Peter Luschny_, Sep 24 2021 *)

%o (Python)

%o M = [4, 9]; E = [1, 1, 1, 1, 3];

%o A343386 = [0, 0, 1, 3, 6]

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

%o     M.append(((2*n+1)*M[1]+(3*n-3)*M[0])//(n+2))

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

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

%o       - 15*(n-3)*(n-4)*E[0]) // (n*n+2*n))

%o     A343386.append(M[-1] - E[-1])

%o     M.pop(0); E.pop(0)

%Y Cf. A000108, A001006, A107587, A024492, A100223.

%K nonn,easy

%O 0,4

%A _Gennady Eremin_, _Sergey Kirgizov_, Apr 13 2021