A285522 -id:A285522 - 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

A132191 Square array a(m,n) read by antidiagonals, defined by A000010(n)*a(m,n) = Sum_{k=1..n, gcd(k,n)=1} m^{ Sum_{d|n} A000010(d)/ (multiplicative order of k modulo d) }.

Original entry on oeis.org

1, 1, 2, 1, 4, 3, 1, 6, 9, 4, 1, 12, 18, 16, 5, 1, 12, 54, 40, 25, 6, 1, 40, 72, 160, 75, 36, 7, 1, 28, 405, 280, 375, 126, 49, 8, 1, 96, 390, 2176, 825, 756, 196, 64, 9, 1, 104, 1944, 2800, 8125, 2016, 1372, 288, 81, 10, 1, 280, 3411, 17920, 13175, 23976, 4312, 2304, 405

Offset: 1

N. J. A. Sloane, Dec 01 2007, based on email from Max Alekseyev, Nov 08 2007

From Andrew Howroyd, Apr 22 2017: (Start)
Number of step shifted (decimated) sequences of length n using a maximum of m different symbols. See A056371 for an explanation of step shifts. -
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, such that A(i) = B(i*d mod n) for i in {0..n-1}. (End)

			Array begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
2, 4, 6, 12, 12, 40, 28, 96, 104, 280, 216, 1248, 704, 2800, 4344, 8928, 8232, 44224, 29204, 136032, ...
3, 9, 18, 54, 72, 405, 390, 1944, 3411, 14985, 17802, 139968, 133104, 798525, 1804518, 5454378, 8072532, 64599849, 64573626, 437732424, ...
4, 16, 40, 160, 280, 2176, 2800, 17920, 44224, 263296, 419872, 4280320, 5594000, 44751616, 134391040, 539054080, 1073758360, 11453771776, 15271054960, 137575813120, ...
5, 25, 75, 375, 825, 8125, 13175, 103125, 327125, 2445625, 4884435, 61640625, 101732425, 1017323125, 3816215625, 19104609375, 47683838325, 635787765625, 1059638680675, 11924780390625, ...

Vincenzo Librandi, Table of n, a(n) for n = 1..1830
Max Alekseyev, First 20 rows and columns of table
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.

Row m=2 is A056371
Row m=3 is A056372
Row m=4 is A056373
Row m=5 is A056374
Row m=6 is A056375
Column n=2 is A000290
Column n=3 is A002411
Column n=4 is A019582
Cf. A285522, A285548.

