login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A343386
Number of odd Motzkin n-paths, i.e., Motzkin n-paths with an odd number of up steps.
4
0, 0, 1, 3, 6, 10, 20, 56, 168, 456, 1137, 2827, 7458, 20670, 57577, 157691, 427976, 1170552, 3248411, 9096497, 25505562, 71436182, 200338074, 564083786, 1595055520, 4522769520, 12842772295, 36514010301, 103995490758, 296794937626, 848620165860, 2430089817720
OFFSET
0,4
COMMENTS
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.
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).
FORMULA
a(n) = Sum_{k=0..n} binomial(n, 4*k+2) * A000108(2*k+1).
a(n) = A001006(n) - A107587(n).
G.f.: A(x) = (2 - 2*x - sqrt(1-2*x-3*x^2) - sqrt(1-2*x+5*x^2))/(4*x^2).
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.
a(n) = A107587(n) - A100223(n+2). - R. J. Mathar, Apr 16 2021
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
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
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)]
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
a(n) ~ 3^(n + 3/2) / (4*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Apr 27 2024
EXAMPLE
G.f. = x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 20*x^6 + 56*x^7 + 168*x^8 + ...
MATHEMATICA
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;
Table[a[n], {n, 0, 31}] (* Peter Luschny, Sep 24 2021 *)
PROG
(Python)
M = [4, 9]; E = [1, 1, 1, 1, 3];
A343386 = [0, 0, 1, 3, 6]
for n in range(5, 801):
M.append(((2*n+1)*M[1]+(3*n-3)*M[0])//(n+2))
E.append(((5*n**2+n-3)*E[4] - (10*n**2-16*n+3)*E[3]
+ (10*n**2-34*n+27)*E[2] + (11*n-5)*(n-3)*E[1]
- 15*(n-3)*(n-4)*E[0]) // (n*n+2*n))
A343386.append(M[-1] - E[-1])
M.pop(0); E.pop(0)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved