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
Amiram Eldar, Table of n, a(n) for n = 3..1666
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
N. J. A. Sloane, Jan 07 2001
EXTENSIONS
New name, using existing formula, from Pontus von Brömssen, Mar 30 2022
STATUS
approved