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

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

Author

Gennady Eremin, Sergey Kirgizov, Apr 13 2021

Keywords

• nonn
• easy

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

Examples

			G.f. = x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 20*x^6 + 56*x^7 + 168*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, A107587, A024492, A100223.

Programs

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

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)

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