|
|
A053656
|
|
Number of cyclic graphs with oriented edges on n nodes (up to symmetry of dihedral group).
|
|
14
|
|
|
1, 2, 2, 4, 4, 9, 10, 22, 30, 62, 94, 192, 316, 623, 1096, 2122, 3856, 7429, 13798, 26500, 49940, 95885, 182362, 350650, 671092, 1292762, 2485534, 4797886, 9256396, 17904476, 34636834, 67126282, 130150588, 252679832, 490853416
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Also number of bracelets (or necklaces) with n red or blue beads such that the beads switch colors when bracelet is turned over.
a(n) is also the number of frieze patterns generated by filling a 1 X n block with n copies of an asymmetric motif (where the copies are chosen from original motif or a 180-degree rotated copy) and then repeating the block by translation to produce an infinite frieze pattern. (Pisanski et al.)
a(n) is also the number of minimal fibrations of a bidirectional n-cycle over the 2-bouquet up to precompositions with automorphisms of the n-cycle. (Boldi et al.) - Sebastiano Vigna, Jan 08 2018
|
|
REFERENCES
|
Jeb F. Willenbring, A stability result for a Hilbert series of O_n(C) invariants.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: x/(1-x) + x^2/(2*(1-2*x^2)) + Sum_{n >= 1} (x^(2*n)/(2*n)) * Sum_{ d divides n } phi(d)/(1-x^d)^(2*n/d), or x^2/(2*(1-2*x^2)) - Sum_{n >= 1} phi(n)*log(1-2*x^n)/(2*n). [corrected and extended by Andrey Zabolotskiy, Oct 17 2017]
a(n) = A000031(n)/2 + (if n even) 2^(n/2-2).
|
|
EXAMPLE
|
2 at n=3 because there are two such cycles. On (o -> o -> o ->) and (o -> o <- o ->).
|
|
MAPLE
|
v:=proc(n) local k, t1; t1:=0; for k in divisors(n) do t1 := t1+phi(k)*2^(n/k); od: t1; end;
h:=n-> if n mod 2 = 0 then (n/2)*2^(n/2); else 0; fi;
|
|
MATHEMATICA
|
a[n_] := Total[ EulerPhi[#]*2^(n/#)& /@ Divisors[n]]/(2n) + 2^(n/2-2)(1-Mod[n, 2]); Table[a[n], {n, 1, 35}] (* Jean-François Alcover, Nov 21 2011 *)
|
|
PROG
|
(PARI) a(n)={(sumdiv(n, d, eulerphi(d)*2^(n/d))/n + if(n%2==0, 2^(n/2-1)))/2} \\ Andrew Howroyd, Jun 16 2021
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
Jeb F. Willenbring (jwillenb(AT)ucsd.edu), Feb 14 2000
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|