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

%I #27 Oct 18 2022 14:59:02

%S 1,4,10,21,34,53,74,101,130,165,202,245,290,341,394,453,514,581,650,

%T 725,802,885,970,1061,1154,1253,1354,1461,1570,1685,1802,1925,2050,

%U 2181,2314,2453,2594,2741,2890,3045,3202

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

%C One can reuse a point, but not an edge.

%C From _Hugo van der Sanden_, Sep 27 2005: (Start)

%C 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.

%C 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.

%C 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.

%C 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.)

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

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2, 0, -2, 1).

%F From _Colin Barker_, May 02 2013: (Start)

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

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

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

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

%Y Cf. A049487.

%K nonn,walk,nice,easy

%O 1,2

%A Arlin Anderson (starship1(AT)gmail.com)

%E More terms from _Hugo van der Sanden_, Sep 27 2005