login
Number of step shifted (decimated) sequences using a maximum of two different symbols.
87

%I #26 Dec 01 2017 21:41:49

%S 2,4,6,12,12,40,28,96,104,280,216,1248,704,2800,4344,8928,8232,44224,

%T 29204,136032,176752,419872,381492,2150400,1678256,5594000,7461168,

%U 22553408,19175160,134391040,71585136,269510016,429726240,1073758360

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

%C All step shifts of a sequence are considered to be equivalent, where a step shift transformation is obtained by selecting every k-th element of a sequence for some k relatively prime to n. For example, 2 is relatively prime to 5 and a 2-step shift of abcde is bdace.

%D M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

%H G. C. Greubel, <a href="/A056371/b056371.txt">Table of n, a(n) for n = 1..1000</a>

%H R. C. Titsworth, <a href="http://projecteuclid.org/euclid.ijm/1256059671">Equivalence classes of periodic sequences</a>, Illinois J. Math., 8 (1964), 266-270.

%F The cycle index is implicit in Titsworth.

%F a(n) = ( Sum_{k=1..n : gcd(k,n)=1} 2^( Sum_{d|n} A000010(d)/ord_d(k) ) ) / A000010(n), where ord_d(k) is the multiplicative order of k modulo d. - _Max Alekseyev_, Jun 18 2007, corrected Nov 08 2007

%t a[m_, n_] := (1/EulerPhi[n])*Sum[If[GCD[k, n] == 1, m^DivisorSum[n, EulerPhi[#] / MultiplicativeOrder[k, #]&], 0], {k, n}]; Table[a[2, n], {n, 34}] (* _Jean-François Alcover_, Dec 04 2015 *)

%o (PARI) { a(n) = sum(k=1,n, if(gcd(k,n)==1, 2^sumdiv(n,d,eulerphi(d)/znorder(Mod(k,d))), 0); ) / eulerphi(n) } /* _Max Alekseyev_, Jun 18 2007 */

%Y Cf. A002729.

%Y A row or column of A132191.

%K nonn

%O 1,1

%A _Marks R. Nester_

%E More terms from _Max Alekseyev_, Jun 18 2007