A362652 Expansion of g.f. x*(-2 - 2*x + x^2 - x^3)/((1 + x)^2 *(-1 + x)^3).

2, 4, 7, 12, 16, 24, 29, 40, 46, 60, 67, 84, 92, 112, 121, 144, 154, 180, 191, 220, 232, 264, 277, 312, 326, 364, 379, 420, 436, 480, 497, 544, 562, 612, 631, 684, 704, 760, 781, 840, 862, 924, 947, 1012, 1036, 1104, 1129, 1200, 1226, 1300, 1327

Offset: 1

Author

Jonathon Priestley, Apr 28 2023

Keywords

• nonn
• easy

Comments

a(n) gives the number of vertices encountered along the shortest walk that encounters every edge at least once on the graph with n vertices where the graph is both complete and every node also has an edge to itself.

a(n) can be thought of as the length of a list made up using n distinct elements where every element is next to every other element (including a copy of itself) at least once. Such a list could be used forwards and backward when kerning a font as a way to minimize the number of characters typed in total.

Examples

			G.f.: 2*x + 4*x^2 + 7*x^3 + 12*x^4 + 16*x^5 + 24*x^6 + 29*x^7 + 40*x^8 + 46*x^9 + ...
		

Links

• Index entries for linear recurrences with constant coefficients, signature (1,2,-2,-1,1).

Crossrefs

Cf. A053439.

Programs

Mathematica

CoefficientList[Series[x(-2-2x+x^2-x^3)/((1+x)^2(-1+x)^3), {x, 0, 50}], x]
(* or *)
LinearRecurrence[{1, 2, -2, -1, 1}, {2, 4, 7, 12, 16}, 50]

Python

def a(n: int): return n + (n & 1) + n * ( n >> 1 )

Formula

a(n) = n + (n mod 2) + (n * (n - (n mod 2)))/2.

a(2*n) = 2*n + 2*n^2;

a(2*n - 1) = 1 - n + 2*n^2.

E.g.f.: (2 + x)*(exp(x)*x + sinh(x))/2. - Stefano Spezia, May 07 2023