login
Array read by antidiagonals: T(m,n) = number of step cyclic shifted sequences of length n using a maximum of m different symbols.
10

%I #19 Oct 02 2017 15:20:03

%S 1,1,2,1,3,3,1,4,6,4,1,6,10,10,5,1,6,21,20,15,6,1,13,24,55,35,21,7,1,

%T 10,92,76,120,56,28,8,1,24,78,430,201,231,84,36,9,1,22,327,460,1505,

%U 462,406,120,45,10,1,45,443,2605,2015,4291,952,666,165,55,11

%N Array read by antidiagonals: T(m,n) = number of step cyclic shifted sequences of length n using a maximum of m different symbols.

%C See A056371, A002729 for an explanation of step shifts. Under step cyclic shifts, abcde, bdace, bcdea, cdeab and daceb etc. are equivalent.

%C Equivalently, the number of mappings with domain {0..n-1} and codomain {1..m} up to equivalence. Mappings A and B are equivalent if there is a d, prime to n, and a t such that A(i) = B((i*d + t) mod n) for i in {0..n-1}.

%C All column sequences are polynomials of order n.

%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 Andrew Howroyd, <a href="/A285548/b285548.txt">Table of n, a(n) for n = 1..1275</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.

%e Table starts:

%e 1 1 1 1 1 1 1 1 1 1 ...

%e 2 3 4 6 6 13 10 24 22 45 ...

%e 3 6 10 21 24 92 78 327 443 1632 ...

%e 4 10 20 55 76 430 460 2605 5164 26962 ...

%e 5 15 35 120 201 1505 2015 14070 37085 246753 ...

%e 6 21 56 231 462 4291 6966 57561 188866 1519035 ...

%e 7 28 84 406 952 10528 20140 192094 752087 7079800 ...

%e ...

%t IsLeastPoint[s_, f_] := Module[{t=f[s]}, While[t>s, t=f[t]]; Boole[s==t]];

%t c[n_, k_, t_] := Sum[IsLeastPoint[u, Mod[#*k+t, n]&], {u, 0, n-1}];

%t a[n_, x_] := Sum[If[GCD[k, n] == 1, x^c[n, k, t], 0], {t, 0, n-1}, {k, 1,

%t n}] / (n*EulerPhi[n]);

%t Table[a[n-m+1, m], {n, 1, 11}, {m, 1, n}] // Flatten (* _Jean-François Alcover_, Jun 05 2017, translated from PARI *)

%o (PARI)

%o IsLeastPoint(s,f)={my(t=f(s)); while(t>s,t=f(t));s==t}

%o C(n,k,t)=sum(u=0,n-1,IsLeastPoint(u,v->(v*k+t)%n));

%o a(n,x)=sum(t=0, n-1, sum(k=1, n, if (gcd(k, n)==1, x^C(n,k,t),0)))/(n * eulerphi(n));

%o for(m=1, 7, for(n=1, 10, print1( a(n,m), ", ") ); print(); );

%Y Rows 2-6 are A002729, A056411, A056412, A056413, A056414.

%Y Cf. A285522, A132191.

%K nonn,tabl

%O 1,3

%A _Andrew Howroyd_, Apr 20 2017