A064043 Number of length 3 walks on an n-dimensional hypercubic lattice starting at the origin and staying in the nonnegative part.

0, 3, 18, 51, 108, 195, 318, 483, 696, 963, 1290, 1683, 2148, 2691, 3318, 4035, 4848, 5763, 6786, 7923, 9180, 10563, 12078, 13731, 15528, 17475, 19578, 21843, 24276, 26883, 29670, 32643, 35808, 39171, 42738, 46515, 50508, 54723, 59166, 63843, 68760, 73923, 79338

Offset: 0

Author

Henry Bottomley, Aug 23 2001

Keywords

• nonn
• easy

Links

• Harry J. Smith, Table of n, a(n) for n = 0..1000
• D. R. L. Brown, Bounds on surmising remixed keys, IACR, Report 2015/375, 2015-2016. See Table 1.
• Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Crossrefs

Number of walks length 0, 1 and 2 are A000012, A001477 and A002378.

Cf. A084990.

Programs

Maple

seq(sum(3*n+n^2-1, k=1..n), n=0..39); # Zerinvary Lajos, Jan 28 2008

Mathematica

Table[n*(n^2 + 3n -1), {n,0,50}] (* G. C. Greubel, Jul 20 2017 *)

PARI

a(n) = { n*(n^2 + 3*n - 1) } \\ Harry J. Smith, Sep 06 2009

Formula

a(n) = n*(n^2 + 3*n - 1) = n*A014209(n) = A064044(n, 3).

a(n) = a(n-1) + 3*A002378(n-1) + 6*A001477(n-1) + 3*A000012(n-1).

G.f.: 3*x*(1+2*x-x^2)/(1-x)^4. - Colin Barker, Apr 19 2012

E.g.f.: (x^3 + 6*x^2 + 3*x)*exp(x). - G. C. Greubel, Jul 20 2017

a(n) = A084990(n)/3. - Alois P. Heinz, Jul 21 2017