|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=0..n} binomial(n, 4*k+2) * A000108(2*k+1).
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.
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) = ((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
|
|
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;
|
|
PROG
|
(Python)
M = [4, 9]; E = [1, 1, 1, 1, 3];
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))
M.pop(0); E.pop(0)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|