A257388 Number of 4-Motzkin paths of length n with no level steps at odd level.
1, 4, 17, 72, 306, 1304, 5573, 23888, 102702, 442904, 1915978, 8314480, 36195236, 158067312, 692475053, 3043191200, 13415404246, 59321085720, 263100680926, 1170347803440, 5221037429948, 23356788588752, 104772374565666, 471214329434208, 2124649562373708, 9603094073668208
Offset: 0
Keywords
Examples
For n=2 we have 17 paths: H(1)H(1), H(1)H(2), H(1)H(3), H(1)H(4), H(2)H(1), H(2)H(2), H(2)H(3), H(2)H(4), H(3)H(1), H(3)H(2), H(3)H(3), H(3)H(4), H(4)H(1), H(4)H(2), H(4)H(3), H(4)H(4) and UD.
Links
- G. C. Greubel, Table of n, a(n) for n = 0..1000
Programs
-
Mathematica
CoefficientList[Series[(1-4*x-Sqrt[(1-4*x)*(1-4*x-4*x^2)])/(2*x^2*(1-4*x)), {x, 0, 20}], x] (* Vaclav Kotesovec, Apr 22 2015 *) -
PARI
x='x+O('x^50); Vec((1-4*x-sqrt((1-4*x)*(1-4*x-4*x^2)))/(2*x^2*(1-4*x))) \\ G. C. Greubel, Apr 08 2017
Formula
a(n) = Sum_{i=0..floor(n/2)}4^(n-2i)*C(i)*binomial(n-i,i), where C(n) is the n-th Catalan number A000108.
G.f.: (1-4*x-sqrt((1-4*x)*(1-4*x-4*x^2)))/(2*x^2*(1-4*x)).
a(n) ~ sqrt(58+41*sqrt(2)) * 2^(n+1/2) * (1+sqrt(2))^n / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Apr 22 2015
Conjecture: (n+2)*a(n) +8*(-n-1)*a(n-1) +4*(3*n+1)*a(n-2) +8*(2*n-3)*a(n-3)=0. - R. J. Mathar, Sep 24 2016
G.f. A(x) satisfies: A(x) = 1/(1 - 4*x) + x^2 * A(x)^2. - Ilya Gutkovskiy, Jun 30 2020