|
| |
|
|
A090345
|
|
Number of Motzkin paths of length n with no level steps at even level.
|
|
9
|
|
|
|
1, 0, 1, 1, 3, 5, 12, 24, 55, 119, 272, 612, 1411, 3247, 7565, 17667, 41561, 98099, 232696, 553784, 1322813, 3169065, 7614583, 18342921, 44294991, 107200829, 259983346, 631718606, 1537737567, 3749440151, 9156561590, 22394270034, 54845701243, 134497468359
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
Hankel transform of a(n) is A000012. Hankel transform of a(n+1) is 0,-1,0,1,0,-1,0,... or -[x^n](x/(1+x^2)). Hankel transform of a(n+2) is A008619(n+1). - Paul Barry, Mar 23 2011
Number of lattice paths, never going below the x-axis, from (0,0) to (n,0) consisting of up steps U(k) = (k,1) for every positive integer k and down steps D = (1,-1). For instance, for n=5, we have the 5 paths: U(4)D, U(2)U(1)DD, U(1)U(2)DD, U(2)DU(1)D, U(1)DU(2)D. - José Luis Ramírez Ramírez, Apr 19 2015
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: (1 - z - sqrt(1 - 2*z - 3*z^2 + 4*z^3))/(2*z^2).
G.f.: 1/(1-x^2/(1-x-x^2/(1-x^2/(1-x-x^2/(1-x^2/(1-x-x^2/(1-... (continued fraction). - Paul Barry, Apr 08 2009
G.f.: 1/(1-z/(1-z/(1-z/(...)))) where z=x^2/(1-x) (continued fraction); in other words, g.f.: C(x^2/(1-x)) where C(x) is the g.f. for the Catalan numbers (A000108). - Joerg Arndt, Mar 18 2011
a(0) = 1, a(n) = Sum_{k=0..floor(n/2)} (k/(n-k))*binomial(n-k,k)*A000108(k). - Paul Barry, Jul 01 2009
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k-1, n-2k)*A000108(k). - Paul Barry, Mar 23 2011
The sequence starting with offset 1 = iterates of M*V, leftmost column. M = an infinite tridiagonal matrix with all 1's in the sub and superdiagonals and [0,1,0,1,0,1,0,1,...] as the main diagonal; and the rest zeros. V = vector [1,0,0,0,...]. - Gary W. Adamson, Jun 08 2011
D-finite with recurrence (n+2)*a(n) + (-2*n-1)*a(n-1) + 3*(-n+1)*a(n-2) + 2*(2*n-5)*a(n-3) = 0. - R. J. Mathar, Nov 24 2012
a(n) ~ sqrt(34+2*sqrt(17)) * ((1+sqrt(17))/2)^n / (4 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 12 2014
a(0) = 1, a(1) = 0; a(n) = a(n-1) + Sum_{k=0..n-2} a(k) * a(n-k-2). - Ilya Gutkovskiy, Jul 20 2021
|
|
|
EXAMPLE
|
a(5)=5 because we have UHDUD, UDUHD, UHUDD, UUDHD and UHHHD, where U=(1,1), D=(1,-1) and H=(1,0).
|
|
|
MATHEMATICA
|
CoefficientList[Series[(1-x-Sqrt[1-2*x-3*x^2+4*x^3])/(2*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 12 2014 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
