login
A329910
Number of harmoniously labeled graphs with n edges and at most n vertices.
2
0, 0, 1, 4, 32, 72, 2187, 20736, 262144, 3200000, 48828125, 729000000, 13060694016, 230539333248, 4747561509943, 96717311574016, 2251799813685250, 51998697814229000, 1350851717672990000, 34867844010000000000, 1000000000000000000000, 28531167061100000000000
OFFSET
1,4
COMMENTS
A graph G with n edges is harmonious if there is an injection f from its vertex set to the group of integers modulo n such that when each edge uv of G is assigned the weight f(u)+f(v) (mod n), the resulting weights are distinct.
LINKS
R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs, SIAM J. Algebraic and Discrete Methods, 1 (1980), 382-404.
R. L. Graham and N. J. A. Sloane, On Additive Bases and Harmonious Graphs
FORMULA
For n odd, a(n) = ((n-1)/2)^n. For n even, a(n) = (n*(n-2)/4)^(n/2).
EXAMPLE
a(3)=1 because there is only one harmonious graph with 3 edges and at most 3 vertices.
MATHEMATICA
Table[If[EvenQ[n], (n*(n-2)/4)^(n/2), ((n-1)/2)^n], {n, 1, 22}] (* Stefano Spezia, Nov 24 2019 *)
CROSSREFS
A085526 contains the odd-indexed terms.
Sequence in context: A076137 A138340 A113250 * A012036 A153794 A222326
KEYWORD
nonn,easy
AUTHOR
STATUS
approved