A053656 Number of cyclic graphs with oriented edges on n nodes (up to symmetry of dihedral group).

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

Offset: 1

Author

Jeb F. Willenbring (jwillenb(AT)ucsd.edu), Feb 14 2000

Keywords

• nonn
• easy
• nice

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

Examples

			2 at n=3 because there are two such cycles. On (o -> o -> o ->) and (o -> o <- o ->).
		

References

• Jeb F. Willenbring, A stability result for a Hilbert series of O_n(C) invariants.

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..3334
• Rémi Cocou Avohou, Joseph Ben Geloun, and Reiko Toriumi, Counting U(N)^{⊗r} ⊗ O(N)^{⊗q} invariants and tensor model observables, Eur. Phys. J. C 84, 839 (2024), see pp. 11, 27; Preprint arXiv:2404.16404 [hep-th], 2024. See pp. 18, 49.
• Paolo Boldi and Sebastiano Vigna, Fibrations of Graphs, Discrete Math., 243 (2002), 21-66.
• Shinsaku Fujita, alpha-beta Itemized Enumeration of Inositol Derivatives and m-Gonal Homologs by Extending Fujita's Proligand Method, Bull. Chem. Soc. Jpn. 2017, 90, 343-366. See Table 8.
• T. Pisanski, D. Schattschneider, and B. Servatius, Applying Burnside's lemma to a one-dimensional Escher problem, Math. Mag., 79 (2006), 167-180.
• Jeb F. Willenbring, Home page.
• A. Yajima, How to calculate the number of stereoisomers of inositol-homologs, Bull. Chem. Soc. Jpn. 2014, 87, 1260-1264. See Tables 1 and 2 (and text).
• Index entries for sequences related to bracelets.

Crossrefs

The 8 sequences in Table 8 of Fujita (2017) are A053656, A000011, A256216, A256217, A123045, A283846, A283847, A283848.

Programs

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;
A053656:=n->(v(n)+h(n))/(2*n); # N. J. A. Sloane, Nov 11 2006

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 *)

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

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).

Extensions

More terms and additional comments from Christian G. Bower, Dec 13 2001