A049287 -id:A049287 - cp's OEIS frontend

A056391 Number of step shifted (decimated) sequence structures using a maximum of two different symbols.

1, 2, 3, 6, 6, 20, 14, 48, 52, 140, 108, 624, 352, 1400, 2172, 4464, 4116, 22112, 14602, 68016, 88376, 209936, 190746, 1075200, 839128, 2797000, 3730584, 11276704, 9587580, 67195520, 35792568

Offset: 1

Marks R. Nester

nonn

See A056371 for an explanation of step shifts. Permuting the symbols will not change the structure.

Also, number of circulant digraphs on n vertices up to Cayley isomorphism. Two circulant graphs are Cayley isomorphic if there is a d, which is necessarily prime to n, that transforms through multiplication modulo n the step values of one graph into those of the other. For squarefree n this is the only way that two circulant graphs can be isomorphic (see A049297). - Andrew Howroyd, Apr 20 2017

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia.

G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..200 from Andrew Howroyd)
Andrew Howroyd, Polya Enumeration in PARI (many sequences included)
Marks R. Nester, Mathematical investigations of some plant interaction designs, Chapter 2, Finite and Periodic Sequences, plus Notes and Errata.

Row 2 of A285522.

Cf. A056371, A049297, A285620, A049287, A288620.

