A336627 Coordination sequence for the Manhattan lattice.

1, 2, 4, 8, 11, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124, 128, 132, 136, 140, 144, 148, 152, 156, 160, 164, 168, 172, 176, 180, 184, 188, 192, 196, 200, 204, 208, 212, 216, 220, 224

Offset: 0

Author

Sean A. Irvine, Jul 28 2020

Keywords

• nonn
• nice
• easy

Comments

In the Manhattan lattice, N-S streets run alternately N and S, and E-W streets run alternately E and W. - N. J. A. Sloane, Jul 29 2020

Links

• Sean A. Irvine, Illustration of a(0) to a(7)
• N. J. A. Sloane, Crude drawing of initial layers showing paths of length 6 from origin (looking North-West). The presence of three points at distance 4 from the origin on the line of symmetry explains why a(4) is odd!
• Index entries for linear recurrences with constant coefficients, signature (2,-1).

Crossrefs

Cf. A008574 (square lattice), A117633 (self-avoiding walks).

Programs

Mathematica

CoefficientList[Series[(1+x^2)(1+2x^3-x^4)/(1-x)^2,{x,0,80}],x] (* or *) LinearRecurrence[{2,-1},{1,2,4,8,11,16,20},80] (* Harvey P. Dale, Dec 28 2021 *)

PARI

a(n)=if(n>4, 4*n-4, min(2^n, 11)) \\ Charles R Greathouse IV, Oct 18 2022

Formula

G.f.: (1+x^2) * (1+2*x^3-x^4) / (1-x)^2.

a(n) = 4*(n-1), n >= 5.