login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A049486 Maximum length of non-crossing 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 re-use a point, but not an edge.

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. (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 zero-length 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)^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)). - 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 26 04:39 EDT 2017. Contains 288752 sequences.