A257178 Number of 3-Motzkin paths of length n with no level steps at odd level.

1, 3, 10, 33, 110, 369, 1247, 4245, 14558, 50295, 175029, 613467, 2165100, 7692345, 27504600, 98941185, 357952580, 1301960925, 4759282415, 17478557925, 64468072820, 238736987535, 887359113700, 3309489922743, 12381998910700, 46460457776739

Offset

0,2

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Formula

a(n)= Sum_{i=0..floor(n/2)}3^(n-2i)*C(i)*binomial(n-i,i), where C(n) is the n-th Catalan number A000108.

G.f.: (1-3*z-sqrt((1-3*z)*(1-3*z-4*z^2)))/(2*z^2*(1-3*z)).

a(n) ~ sqrt(5) * 4^(n+1) / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Apr 21 2015

Conjecture: (n+2)*a(n) +6*(-n-1)*a(n-1) +(5*n+4)*a(n-2) +6*(2*n-3)*a(n-3)=0. - R. J. Mathar, Sep 24 2016

G.f. A(x) satisfies: A(x) = 1/(1 - 3*x) + x^2 * A(x)^2. - Ilya Gutkovskiy, Jun 30 2020

Example

For n=2 we have 10 paths: H(1)H(1), H(1)H(2), H(1)H(3), H(2)H(1), H(2)H(2), H(2)H(3), H(3)H(1), H(3)H(2), H(3)H(3) and UD.

Mathematica

CoefficientList[Series[(1-3*x-Sqrt[(1-3*x)*(1-3*x-4x^2)])/(2*x^2*(1-3*x)), {x, 0, 20}], x] (* Vaclav Kotesovec, Apr 21 2015 *)

Prog

(PARI) Vec((1-3*x-sqrt((1-3*x)*(1-3*x-4*x^2)))/(2*x^2*(1-3*x)) + O(x^50)) \\ G. C. Greubel, Feb 05 2017

Crossrefs

Cf. A090344, A086622.

Sequence in context: A289450 A113299 A126931 * A257363 A071722 A058987

Adjacent sequences: A257175 A257176 A257177 * A257179 A257180 A257181

Keyword

nonn

Author

José Luis Ramírez Ramírez, Apr 20 2015

Status

approved