Search: id:A049486
Results 1-1 of 1 results found.

%I A049486
%S A049486 1,4,10,21,34,53,74,101,130,165,202,245,290,341,394,453,514,581,650,
%T A049486 725,802,885,970,1061,1154,1253,1354,1461,1570,1685,1802,1925,2050,
%U A049486 2181,2314,2453,2594,2741,2890,3045,3202
%N A049486 Maximum length of non-crossing path on n X n square lattice.
%C A049486 One can re-use a point, but not an edge.
%C A049486 Comments from Hugo van der Sanden (hv(AT)crypt.org), Sep 27 2005:
%C A049486 "The n X n square has #(n) = 2n(n+1) line segments and v_o(n) = 4(n-1)
%C A049486 vertices of odd degree. The network is traversable only when v_o(n) <= 
               2.
%C A049486 When not, we must lose sufficient line segments to reduce v_o() to 2.
%C A049486 For odd n >= 3, we have an even number of odd vertices along each
%C A049486 edge; we can pair them up and lose the single line segment joining
%C A049486 each pair except for our start/end points. So in this case we have
%C A049486 a(n) = #(n) - (v_o(n) - 2)/2 = 2n^2 + 3.
%C A049486 For even n >= 2, we have an odd number of odd vertices along each
%C A049486 edge. The best we can do is start and end at the two vertices
%C A049486 adjacent to one corner; pairing up the rest allows us to lose a
%C A049486 single line segment for each of the remaining pairs except for
%C A049486 the two vertices adjacent to the diagonally opposite corner, for
%C A049486 which we must lose 2 line segments. So in this case we have
%C A049486 a(n) = #(n) - ((v_o(n) - 4)/2 + 2) = 2n^2 + 2.
%C A049486 For n < 2, we have no vertices of odd degree, so we cannot save a
%C A049486 segment by starting and ending on a pair of them. So we can specify
%C A049486 the exact function using a couple of characteristic functions: a(n) = 
               2n^2 + 1 + c(n > 1) + c(n odd)
%C A049486 (I'm assuming a(0) = 1 here, on the grounds that there is a single zero-length 
               path in that case.)
%C A049486 Note that the theoretical maximum is always achievable, e.g. using Fleury's 
               algorithm."
%Y A049486 Cf. A049487.
%Y A049486 Sequence in context: A009870 A009919 A008042 this_sequence A008139 A038404 
               A024985
%Y A049486 Adjacent sequences: A049483 A049484 A049485 this_sequence A049487 A049488 
               A049489
%K A049486 nonn,walk,nice
%O A049486 1,2
%A A049486 Arlin Anderson (starship1(AT)gmail.com)
%E A049486 More terms from Hugo van der Sanden (hv(AT)crypt.org), Sep 27 2005

Search completed in 0.001 seconds