A212584 - OEIS

A212584

Nonnegative walks of length n on the x-axis starting at the origin using steps {1,-1} and visiting no point more than twice.

1, 1, 2, 3, 5, 6, 9, 12, 18, 24, 34, 46, 65, 89, 124, 170, 236, 325, 450, 620, 857, 1182, 1633, 2253, 3111, 4293, 5927, 8180, 11292, 15585, 21513, 29693, 40986, 56571, 78085, 107778, 148765, 205336, 283422, 391200, 539966, 745302, 1028725, 1419925, 1959892

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

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

FORMULA

G.f. (1 + x^3 - x^5)/(1 - x - x^2 + x^3 - x^4 + x^6).

a(n) = a(n-2) + a(n-4) + a(n-5) + 1, a(0..4) = {1,1,2,3,5}.

a(n) = g(n) + sum(j=0..n-4, g(j) * sum(k=1..(n-j)/4, binomial(n-j-3*k-1, k-1))), g(j) = if(j<3,1,2) + floor(j/2).

EXAMPLE

The 5 walks of length 4 are (1,1,1,1),(1,1,1,-1),(1,1,-1,1),(1,1,-1,-1) and (1,-1,1,1).

MATHEMATICA