A045994 a(0)=1, a(n) = M(n) + Sum_{k=1..n-1} M(k)*a(n-k-1), where M(n) are the Motzkin numbers (A001006).

1, 1, 3, 7, 18, 47, 125, 337, 918, 2522, 6977, 19415, 54297, 152507, 429974, 1216297, 3450817, 9816460, 27991422, 79989880, 229034820, 656979399, 1887653560, 5431969355, 15653355151, 45167783715, 130491471940, 377426429199

Offset

0,3

Comments

Apparently the number of grand Motzkin paths of length n that avoid DD starting at level 1. That is, avoiding either positive to negative or negative to positive crossings of the x axis. - David Scambler, Jul 04 2013

Links

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

Vladimir Kruchinin, D. V. Kruchinin, Composita and their properties, arXiv:1103.2582 [math.CO], 2011-2013.

Formula

G.f.: 1/(1-x(1+x)*M(x)), where M(x) is the generating function for the Motzkin numbers. a(n) = Sum(Sum(k/i*Sum(binomial(i,j)*binomial(j,2*j-i-k),j,0,i)*binomial(n-i+k-1,k-1)*(-1)^(n-i),i,k,n),k,1,n), n>0. - Vladimir Kruchinin, Sep 10 2010

Conjecture: (n+1)*a(n) + 2*(-2*n-1)*a(n-1) + 2*(-n+3)*a(n-2) + (11*n-19)*a(n-3) + (11*n-27)*a(n-4) + 3*(n-3)*a(n-5) = 0. - R. J. Mathar, Sep 27 2013

Mathematica

m[0] = 1; m[n_] := m[n] = m[n-1] + Sum[m[k]*m[n-k-2], {k, 0, n-2}]; a[0] = 1; a[n_] := a[n] = m[n] + Sum[m[k]*a[n-k-1], {k, 1, n-1}]; Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Oct 04 2013 *)

Prog

(Maxima) a(n):=sum(sum(k/i*sum(binomial(i, j)*binomial(j, 2*j-i-k), j, 0, i)*binomial(n-i+k-1, k-1)*(-1)^(n-i), i, k, n), k, 1, n); /* Vladimir Kruchinin, Sep 10 2010 */

Crossrefs

Cf. A005773.

Sequence in context: A219233 A211276 A018028 * A101308 A279482 A018029

Adjacent sequences: A045991 A045992 A045993 * A045995 A045996 A045997

Keyword

nonn

Author

N. J. A. Sloane

Status

approved