cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 10 results.

A323861 Table read by antidiagonals where A(n,k) is the number of n X k aperiodic binary toroidal necklaces.

Original entry on oeis.org

2, 1, 1, 2, 2, 2, 3, 9, 9, 3, 6, 27, 54, 27, 6, 9, 99, 335, 335, 99, 9, 18, 326, 2182, 4050, 2182, 326, 18, 30, 1161, 14523, 52377, 52377, 14523, 1161, 30, 56, 4050, 99858, 698535, 1342170, 698535, 99858, 4050, 56, 99, 14532, 698870, 9586395, 35790267, 35790267, 9586395, 698870, 14532, 99
Offset: 1

Views

Author

Gus Wiseman, Feb 04 2019

Keywords

Comments

The 1-dimensional (Lyndon word) case is A001037.
We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.

Examples

			Table begins:
        1    2    3    4
    ------------------------
  1: |  2    1    2    3
  2: |  1    2    9   27
  3: |  2    9   54  335
  4: |  3   27  335 4050
Inequivalent representatives of the A(3,2) = 9 aperiodic toroidal necklaces:
  [0 0 0] [0 0 0] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 1 1] [0 1 1]
  [0 0 1] [0 1 1] [0 1 0] [0 1 1] [1 0 1] [1 1 0] [1 1 1] [1 0 1] [1 1 1]
		

Crossrefs

First and last columns are A001037. Main diagonal is A323872.

