A290265 The number of non-palindromic Motzkin paths of length n.

0, 0, 0, 2, 4, 16, 38, 114, 288, 800, 2092, 5702, 15244, 41568, 112884, 309822, 851344, 2354656, 6530336, 18193238, 50834716, 142530256, 400713502, 1129710694, 3192584432, 9043259136, 25669403892, 73007358218, 208022076292, 593741582912, 1697381979094, 4859758184274, 13933559180928

Offset

0,4

Comments

The Motzkin paths (A001006) are classified here as either palindromic or non-palindromic. The latter are counted by the sequence 1, 1, 2, 2, 3, 3, 5, 5..., offset 0, i.e., entries of A005773 repeated.

Non-palindromic means, there is at least one step of the n (say, the s-th) which does not match the (n-s+1)st step. Not matching means, if the s-th step is U, the (n-s+1)st step is not D, or if the s-th step is F (sometimes also denoted H), the (n-s+1)st step is not F.

All terms are even (because a non-palindromic path reversed creates a different non-palindromic path).

Links

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

Formula

a(n) = A001006(n)-A005773(1+floor(n/2)).

Conjecture: -(16*n-47)*(n+2)*(n+1)*a(n) -(n+1)*(9*n^2-167*n+188)*a(n-1) +n*(139*n^2-450*n+59)*a(n-2) +(n-1)*(187*n^2-1619*n+2250)*a(n-3) -(n-2)*(97*n^2+346*n-2255)*a(n-4) +(-311*n^3+2398*n^2-5779*n+4112)*a(n-5) +3*(-153*n^3+1458*n^2-4361*n+4348)*a(n-6) -3*(n-6)*(169*n^2-1152*n+1799)*a(n-7) -9*(n-6)*(n-7)*(23*n-82)*a(n-8)=0.

Maple

A290265 := proc(n)
    A001006(n)-A005773(1+floor(n/2)) ;
end proc:
seq( A290265(n), n=0..60) ;

Mathematica

a001006[n_]:=Hypergeometric2F1[(1-n)/2, -n/2, 2, 4]; a005773[n_]:=If[n==0, 1, Sum[k*Sum[Binomial[n, j]*Binomial[j, 2*j-n-k], {j, 0, n}]/n, {k, 1, n}]]; Table[a001006[n] - a005773[1 + Floor[n/2]], {n, 0, 50}] (* Indranil Ghosh, Aug 04 2017 *)

Crossrefs

Cf. A001006, A005773.

Sequence in context: A110998 A051861 A296297 * A223093 A333022 A048222

Adjacent sequences: A290262 A290263 A290264 * A290266 A290267 A290268

Keyword

nonn

Author

R. J. Mathar, Jul 25 2017

Status

approved