A049486 Maximum length of non-crossing path on n X n square lattice.

1, 4, 10, 21, 34, 53, 74, 101, 130, 165, 202, 245, 290, 341, 394, 453, 514, 581, 650, 725, 802, 885, 970, 1061, 1154, 1253, 1354, 1461, 1570, 1685, 1802, 1925, 2050, 2181, 2314, 2453, 2594, 2741, 2890, 3045, 3202

Offset: 1

Author

Arlin Anderson (starship1(AT)gmail.com)

Keywords

• nonn
• walk
• nice
• easy

Comments

One can reuse a point, but not an edge.

From Hugo van der Sanden, Sep 27 2005: (Start)

The n X n square has #(n) = 2n(n+1) line segments and v_o(n) = 4(n-1) vertices of odd degree. The network is traversable only when v_o(n) <= 2. When not, we must lose sufficient line segments to reduce v_o() to 2.

For odd n >= 3, we have an even number of odd vertices along each edge; we can pair them up and lose the single line segment joining each pair except for our start/end points. So in this case we have a(n) = #(n) - (v_o(n) - 2)/2 = 2n^2 + 3.

For even n >= 2, we have an odd number of odd vertices along each edge. The best we can do is start and end at the two vertices adjacent to one corner; pairing up the rest allows us to lose a single line segment for each of the remaining pairs except for the two vertices adjacent to the diagonally opposite corner, for which we must lose 2 line segments. So in this case we have a(n) = #(n) - ((v_o(n) - 4)/2 + 2) = 2n^2 + 2.

For n < 2, we have no vertices of odd degree, so we cannot save a segment by starting and ending on a pair of them. So we can specify the exact function using a couple of characteristic functions: a(n) = 2n^2 + 1 + c(n > 1) + c(n odd) (I'm assuming a(0) = 1 here, on the grounds that there is a single zero-length path in that case.)

Note that the theoretical maximum is always achievable, e.g. using Fleury's algorithm. (End)

Links

• Index entries for linear recurrences with constant coefficients, signature (2, 0, -2, 1).

Crossrefs

Cf. A049487.

Programs

Mathematica

Join[{1,4},LinearRecurrence[{2,0,-2,1},{10,21,34,53},40]] (* Harvey P. Dale, Aug 21 2013 *)

Formula

From Colin Barker, May 02 2013: (Start)

Conjecture: a(n) = (9 + (-1)^n - 8*n + 4*n^2)/2 for n > 2.

a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4) for n > 6.

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

Extensions

More terms from Hugo van der Sanden, Sep 27 2005