|
|
A257388
|
|
Number of 4-Motzkin paths of length n with no level steps at odd level.
|
|
2
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
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
|
|
EXAMPLE
|
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.
|
|
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 *)
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|