A095981 Number of plateau-free Motzkin paths of length n.

0, 0, 1, 2, 5, 11, 26, 61, 147, 357, 879, 2183, 5471, 13811, 35100, 89724, 230562, 595237, 1543191, 4016038, 10487553, 27473602, 72178312, 190127740, 502044221, 1328667241, 3523684572, 9363119781, 24924679832, 66461841934, 177501561659

Offset

0,4

Comments

A plateau in a Motzkin path is a sequence of contiguous flatsteps that is either the entire path or of length >=1 and preceded by an up step and followed by a down step. a(n) = number of plateau-free Motzkin paths of length n.

Links

Table of n, a(n) for n=0..30.

Formula

a(n) = a(n-1) + a(n-2) + 1 + a(2)(1 + a(n-4) )+a(3)(1 + a(n-5)) + ... + a(n-2)(1 + a(0)) for n>=3. This recurrence counts plateau-free Motzkin n-paths by location of first return to ground level.

G.f.: (-1 + 2*x + x^2 - x^3 + (1 - 4*x + 2*x^2 + 6*x^3 - 7*x^4 + 2*x^5 + x^6)^(1/2))/(2*(-1 + x)*x^2). Satisfies x^2*(1-x)*A(x)^2-(1-2*x-x^2+x^3)*A(x)+x^2=0.

Conjecture: (n+2)*a(n) +(-5*n-4)*a(n-1) +6*n*a(n-2) +(4*n-13)*a(n-3) +(-13*n+43)*a(n-4) +3*(3*n-13)*a(n-5) +(-n+4)*a(n-6) +(-n+7)*a(n-7)=0. - R. J. Mathar, Nov 23 2014

Example

The middle two steps of UFFD form a plateau and a(4) counts the 5 paths FFUD,FUDF,UDFF,UDUD,UUDD.

Mathematica

a[0] = 0; a[1] = 0; a[2] = 1; a[n_]/; n>=3 := a[n] = a[n-1] + a[n-2] + 1 + Sum[(a[k])(1+a[n-2-k]), {k, 2, n-2}]; Table[a[n], {n, 0, 15}]

Crossrefs

Sequence in context: A191692 A182015 A124217 * A247471 A082397 A051286

Adjacent sequences: A095978 A095979 A095980 * A095982 A095983 A095984

Keyword

nonn

Author

David Callan, Jul 16 2004

Status

approved