

A049486


Maximum length of noncrossing path on n X n square lattice.


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

One can reuse a point, but not an edge.
The n X n square has #(n) = 2n(n+1) line segments and v_o(n) = 4(n1) 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. (cont.)
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. (cont.)
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. (cont.)
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 zerolength path in that case.) (cont.)
Note that the theoretical maximum is always achievable, e.g. using Fleury's algorithm.  Hugo van der Sanden, Sep 27 2005


LINKS

Table of n, a(n) for n=1..41.
Index entries for linear recurrences with constant coefficients, signature (2, 0, 2, 1).


FORMULA

Conjecture: a(n) = (9+(1)^n8*n+4*n^2)/2 for n>2. a(n) = 2*a(n1)2*a(n3)+a(n4) for n>6. G.f.: x*(x^5x^4+3*x^3+2*x^2+2*x+1) / ((x1)^3*(x+1)).  Colin Barker, May 02 2013


MATHEMATICA

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


CROSSREFS

Cf. A049487.
Sequence in context: A009870 A009919 A008042 * A008139 A038404 A024985
Adjacent sequences: A049483 A049484 A049485 * A049487 A049488 A049489


KEYWORD

nonn,walk,nice


AUTHOR

Arlin Anderson (starship1(AT)gmail.com)


EXTENSIONS

More terms from Hugo van der Sanden, Sep 27 2005


STATUS

approved



