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
Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).
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
KEYWORD
nonn
AUTHOR
Stephen R Simons, Feb 05 2020
STATUS
approved