Programs

  • GAP
    # See link for code.
    for n in [1..8] do for k in [1..8] do Print(A323861(n,k), ", "); od; Print("\n"); od; # Andrew Howroyd, Aug 21 2019
  • Mathematica
    apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
    neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
    Table[Length[Select[Partition[#,n-k]&/@Tuples[{0,1},(n-k)*k],And[apermatQ[#],neckmatQ[#]]&]],{n,6},{k,n-1}]

Extensions

Terms a(37) and beyond from Andrew Howroyd, Aug 21 2019

A323865 Number of aperiodic binary toroidal necklaces of size n.

Original entry on oeis.org

1, 2, 2, 4, 8, 12, 36, 36, 114, 166, 396, 372, 1992, 1260, 4644, 8728, 20310, 15420, 87174, 55188, 314064, 399432, 762228, 729444, 5589620, 4026522, 10323180, 19883920, 57516048, 37025580, 286322136, 138547332, 805277760, 1041203944, 2021145660, 3926827224
Offset: 0

Views

Author

Gus Wiseman, Feb 04 2019

Keywords

Comments

We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.

Examples

			Inequivalent representatives of the a(6) = 36 aperiodic necklaces:
  000001  000011  000101  000111  001011  001101  001111  010111  011111
.
  000  000  001  001  001  001  001  011  011
  001  011  010  011  101  110  111  101  111
.
  00  00  00  00  00  01  01  01  01
  00  01  01  01  11  01  01  10  11
  01  01  10  11  01  10  11  11  11
.
  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  1  1
  0  0  0  0  1  1  1  0  1
  0  0  1  1  0  1  1  1  1
  0  1  0  1  1  0  1  1  1
  1  1  1  1  1  1  1  1  1
		

Crossrefs

Programs

  • Mathematica
    apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
    neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
    zaz[n_]:=Join@@(Table[Partition[#,d],{d,Divisors[n]}]&/@Tuples[{0,1},n]);
    Table[If[n==0,1,Length[Union[First/@matcyc/@Select[zaz[n],And[apermatQ[#],neckmatQ[#]]&]]]],{n,0,10}]

Formula

a(n) = Sum_{d|n} A323861(d, n/d) for n > 0. - Andrew Howroyd, Aug 21 2019

Extensions

Terms a(19) and beyond from Andrew Howroyd, Aug 21 2019

A323870 Number of toroidal necklaces of size n whose entries cover an initial interval of positive integers.

Original entry on oeis.org

1, 4, 10, 61, 218, 3136, 13514, 272998, 2362439, 40899248, 295024106, 14045787790, 81055130522, 3040383719360, 61408850927732, 1661142088494553, 15337737297545402, 1128511554421317128, 9768588138876674858, 803306338873366385030, 15452347618762680757428
Offset: 1

Views

Author

Gus Wiseman, Feb 04 2019

Keywords

Comments

We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. Alternatively, a toroidal necklace is a matrix that is minimal among all possible rotations of its sequence of rows and its sequence of columns.

Examples

			The a(3) = 10 toroidal necklaces:
  [1 2 3] [1 3 2] [1 2 2] [1 1 2] [1 1 1]
.
  [1] [1] [1] [1] [1]
  [2] [3] [2] [1] [1]
  [3] [2] [2] [2] [1]
		

Crossrefs

Programs

  • Mathematica
    sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
    nrmmats[n_]:=Join@@Table[Table[Table[Position[stn,{i,j}][[1,1]],{i,d},{j,n/d}],{stn,Join@@Permutations/@sps[Tuples[{Range[d],Range[n/d]}]]}],{d,Divisors[n]}];
    neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
    Table[Length[Select[nrmmats[n],neckmatQ]],{n,6}]
  • PARI
    U(n,m,k) = (1/(n*m)) * sumdiv(n, c, sumdiv(m, d, eulerphi(c) * eulerphi(d) * k^(n*m/lcm(c, d))));
    R(v)={sum(n=1, #v, sum(k=1, n, (-1)^(n-k)*binomial(n,k)*v[k]))}
    a(n)={if(n < 1, n==0, R(vector(n, k, sumdiv(n, d, U(d, n/d, k))) ))} \\ Andrew Howroyd, Aug 18 2019

Extensions

Terms a(9) and beyond from Andrew Howroyd, Aug 18 2019

A323866 Number of aperiodic toroidal necklaces of positive integers summing to n.

Original entry on oeis.org

1, 1, 1, 3, 5, 12, 18, 42, 72, 145, 262, 522, 960, 1879, 3531, 6831, 13013, 25148, 48177, 93186, 179507, 347509, 671955, 1303257, 2527162, 4910681, 9545176, 18579471, 36183505, 70540861, 137603801, 268655547, 524842088, 1026067205, 2007118657, 3928564113
Offset: 0

Views

Author

Gus Wiseman, Feb 04 2019

Keywords

Comments

The 1-dimensional (Lyndon word) case is A059966.
We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.

Examples

			Inequivalent representatives of the a(6) = 18 toroidal necklaces:
  [6] [1 5] [2 4] [1 1 4] [1 2 3] [1 3 2] [1 1 1 3] [1 1 2 2] [1 1 1 1 2]
.
  [1] [2] [1 1]
  [5] [4] [1 3]
.
  [1] [1] [1]
  [1] [2] [3]
  [4] [3] [2]
.
  [1] [1]
  [1] [1]
  [1] [2]
  [3] [2]
.
  [1]
  [1]
  [1]
  [1]
  [2]
		

Crossrefs

Programs

  • GAP
    List([0..30], A323866); # See A323861 for code; Andrew Howroyd, Aug 21 2019
  • Mathematica
    primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
    facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
    ptnmats[n_]:=Union@@Permutations/@Select[Union@@(Tuples[Permutations/@#]&/@Map[primeMS,facs[n],{2}]),SameQ@@Length/@#&];
    apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
    neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
    Table[If[n==0,1,Length[Union@@Table[Select[ptnmats[k],And[apermatQ[#],neckmatQ[#]]&],{k,Times@@Prime/@#&/@IntegerPartitions[n]}]]],{n,0,10}]

Extensions

Terms a(16) and beyond from Andrew Howroyd, Aug 21 2019

A323869 Number of aperiodic matrices of size n whose entries cover an initial interval of positive integers.

Original entry on oeis.org

1, 4, 24, 212, 1080, 18672, 94584, 2182752, 21261708, 408988080, 3245265144, 168549358368, 1053716696760, 42565371692592, 921132763909200, 26578273403903040, 260741534058271800, 20313207979498492344, 185603174638656822264, 16066126777465282744800, 324499299994016295338064
Offset: 1

Views

Author

Gus Wiseman, Feb 04 2019

Keywords

Comments

An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.

Examples

			The a(3) = 24 matrices:
  [123][132][213][312][231][321][122][211][112][221][121][212]
.
  [1][1][2][3][2][3][1][2][1][2][1][2]
  [2][3][1][1][3][2][2][1][1][2][2][1]
  [3][2][3][2][1][1][2][1][2][1][1][2]
		

Crossrefs

Programs

  • GAP
    List([1..30], A323869); # See A323861 for code; Andrew Howroyd, Aug 21 2019
  • Mathematica
    sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
    nrmmats[n_]:=Join@@Table[Table[Table[Position[stn,{i,j}][[1,1]],{i,d},{j,n/d}],{stn,Join@@Permutations/@sps[Tuples[{Range[d],Range[n/d]}]]}],{d,Divisors[n]}];
    apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
    Table[Length[Select[nrmmats[n],apermatQ]],{n,6}]

Formula

a(n) = n*A323871(n). - Andrew Howroyd, Aug 21 2019

Extensions

Terms a(9) and beyond from Andrew Howroyd, Aug 21 2019

A324513 Number of aperiodic cycle necklaces with n vertices.

Original entry on oeis.org

1, 0, 0, 0, 2, 7, 51, 300, 2238, 18028, 164945, 1662067, 18423138, 222380433, 2905942904, 40864642560, 615376173176, 9880203467184, 168483518571789, 3041127459127222, 57926238289894992, 1161157775616335125, 24434798429947993043, 538583682037962702384
Offset: 1

Views

Author

Gus Wiseman, Mar 04 2019

Keywords

Comments

We define an aperiodic cycle necklace to be an equivalence class of (labeled, undirected) Hamiltonian cycles under rotation of the vertices such that all n of these rotations are distinct.

Crossrefs

Cf. A000740, A000939, A001037 (binary Lyndon words), A008965, A059966 (Lyndon compositions), A060223 (normal Lyndon words), A061417, A064852 (if cycle is oriented), A086675, A192332, A275527, A323866 (aperiodic toroidal arrays), A323871.

Programs

  • Mathematica
    rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
    Table[Length[Select[Union[Sort[Sort/@Partition[#,2,1,1]]&/@Permutations[Range[n]]],#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]&&UnsameQ@@Table[Nest[rotgra[#,n]&,#,j],{j,n}]&]],{n,8}]
  • PARI
    a(n)={if(n<3, n==0||n==1, (if(n%2, 0, -(n/2-1)!*2^(n/2-2)) + sumdiv(n, d, moebius(n/d)*eulerphi(n/d)*(n/d)^d*d!/n^2))/2)} \\ Andrew Howroyd, Aug 19 2019

Formula

a(n) = A324512(n)/n.
a(2*n+1) = A064852(2*n+1)/2 for n > 0; a(2*n) = (A064852(2*n) - A002866(n-1))/2 for n > 1. - Andrew Howroyd, Aug 16 2019

Extensions

Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019

A306669 Number of aperiodic permutation necklaces of weight n.

Original entry on oeis.org

1, 0, 1, 4, 23, 110, 719, 4992, 40302, 362492, 3628799, 39912804, 479001599, 6226974714, 87178289207, 1307673722880, 20922789887999, 355687417744992, 6402373705727999, 121645100223036700, 2432902008176115023, 51090942167993548790, 1124000727777607679999
Offset: 1

Views

Author

Gus Wiseman, Mar 04 2019

Keywords

Comments

A permutation is aperiodic if every rotation of {1...n} acts on the vertices of the cycle decomposition to produce a different digraph. A permutation necklace is an equivalence class of permutations under the action of rotation of vertices in the cycle decomposition. The corresponding action on words applies m -> m + 1 for m < n and n -> 1, and rotates once to the right. For example, (24531) first becomes (35142) under the application of cyclic rotation, and then is rotated right to give (23514).

Crossrefs

Programs

  • Mathematica
    Table[Length[Select[Permutations[Range[n]],UnsameQ@@NestList[RotateRight[#/.k_Integer:>If[k==n,1,k+1]]&,#,n-1]&]]/n,{n,6}]
  • PARI
    a(n) = (1/n)*sumdiv(n, d, moebius(n/d)*(n/d)^d*d!); \\ Andrew Howroyd, Aug 19 2019

Formula

a(n) = A324514(n)/n.
a(n) = (1/n)*Sum_{d|n} mu(n/d)*(n/d)^d*d!. - Andrew Howroyd, Aug 19 2019

Extensions

Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019

A323872 Number of n X n aperiodic binary toroidal necklaces.

Original entry on oeis.org

1, 2, 2, 54, 4050, 1342170, 1908852102, 11488774559598, 288230375950387200, 29850020237398244599296, 12676506002282260237970435130, 21970710674130840874443091905460038, 154866286100907105149455216472736043777350, 4427744605404865645682169434028029029963535277450
Offset: 0

Views

Author

Gus Wiseman, Feb 04 2019

Keywords

Comments

The 1-dimensional (Lyndon word) case is A001037.
We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.

Examples

			Inequivalent representatives of the a(2) = 2 aperiodic necklaces:
  [0 0] [0 1]
  [0 1] [1 1]
Inequivalent representatives of the a(3) = 54 aperiodic necklaces:
  000  000  000  000  000  000  000  000  000
  000  000  001  001  001  001  001  001  001
  001  011  001  010  011  100  101  110  111
.
  000  000  000  000  000  000  000  000  000
  011  011  011  011  011  011  011  111  111
  001  010  011  100  101  110  111  001  011
.
  001  001  001  001  001  001  001  001  001
  001  001  001  001  001  001  010  010  010
  010  011  100  101  110  111  011  101  110
.
  001  001  001  001  001  001  001  001  001
  010  011  011  011  011  011  100  100  100
  111  010  011  101  110  111  011  110  111
.
  001  001  001  001  001  001  001  001  001
  101  101  101  101  110  110  110  110  111
  011  101  110  111  011  101  110  111  011
.
  001  001  001  011  011  011  011  011  011
  111  111  111  011  011  011  101  110  111
  101  110  111  101  110  111  111  111  111
		

Crossrefs

Programs

  • Mathematica
    apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
    neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
    Table[Length[Select[(Partition[#,n]&)/@Tuples[{0,1},n^2],And[apermatQ[#],neckmatQ[#]]&]],{n,4}]

Extensions

Terms a(5) and beyond from Andrew Howroyd, Aug 21 2019

A323868 Number of matrices of size n whose entries cover an initial interval of positive integers.

Original entry on oeis.org

1, 6, 26, 225, 1082, 18732, 94586, 2183340, 21261783, 408990252, 3245265146, 168549405570, 1053716696762, 42565371881772, 921132763911412, 26578273409906775, 260741534058271802, 20313207979541071938, 185603174638656822266, 16066126777466305218690
Offset: 1

Views

Author

Gus Wiseman, Feb 04 2019

Keywords

Examples

			The 42 matrices of size 4 whose entries cover {1,2}:
  1222 2111 1122 2211 1212 2121 1221 2112 1112 2221 1121 2212 1211 2122
.
  12  21  11  22  12  21  12  21  11  22  11  22  12  21
  22  11  22  11  12  21  21  12  12  21  21  12  11  22
.
  1   2   1   2   1   2   1   2   1   2   1   2   1   2
  2   1   1   2   2   1   2   1   1   2   1   2   2   1
  2   1   2   1   1   2   2   1   1   2   2   1   1   2
  2   1   2   1   2   1   1   2   2   1   1   2   1   2
The 18 matrices of size 4 whose entries cover {1,2} with multiplicities {2,2}:
  [1 1 2 2] [2 2 1 1] [1 2 1 2] [2 1 2 1] [1 2 2 1] [2 1 1 2]
.
  [1 1] [2 2] [1 2] [2 1] [1 2] [2 1]
  [2 2] [1 1] [1 2] [2 1] [2 1] [1 2]
.
  [1] [2] [1] [2] [1] [2]
  [1] [2] [2] [1] [2] [1]
  [2] [1] [1] [2] [2] [1]
  [2] [1] [2] [1] [1] [2]
		

Crossrefs

Programs

  • Maple
    b:= proc(n) option remember; `if`(n=0, 1,
          add(b(n-j)*binomial(n, j), j=1..n))
        end:
    a:= n-> b(n)*numtheory[tau](n):
    seq(a(n), n=1..20);  # Alois P. Heinz, Feb 04 2019
  • Mathematica
    sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
    nrmmats[n_]:=Join@@Table[Table[Table[Position[stn,{i,j}][[1,1]],{i,d},{j,n/d}],{stn,Join@@Permutations/@sps[Tuples[{Range[d],Range[n/d]}]]}],{d,Divisors[n]}];
    Table[Length[nrmmats[n]],{n,6}]
    Table[DivisorSigma[0, n]*Sum[k! StirlingS2[n, k], {k, 1, n}], {n, 1, 20}] (* Vaclav Kotesovec, Feb 05 2019 *)
  • PARI
    a(n) = numdiv(n)*sum(k=0, n, stirling(n, k, 2)*k!); \\ Michel Marcus, Feb 05 2019

Formula

a(n) = A000005(n) * A000670(n).

A306715 Number of graphical necklaces with n vertices and distinct rotations.

Original entry on oeis.org

1, 0, 2, 12, 204, 5372, 299592, 33546240, 7635496960, 3518433853392, 3275345183542176, 6148914685509544960, 23248573454127484128960, 176848577040728399988915648, 2704321280486889389857342715776, 83076749736557240903566436660674560
Offset: 1

Views

Author

Gus Wiseman, Mar 05 2019

Keywords

Comments

A simple graph with n vertices has distinct rotations if all n rotations of its vertex set act on the edge set to give distinct graphs. A graphical necklace is a simple graph that is minimal among all n rotations of the vertices.

Crossrefs

Cf. A000088, A001037, A006125, A059966, A060223, A086675, A192332 (graphical necklaces), A306669, A323861, A323865, A323866, A323871, A324461 (distinct rotations), A324513.

Programs

  • Mathematica
    rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
    Table[Length[Select[Subsets[Subsets[Range[n],{2}]],With[{rots=Table[Nest[rotgra[#,n]&,#,j],{j,n}]},UnsameQ@@rots&&#==First[Sort[rots]]]&]],{n,5}]
  • PARI
    a(n)={if(n==0, 1, sumdiv(n, d, moebius(d)*2^(n*(n/d-1)/2 + n*(d\2)/d))/n)} \\ Andrew Howroyd, Aug 15 2019

Formula

a(n > 0) = A324461(n)/n.
a(n) = (1/n)*Sum_{d|n} mu(d)*2^(n*(n/d-1)/2 + n*floor(d/2)/d) for n > 0. - Andrew Howroyd, Aug 15 2019

Extensions

Terms a(7) and beyond from Andrew Howroyd, Aug 15 2019
Showing 1-10 of 10 results.