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

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

g[j_]:= If[j<3, 1, 2] + Floor[j/2]; Table[Sum[(g[j])*((Sum[Binomial[(n-j-3*k-1), k-1], {k, 1, (n-j)/4}])), {j, 0, n-4}] + g[n], {n, 0, 45}]
CoefficientList[Series[(1+x^3-x^5)/(1-x-x^2+x^3-x^4+x^6), {x, 0, 45}], x]

Crossrefs

Cf. A212585, A212586, A212587, A164392, A212589.

Sequence in context: A258939 A244747 A241742 * A330228 A166048 A240306

Adjacent sequences: A212581 A212582 A212583 * A212585 A212586 A212587

Keyword

nonn,walk

Author

David Scambler, May 22 2012

Status

approved