a[m_, n_] := (1/EulerPhi[n])*Sum[If[GCD[k, n] == 1, m^DivisorSum[n, EulerPhi[#]/MultiplicativeOrder[k, #]&], 0], {k, 1, n}]; a[n_] := a[2, n]/2; Array[a, 40] (* Jean-François Alcover, Jun 12 2017 *)

a(n)=sum(k=1, n, if(gcd(k, n)==1, 2^(sumdiv(n, d, eulerphi(d)/znorder(Mod(k, d)))-1), 0))/eulerphi(n); \\ Andrew Howroyd, Apr 20 2017

\\ alternative using Polya enumeration functions (see attachment)
a(n) = NonequivalentStructs(StepShiftPerms(n),2); \\ Andrew Howroyd, Oct 01 2017

Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
a(n) = A056371(n) / 2. - Andrew Howroyd, Apr 20 2017
a(n) = A288620(n, 2) + 1. - Andrew Howroyd, Jun 13 2017

A049297 Number of nonisomorphic circulant digraphs (i.e., Cayley digraphs for the cyclic group) of order n.

Original entry on oeis.org

1, 2, 3, 6, 6, 20, 14, 46, 51, 140, 108, 624, 352, 1400, 2172, 4262, 4116, 22040, 14602, 68016, 88376, 209936, 190746, 1062592, 839094, 2797000, 3728891, 11276704, 9587580, 67195520, 35792568

Offset: 1

Valery A. Liskovets

Terms may be computed by filtering potentially isomorphic graphs of A056391 through nauty. Terms computed in this way for a(25), a(27) agree with theoretical calculations by others. - Andrew Howroyd, Apr 23 2017

V. A. Liskovets, Some identities for enumerators of circulant graphs, arXiv:math/0104131 [math.CO], 2001.
V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders.
R. Poeschel, Publications.
V. Gatt, On the Enumeration of Circulant Graphs of Prime-Power Order: the case of p^3, arXiv:1703.06038 [math.CO], 2017.
Victoria Gatt, Mikhail Klin, Josef Lauri, Valery Liskovets, From Schur Rings to Constructive and Analytical Enumeration of Circulant Graphs with Prime-Cubed Number of Vertices, in Isomorphisms, Symmetry and Computations in Algebraic Graph Theory, (Pilsen, Czechia, WAGT 2016) Vol. 305, Springer, Cham, 37-65.
Brendan McKay, Nauty home page.

Cf. A049287-A049289, A056391, A038777.

LoadPackage("grape");
CirculantDigraphCount:= function(n) local g; # slow for n >= 10
g:=Graph( Group(()), [1..n], OnPoints, function(x,y) return (y-x) mod n = 1; end,false);
return Length(GraphIsomorphismClassRepresentatives(List(Combinations([1..n]), s->DistanceGraph(g,s))));
end; # Andrew Howroyd, Apr 23 2017

There is an easy formula for prime orders. Formulae are also known for squarefree and prime-squared orders.
From Andrew Howroyd, Apr 23 2017: (Start)
a(n) <= A056391(n).
a(n) = A056391(n) for squarefree n.
a(A000040(n)^2) = A038777(n).
(End)

Further values for (twice) squarefree and (twice) prime-squared orders can be found in the Liskovets reference.
a(14) corrected by Andrew Howroyd, Apr 23 2017
a(16)-a(31) from Andrew Howroyd, Apr 23 2017

A049288 Number of nonisomorphic circulant tournaments, i.e., Cayley tournaments for cyclic group of order 2n-1.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 6, 16, 16, 30, 88, 94, 205, 457, 586, 1096, 3280, 5472, 7286, 21856, 26216, 49940, 174848, 182362, 399472, 1048576, 1290556, 3355456, 7456600, 9256396, 17895736, 59654816, 89478656, 130150588, 390451576, 490853416, 954437292

Offset: 1

Valery A. Liskovets

Further values for prime-squared orders can be found in A038789.

There is an easy formula for prime orders. Formulae are also known for squarefree and prime-squared orders.

B. Alspach, On point-symmetric tournaments, Canad. Math. Bull., 13 (1970), 317-323. [Annotated copy] See r(n).
B. Alspach, On point-symmetric tournaments, Canad. Math. Bull., 13 (1970), 317-323. See r(n).
V. A. Liskovets, Some identities for enumerators of circulant graphs, arXiv:math/0104131 [math.CO], 2001.
V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders
R. Poeschel, Publications
Index entries for sequences related to tournaments

Cf. A002086, A002087, A038789, A049297, A049287, A049289, A060966.

a(n) <= A002086(n). - Andrew Howroyd, Apr 28 2017

a(n) = A002086(n) for squarefree 2n-1. - Andrew Howroyd, Apr 28 2017

a(14)-a(37) from Andrew Howroyd, Apr 28 2017

Reference to Alspach (1970) corrected by Andrew Howroyd, Apr 28 2017

A049289 Number of nonisomorphic self-complementary circulant graphs (Cayley graphs for the cyclic group) of order 4n+1.

Original entry on oeis.org

1, 1, 0, 2, 4, 0, 7, 10, 0, 30, 56, 0, 0, 316, 0, 1096

Offset: 0

Valery A. Liskovets

Further values for (twice) squarefree and (twice) prime-squared orders can be found in the Liskovets reference.

V. A. Liskovets, Some identities for enumerators of circulant graphs, arXiv:math/0104131 [math.CO], 2001.
V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders
R. Poeschel, Publications

Cf. A049297, A049287, A049288.

A285620 Number of circulant graphs on n vertices up to Cayley isomorphism.

Original entry on oeis.org

1, 2, 2, 4, 3, 8, 4, 12, 8, 20, 8, 48, 14, 48, 44, 88, 36, 192, 60, 336, 200, 416, 188, 1344, 424, 1400, 944, 3104, 1182, 8768, 2192, 8784, 6768, 16460, 11144, 46848, 14602, 58288, 44424, 138432, 52488, 355200, 99880, 432576, 351712, 762608, 364724, 2151936, 798960

Offset: 1

Andrew Howroyd, Apr 22 2017

nonn

Two circulant graphs are Cayley isomorphic if there is a d, which is necessarily prime to n, that transforms through multiplication modulo n the step values of one graph into those of the other. For squarefree n this is the only way that two circulant graphs can be isomorphic (See A049287).

Andrew Howroyd, Table of n, a(n) for n = 1..200
V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders.

Cf. A049287, A056391 (circulant digraphs), A049297, A038782.

IsLeastPoint[s_, f_] := Module[{t = f[s]}, While[t > s, t=f[t]]; Boole[s == t]];
c[n_, k_] := Sum[IsLeastPoint[u, Abs[Mod[#*k + Quotient[n, 2], n] - Quotient[n, 2]]&], {u, 1, n/2}];
a[n_] := If[n < 3, n, Sum[If[GCD[k, n] == 1, 2^c[n, k], 0]*2/EulerPhi[n], {k, 1, n/2}]];
Array[a, 50] (* Jean-François Alcover, Jun 12 2017, translated from PARI *)

IsLeastPoint(s,f)={my(t=f(s)); while(t>s,t=f(t));s==t}
C(n,k)=sum(u=1,n/2,IsLeastPoint(u,v->abs((v*k+n\2)%n-n\2)));
a(n)=if(n<3, n, sum(k=1, n/2, if (gcd(k, n)==1, 2^C(n,k),0))*2/eulerphi(n));

A357000 Number of non-isomorphic cyclic Haar graphs on 2*n nodes.

Original entry on oeis.org

1, 2, 3, 5, 5, 12, 9, 22, 21, 44, 29, 157, 73, 244, 367, 649, 521, 2624, 1609, 7385, 8867, 19400, 16769, 92529, 67553, 216274, 277191, 815557, 662369, 4500266, 2311469

Offset: 1

Pontus von Brömssen, Sep 08 2022

The first value of n for which a(n) < A002729(n) - 1 is n = 8. This is because the first counterexample to the bicirculant analog to Ádám's conjecture occurs for n = 8. In the terminology of Hladnik, Marušič, and Pisanski, the smallest integer pair (i,j) such that i and j are Haar equivalent (i.e., the cyclic Haar graphs with indices i and j are isomorphic) but not cyclically equivalent (see A357005) is (141,147). See also A357001 and A357002.

Terms a(1)-a(29) were found by generating the cyclic Haar graphs with indices in A333764, and filtering out isomorphic graphs using Brendan McKay's software nauty.

Milan Hladnik, Dragan Marušič, and Tomaž Pisanski, Cyclic Haar graphs, Discrete Mathematics 244 (2002), 137-152.
Eric Weisstein's World of Mathematics, Haar Graph

Cf. A002729, A008965, A049287, A091696, A137706, A291166, A333764, A339502, A357001, A357002, A357003, A357004, A357005, A357006.

a(n) is the number of terms k of A137706 in the interval 2^(n-1) <= k < 2^n.
a(n) is the number of fixed points k of A357004 in the interval 2^(n-1) <= k < 2^n.
a(n) <= A002729(n)-1 <= A091696(n) <= A008965(n).

a(30) from Eric W. Weisstein, Jun 27 2023

a(31) from Eric W. Weisstein, Jun 28 2023

A075545 Number of connected circulant graphs on n nodes.

Original entry on oeis.org

1, 1, 1, 2, 2, 5, 3, 8, 6, 16, 7, 38, 13, 43, 40, 72, 35, 178, 59, 314, 195, 407, 187, 1256, 420, 1385, 920, 3054, 1181, 8702, 2191, 8280, 6759, 16423, 11138, 46552, 14601, 58227, 44409, 135784, 52487, 354951, 99879, 432158, 351374, 762419, 364723, 2121560, 798948, 3355968

Offset: 1

Eric W. Weisstein, Sep 22 2002

nonn

Computed by Brendan McKay.

Jean-François Alcover, Table of n, a(n) for n = 1..70 [after _Andrew Howroyd_ for A049287 data]
Eric Weisstein's World of Mathematics, Circulant Graph

Cf. A049287.

CountDistinct /@ Table[Select[CanonicalGraph[CirculantGraph[n, #]] & /@ Subsets[Range[Floor[n/2]]], ConnectedGraphQ], {n, 25}] (* Eric W. Weisstein, May 13 2017 *)
A049287 = Cases[Import["https://oeis.org/A049287/b049287.txt", "Table"], {, }][[All, 2]];
a[n_] := Sum[MoebiusMu[n/d] A049287[[d]], {d, Divisors[n]}];
a /@ Range[70] (* Jean-François Alcover, Jan 11 2020 *)

Moebius transform of A049287. - Andrew Howroyd, Nov 04 2017

a(1) changed to 1 by Andrew Howroyd, Apr 24 2017

a(41)-a(50) from Andrew Howroyd, Nov 04 2017

A038781 Number of nonisomorphic circulant undirected p^2-graphs, indexed by odd primes p.

Original entry on oeis.org

8, 423, 798952, 20962209174670288, 247984783510749556137496, 163976067636254581923091475287730651406666, 8961962227285899756481561562282509859208082639789128

Offset: 1

N. J. A. Sloane, May 04 2000

M. Klin, V. A. Liskovets and R. Poeschel, Analytical enumeration of circulant graphs with prime-squared vertices, Sem. Lotharingien de Combin., B36d, 1996, 36 pages.

Cf. A049287.

More terms from Valery A. Liskovets, May 09 2001

Offset corrected by Sean A. Irvine, Feb 14 2021

A054929 Number of complementary pairs of circulant graphs on n nodes.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 2, 6, 4, 10, 4, 24, 8, 24, 22, 42, 20, 96, 30, 168, 100, 208, 94, 656, 215, 700, 464, 1552, 596, 4384, 1096, 4182, 3384, 8230, 5572, 23392, 7316, 29144, 22212, 68064, 26272, 177600, 49940, 216288, 175712, 381304, 182362, 1061472, 399476

Offset: 1

N. J. A. Sloane, May 24 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..64
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A049287, A049289, A054930.

Average of A049287 and A049289.

a(n) = A049287(n)/2 for n mod 4 <> 1; a(n) = (A049287(n) + A049289((n-1)/4))/2 for n mod 4 = 1. - Andrew Howroyd, Jan 16 2022

Terms a(19) and beyond from Andrew Howroyd, Jan 16 2022

A367554 a(n) is the number of 2n-regular circulant graphs of order 53.

Original entry on oeis.org

1, 1, 13, 100, 578, 2530, 8866, 25300, 60115, 120175, 204347, 297160, 371516, 400024, 371516, 297160, 204347, 120175, 60115, 25300, 8866, 2530, 578, 100, 13, 1, 1

Offset: 0

Andrey Zabolotskiy, Nov 22 2023

Brian Alspach and Marni Mishna, Enumeration of Cayley graphs and digraphs, Discr. Math., 256 (2002), 527-539.
Marni Mishna, Home page.
Marni Mishna, Publications.
Marni Mishna, Cayley Graph Enumeration, Master's Thesis, Simon Fraser University, 2000. See p. 16 (which is p. 24 in the pdf).

Cf. A000031, A049287, A285620.

from math import gcd, comb
from sympy import totient, divisors
def A367554(n): return sum(totient(d)*comb(26//d,n//d) for d in divisors(gcd(n,26),generator=True))//26 # Chai Wah Wu, Nov 23 2023

def a(k, p):
    return (2/(p-1)) * sum(euler_phi(d) * binomial((p-1)/(2*d), k/(2*d)) for d in divisors(gcd(k, p-1)/2)) # see Mishna; beware the missing prefactor (2/(p-1))
print([a(2*n, 53) for n in range(27)]) # Andrey Zabolotskiy, Nov 22 2023

Sum_n a(n) = 2581428 = A049287(53) = A285620(53) = A000031((53-1)/2). - Andrey Zabolotskiy, Nov 22 2023

cp's OEIS Frontend

A056391 Number of step shifted (decimated) sequence structures using a maximum of two different symbols.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A049297 Number of nonisomorphic circulant digraphs (i.e., Cayley digraphs for the cyclic group) of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Formula

Extensions

A049288 Number of nonisomorphic circulant tournaments, i.e., Cayley tournaments for cyclic group of order 2n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A049289 Number of nonisomorphic self-complementary circulant graphs (Cayley graphs for the cyclic group) of order 4n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

A285620 Number of circulant graphs on n vertices up to Cayley isomorphism.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A357000 Number of non-isomorphic cyclic Haar graphs on 2*n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A075545 Number of connected circulant graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A038781 Number of nonisomorphic circulant undirected p^2-graphs, indexed by odd primes p.

Views

Author

Keywords

Links

Crossrefs

Extensions

A054929 Number of complementary pairs of circulant graphs on n nodes.

Views