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

%I #38 Dec 01 2017 18:59:16

%S 1,2,3,6,6,20,14,48,52,140,108,624,352,1400,2172,4464,4116,22112,

%T 14602,68016,88376,209936,190746,1075200,839128,2797000,3730584,

%U 11276704,9587580,67195520,35792568

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

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

%C 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

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

%H G. C. Greubel, <a href="/A056391/b056391.txt">Table of n, a(n) for n = 1..1000</a> (terms 1..200 from Andrew Howroyd)

%H Andrew Howroyd, <a href="/A056391/a056391.txt">Polya Enumeration in PARI (many sequences included)</a>

%H Marks R. Nester, <a href="/A056391/a056391.pdf">Mathematical investigations of some plant interaction designs</a>, Chapter 2, Finite and Periodic Sequences, plus Notes and Errata.

%F Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.

%F a(n) = A056371(n) / 2. - _Andrew Howroyd_, Apr 20 2017

%F a(n) = A288620(n, 2) + 1. - _Andrew Howroyd_, Jun 13 2017

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

%o (PARI) 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

%o (PARI) \\ alternative using Polya enumeration functions (see attachment)

%o a(n) = NonequivalentStructs(StepShiftPerms(n),2); \\ _Andrew Howroyd_, Oct 01 2017

%Y Row 2 of A285522.

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

%K nonn

%O 1,2

%A _Marks R. Nester_