a[m_, n_] := (1/EulerPhi[n])*Sum[If[GCD[k, n]==1, m^DivisorSum[n, EulerPhi[#] / MultiplicativeOrder[k, #]&], 0], {k, 1, n}]; Table[a[m-n+1, n], {m, 1, 15}, {n, m, 1, -1}] // Flatten (* Jean-François Alcover, Dec 01 2015 *)

for(i=1,15,for(m=1,i,n=i-m+1; print1(sum(k=1, n, if(gcd(k,n)==1, m^sumdiv(n,d,eulerphi(d)/znorder(Mod(k,d))),0))/eulerphi(n)","))) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Apr 26 2008

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Apr 26 2008

Offset corrected by Andrew Howroyd, Apr 20 2017

A288620 Triangle read by rows: T(n,k) = number of step shifted (decimated) sequence structures of length n using exactly k different symbols.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 5, 4, 1, 1, 5, 8, 3, 1, 1, 19, 50, 37, 9, 1, 1, 13, 54, 63, 26, 4, 1, 1, 47, 284, 479, 299, 83, 11, 1, 1, 51, 525, 1316, 1183, 454, 82, 8, 1, 1, 139, 2370, 8597, 10701, 5761, 1492, 196, 13, 1, 1, 107, 2872, 14619, 24736, 17998, 6429, 1198, 119, 6, 1

Offset: 1

Andrew Howroyd, Jun 11 2017

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

			Triangle begins
1;
1,  1;
1,  2,   1;
1,  5,   4,    1;
1,  5,   8,    3,    1;
1, 19,  50,   37,    9,   1;
1, 13,  54,   63,   26,   4,  1;
1, 47, 284,  479,  299,  83, 11, 1;
1, 51, 525, 1316, 1183, 454, 82, 8, 1;
...

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]

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Columns 2-6 are A056396, A056397, A056398, A056399, A056400.
Row sums are A288621.
Partial row sums include A056391, A056392, A056393, A056394, A056395.
Cf. A056371, A288627, A285522, A285548, A132191.

\\ see A056391 for Polya enumeration functions
T(n,k) = NonequivalentStructsExactly(StepShiftPerms(n), k); \\ Andrew Howroyd, Oct 14 2017

A288627 Triangle read by rows: T(n,k) = number of step cyclic shifted sequence structures of length n using exactly k different symbols.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 2, 3, 1, 1, 1, 7, 14, 11, 3, 1, 1, 4, 11, 13, 6, 1, 1, 1, 13, 52, 83, 52, 18, 3, 1, 1, 10, 72, 162, 148, 59, 13, 2, 1, 1, 25, 274, 930, 1140, 630, 171, 28, 3, 1, 1, 14, 281, 1369, 2306, 1681, 612, 118, 14, 1, 1

Offset: 1

Andrew Howroyd, Jun 11 2017

See A056371 for an explanation of step shifts. Under step cyclic shifts, abcde, bdace, bcdea, cdeab and daceb etc. are equivalent. Permuting the symbols will not change the structure.

			Triangle begins
1;
1,  1;
1,  1,   1;
1,  3,   2,   1;
1,  2,   3,   1,    1;
1,  7,  14,  11,    3,   1;
1,  4,  11,  13,    6,   1,   1;
1, 13,  52,  83,   52,  18,   3,  1;
1, 10,  72, 162,  148,  59,  13,  2, 1;
1, 25, 274, 930, 1140, 630, 171, 28, 3, 1;
...

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]

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Columns 2-6 are A056434, A056435, A056436, A056437, A056438.
Row sums are A288628.
Partial row sums include A056429, A056430, A056431, A056432, A056433.
Cf. A056391, A056371, A288620, A285522, A285548, A132191.

\\ see A056391 for Polya enumeration functions
T(n,k) = NonequivalentStructsExactly(CyclicStepShiftPerms(n), k); \\ Andrew Howroyd, Oct 14 2017

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

Original entry on oeis.org

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, 10, 92, 76, 120, 56, 28, 8, 1, 24, 78, 430, 201, 231, 84, 36, 9, 1, 22, 327, 460, 1505, 462, 406, 120, 45, 10, 1, 45, 443, 2605, 2015, 4291, 952, 666, 165, 55, 11

Offset: 1

Andrew Howroyd, Apr 20 2017

See A056371, A002729 for an explanation of step shifts. Under step cyclic shifts, abcde, bdace, bcdea, cdeab and daceb etc. are equivalent.
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}.
All column sequences are polynomials of order n.

			Table starts:
1  1  1   1   1     1     1      1      1       1 ...
2  3  4   6   6    13    10     24     22      45 ...
3  6 10  21  24    92    78    327    443    1632 ...
4 10 20  55  76   430   460   2605   5164   26962 ...
5 15 35 120 201  1505  2015  14070  37085  246753 ...
6 21 56 231 462  4291  6966  57561 188866 1519035 ...
7 28 84 406 952 10528 20140 192094 752087 7079800 ...
...

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]

Andrew Howroyd, Table of n, a(n) for n = 1..1275
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.

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

Cf. A285522, A132191.

IsLeastPoint[s_, f_] := Module[{t=f[s]}, While[t>s, t=f[t]]; Boole[s==t]];
c[n_, k_, t_] := Sum[IsLeastPoint[u, Mod[#*k+t, n]&], {u, 0, n-1}];
a[n_, x_] := Sum[If[GCD[k, n] == 1, x^c[n, k, t], 0], {t, 0, n-1}, {k, 1,
n}] / (n*EulerPhi[n]);
Table[a[n-m+1, m], {n, 1, 11}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jun 05 2017, translated from PARI *)

IsLeastPoint(s,f)={my(t=f(s)); while(t>s,t=f(t));s==t}
C(n,k,t)=sum(u=0,n-1,IsLeastPoint(u,v->(v*k+t)%n));
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));
for(m=1, 7, for(n=1, 10, print1( a(n,m), ", ") ); print(); );

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

A132191 Square array a(m,n) read by antidiagonals, defined by A000010(n)*a(m,n) = Sum_{k=1..n, gcd(k,n)=1} m^{ Sum_{d|n} A000010(d)/ (multiplicative order of k modulo d) }.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A288620 Triangle read by rows: T(n,k) = number of step shifted (decimated) sequence structures of length n using exactly k different symbols.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

A288627 Triangle read by rows: T(n,k) = number of step cyclic shifted sequence structures of length n using exactly k different symbols.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI