login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A332044 a(n) is the length of the shortest circuit that visits every edge of an undirected n X n grid graph. 1
4, 16, 28, 48, 68, 96, 124, 160, 196, 240, 284, 336, 388, 448, 508, 576, 644, 720, 796, 880, 964, 1056, 1148, 1248, 1348, 1456, 1564, 1680, 1796, 1920, 2044, 2176, 2308, 2448, 2588, 2736, 2884, 3040, 3196, 3360, 3524, 3696, 3868, 4048, 4228, 4416, 4604, 4800, 4996, 5200 (list; graph; refs; listen; history; text; internal format)
OFFSET
2,1
COMMENTS
An n X n grid graph has a total of 2n(n-1) edges. However, this results in 4n-8 odd vertices, which (except in the case of n=2) means an Eulerian circuit is not possible. Each side of the graph contains n-2 odd vertices.
When n is even, these vertices can be separated into pairs, and the shortest postman circuit can be created using the edges between each pair twice. This results in an increase of (n-2)/2 edges per side, or an increase of 2(n-2) total. When added to the total number of edges, this becomes 2n(n-1) + 2(n-2) = 2n^2-4.
When n is odd, an even number of vertices per side can be separated into pairs, with the edge between them being used twice, just as before (resulting in an increase of (n-3)/2 edges per side, or an increase of 2(n-3) total). However, this will leave four lone vertices - one per side. These can also be paired, and connected with two edges, for an additional 4 edges. Adding all these edges together results in 2n(n-1) + 2(n-3) + 4 = 2n^2-2.
The different forms for an even value of n and an odd value of n can be combined into a(n) = 2*n^2 - 4 + 2*(n mod 2).
LINKS
Wikipedia, Eulerian path
FORMULA
a(n) = 2*n^2 - 4 + 2*(n mod 2).
From Stefano Spezia, Feb 05 2020: (Start)
O.g.f.: 4*x^2*(-1 - 2*x + x^2)/((-1 + x)^3*(1 + x)).
E.g.f.: 4 - exp(-x) + exp(x)*(-3 + 2*x + 2*x^2).
a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4) for n > 5.
a(2*n+1) = A035008(n).
(End)
MATHEMATICA
Array[2 #^2 - 4 + 2 Boole[OddQ@ #] &, 51] (* Michael De Vlieger, Feb 08 2020 *)
LinearRecurrence[{2, 0, -2, 1}, {4, 16, 28, 48}, 50] (* Harvey P. Dale, Sep 10 2021 *)
CROSSREFS
Cf. A035008.
Sequence in context: A017569 A161335 A121054 * A273368 A209979 A294629
KEYWORD
nonn
AUTHOR
Stephen R Simons, Feb 05 2020
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 5 06:19 EST 2024. Contains 370537 sequences. (Running on oeis4.)