|
|
A058880
|
|
a(n) = (1/(2n)) * Sum_{d|n} phi(d) * 2^(2n/d) + (2^((n-4)/2), if n is even).
|
|
1
|
|
|
12, 36, 104, 352, 1172, 4119, 14572, 52492, 190652, 699266, 2581112, 9587602, 35791472, 134219859, 505290272, 1908881998, 7233629132, 27487817244, 104715393912, 399822505942, 1529755308212, 5864062368274, 22517998136936
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
3,1
|
|
COMMENTS
|
Previous name was "Number of orientations of an n-cycle". Apparently, the book by Harary and Palmer erroneously gives this formula for the number of orientations of an n-cycle, but the correct sequence for that is A053656. The error is in the exponent of 2 in the sum; it should be n/d, not 2*n/d. - Pontus von Brömssen, Mar 30 2022
|
|
REFERENCES
|
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 129, (5.3.3).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = (1/(2n)) * Sum_{d|n} phi(d) * 2^(2n/d) + (2^((n-4)/2), if n is even). - Amiram Eldar, Aug 28 2019
|
|
MAPLE
|
A058880 := proc(n) local d, t1, t2; if n mod 2 = 0 then t1 := 2^((n-4)/2) else t1 := 0; fi; t2 := divisors(n); for d in t2 do t1 := t1+phi(d)*2^(2*n/d)/(2*n); od; t1; end;
|
|
MATHEMATICA
|
a[n_] := DivisorSum[n, EulerPhi[#]*2^(2n/#) &]/(2n) + If[OddQ[n], 0, 2^((n - 4)/2)]; Array[a, 23, 3] (* Amiram Eldar, Aug 28 2019 *)
|
|
PROG
|
(PARI) a(n) = sumdiv(n, d, eulerphi(d)*2^(2*n/d))/(2*n) + if (!(n%2), 2^((n-4)/2)); \\ Michel Marcus, Aug 29 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|