A294685
Triangle read by rows: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using exactly three colors under translational symmetry, 1 <= k <= n.
Original entry on oeis.org
0, 0, 9, 2, 91, 2022, 9, 738, 43315, 2679246, 30, 5613, 950062, 174184755, 33887517990, 91, 43404, 21480921, 11765865678, 6862930841141, 4169289730628814, 258, 338259, 497812638, 816999710223, 1429469771994078, 2605213713043722909, 4883659745750360600262, 729, 2679228, 11765822365, 57906482267826, 303941554100145501
Offset: 1
Triangle begins:
0;
0, 9;
2, 91, 2022;
9, 738, 43315, 2679246;
30, 5613, 950062, 174184755, 33887517990;
91, 43404, 21480921, 11765865678, 6862930841141, 4169289730628814;
...
- F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.
-
T(n,m)=6*sumdiv(n, d, sumdiv(m, e, eulerphi(d) * eulerphi(e) * stirling(n*m/lcm(d,e), 3, 2) ))/(n*m) \\ Andrew Howroyd, Oct 05 2024
A294686
Triangle read by rows: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using exactly four colors under translational symmetry, 1 <= k <= n.
Original entry on oeis.org
0, 0, 6, 0, 260, 20720, 6, 5112, 1223136, 257706024, 48, 81876, 67769552, 54278580036, 44900438149488, 260, 1223396, 3731753700, 11681058472672, 38403264917970196, 131160169581733489616, 1200, 17815020, 207438938000, 2570217454576416, 33725471278376393424, 460532748521625850986660, 6467585568566200114362823920, 5106, 257706012, 11681057249536, 576229125971686224
Offset: 1
Triangle begins:
0;
0, 6;
0, 260, 20720;
6, 5112, 1223136, 257706024;
48, 81876, 67769552, 54278580036, 44900438149488;
260, 1223396, 3731753700, 11681058472672, 38403264917970196, 131160169581733489616;
...
- F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.
-
T(n,m)=my(k=4); k!*sumdiv(n, d, sumdiv(m, e, eulerphi(d) * eulerphi(e) * stirling(n*m/lcm(d,e), k, 2) ))/(n*m) \\ Andrew Howroyd, Oct 05 2024
A086675
Number of n X n (0,1)-matrices modulo cyclic permutations of the rows.
Original entry on oeis.org
1, 2, 10, 176, 16456, 6710912, 11453291200, 80421421917440, 2305843009750581376, 268650182136584290872320, 126765060022823052739661424640, 241677817415439249618874010960064512, 1858395433210885261795036719974526548094976
Offset: 0
Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 27 2003
From _Gus Wiseman_, Mar 04 2019: (Start)
Inequivalent representatives of the a(2) = 10 digraphical necklace edge-sets:
{}
{(1,1)}
{(1,2)}
{(1,1),(1,2)}
{(1,1),(2,1)}
{(1,1),(2,2)}
{(1,2),(2,1)}
{(1,1),(1,2),(2,1)}
{(1,1),(1,2),(2,2)}
{(1,1),(1,2),(2,1),(2,2)}
(End)
-
Table[Fold[ #1+EulerPhi[ #2] 2^(n^2 /#2)&, 0, Divisors[n]]/n, {n, 16}]
(* second program *)
rotdigra[g_,m_]:=Sort[g/.k_Integer:>If[k==m,1,k+1]];
Table[Length[Select[Subsets[Tuples[Range[n],2]],#=={}||#==First[Sort[Table[Nest[rotdigra[#,n]&,#,j],{j,n}]]]&]],{n,0,4}] (* Gus Wiseman, Mar 04 2019 *)
A184277
Table read by antidiagonals: T(n,k) = number of distinct n X k toroidal 0..3 arrays.
Original entry on oeis.org
4, 10, 10, 24, 76, 24, 70, 700, 700, 70, 208, 8296, 29184, 8296, 208, 700, 104968, 1398500, 1398500, 104968, 700, 2344, 1399176, 71582944, 268447936, 71582944, 1399176, 2344, 8230, 19175140, 3817765120, 54975633976, 54975633976
Offset: 1
Table starts
4 10 24 70 208 700
10 76 700 8296 104968 1399176
24 700 29184 1398500 71582944 3817765120
70 8296 1398500 268447936 54975633976 11728126132976
208 104968 71582944 54975633976 45035996274688
700 1399176 3817765120 11728126132976
2344 19175140 209430787824
8230 268447816
29144
- Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 48 terms from R. H. Hardin)
- S. N. Ethier, Counting toroidal binary arrays, arXiv:1301.2352v1 [math.CO], Jan 10, 2013.
- S. N. Ethier and Jiyeon Lee, Counting toroidal binary arrays, II, arXiv:1502.03792v1 [math.CO], Feb 12, 2015.
- Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
- Peter Kagey and William Keehn, Counting tilings of the n X m grid, cylinder, and torus, arXiv:2311.13072 [math.CO], 2023. See pp. 3, 42.
-
T[n_, k_] := (1/(n*k))*Sum[Sum[EulerPhi[c]*EulerPhi[d]*4^(n*k/LCM[c, d]), {d, Divisors[k]}], {c, Divisors[n]}];
Table[T[n-k+1, k], {n, 1, 9}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 31 2017, after Andrew Howroyd *)
-
T(n, k) = (1/(n*k)) * sumdiv(n, c, sumdiv(k, d, eulerphi(c) * eulerphi(d) * 4^(n*k/lcm(c,d)))); \\ Andrew Howroyd, Sep 27 2017
A324463
Number of graphical necklaces covering n vertices.
Original entry on oeis.org
1, 0, 1, 2, 15, 156, 4665, 269618, 31573327, 7375159140, 3450904512841, 3240500443884718, 6113078165054644451, 23175001880311842459108, 176546824267008236554238517, 2701847513793569606737940203894, 83036203475880811677609125194805687
Offset: 0
Inequivalent representatives of the a(2) = 1 through a(4) = 15 graphical necklaces:
{{12}} {{12}{13}} {{12}{34}}
{{12}{13}{23}} {{13}{24}}
{{12}{13}{14}}
{{12}{13}{24}}
{{12}{13}{34}}
{{12}{14}{23}}
{{12}{24}{34}}
{{12}{13}{14}{23}}
{{12}{13}{14}{24}}
{{12}{13}{14}{34}}
{{12}{13}{24}{34}}
{{12}{14}{23}{34}}
{{12}{13}{14}{23}{24}}
{{12}{13}{14}{23}{34}}
{{12}{13}{14}{23}{24}{34}}
Cf.
A000031,
A002494,
A006129,
A008965,
A184271,
A192332 (non-covering case),
A323858,
A323859,
A323870,
A324461,
A324462,
A324464.
-
rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],#=={}||#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]]&]],{n,0,5}]
-
a(n)={if(n<1, n==0, sumdiv(n, d, eulerphi(n/d)*sum(k=0, d, (-1)^(d-k)*binomial(d,k)*2^(k*(k-1)*n/(2*d) + k*(n/d\2))))/n)} \\ Andrew Howroyd, Aug 19 2019
A324464
Number of connected graphical necklaces with n vertices.
Original entry on oeis.org
1, 0, 1, 2, 13, 148, 4530, 266614, 31451264, 7366255436, 3449652145180, 3240150686268514, 6112883022923529310, 23174784819204929919428, 176546343645071836902594288, 2701845395848698682311893154024, 83036184895986451215378727412638816, 5122922885438069578928905234650082410736
Offset: 0
Inequivalent representatives of the a(2) = 1 through a(4) = 13 graphical necklaces:
{{12}} {{12}{13}} {{12}{13}{14}}
{{12}{13}{23}} {{12}{13}{24}}
{{12}{13}{34}}
{{12}{14}{23}}
{{12}{24}{34}}
{{12}{13}{14}{23}}
{{12}{13}{14}{24}}
{{12}{13}{14}{34}}
{{12}{13}{24}{34}}
{{12}{14}{23}{34}}
{{12}{13}{14}{23}{24}}
{{12}{13}{14}{23}{34}}
{{12}{13}{14}{23}{24}{34}}
Cf.
A000031,
A000939,
A001187,
A006125,
A006129,
A008965,
A184271,
A192332,
A275527,
A323858,
A323859,
A323870,
A324461,
A324462,
A324463.
-
rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],Length[csm[#]]<=1,#=={}||#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]]&]],{n,0,5}]
-
\\ B(n,d) is graphs on n*d points invariant under 1/d rotation.
B(n,d)={2^(n*(n-1)*d/2 + n*(d\2))}
D(n,d)={my(v=vector(n, i, B(i,d)), u=vector(n)); for(n=1, #u, u[n]=v[n] - sum(k=1, n-1, binomial(n-1, k)*v[k]*u[n-k])); sumdiv(n, e, eulerphi(d*e) * moebius(e) * u[n/e] * e^(n/e-1))}
a(n)={if(n<=1, n==0, sumdiv(n, d, D(n/d,d))/n)} \\ Andrew Howroyd, Jan 24 2023
A184288
Table read by antidiagonals: T(n,k) = number of distinct n X k toroidal 0..4 arrays.
Original entry on oeis.org
5, 15, 15, 45, 175, 45, 165, 2635, 2635, 165, 629, 49075, 217125, 49075, 629, 2635, 976887, 20346485, 20346485, 976887, 2635, 11165, 20349075, 2034505661, 9536816875, 2034505661, 20349075, 11165, 48915, 435970995, 211927741375
Offset: 1
Table starts
5 15 45 165 629 2635
15 175 2635 49075 976887 20349075
45 2635 217125 20346485 2034505661 211927741375
165 49075 20346485 9536816875 4768372070757
629 976887 2034505661 4768372070757
2635 20349075 211927741375
11165 435970995
48915
- Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 39 terms from R. H. Hardin)
- S. N. Ethier, Counting toroidal binary arrays, arXiv:1301.2352v1 [math.CO], Jan 10, 2013.
- S. N. Ethier and Jiyeon Lee, Counting toroidal binary arrays, II, arXiv:1502.03792v1 [math.CO], Feb 12, 2015.
- Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
-
T[n_, k_] := (1/(n*k))*Sum[Sum[EulerPhi[c] * EulerPhi[d] * 5^(n*k/LCM[c, d]), {d, Divisors[k]}], {c, Divisors[n]}];
Table[T[n - k + 1, k], {n, 1, 9}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 31 2017, after Andrew Howroyd *)
-
T(n, k) = (1/(n*k)) * sumdiv(n, c, sumdiv(k, d, eulerphi(c) * eulerphi(d) * 5^(n*k/lcm(c,d)))); \\ Andrew Howroyd, Sep 27 2017
A184294
Table read by antidiagonals: T(n,k) = number of distinct n X k toroidal 0..7 arrays.
Original entry on oeis.org
8, 36, 36, 176, 1072, 176, 1044, 43800, 43800, 1044, 6560, 2098720, 14913536, 2098720, 6560, 43800, 107377488, 5726645688, 5726645688, 107377488, 43800, 299600, 5726689312, 2345624810432, 17592189193216, 2345624810432, 5726689312, 299600
Offset: 1
Table starts
8 36 176 1044 6560 43800
36 1072 43800 2098720 107377488 5726689312
176 43800 14913536 5726645688 2345624810432
1044 2098720 5726645688 17592189193216
6560 107377488 2345624810432
43800 5726689312
299600
- Alois P. Heinz, Antidiagonals n = 1..65, flattened (first 8 antidiagonals from R. H. Hardin)
- S. N. Ethier, Counting toroidal binary arrays, arXiv:1301.2352v1 [math.CO], Jan 10, 2013.
- S. N. Ethier and Jiyeon Lee, Counting toroidal binary arrays, II, arXiv:1502.03792v1 [math.CO], Feb 12, 2015.
- Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
-
with(numtheory):
T:= (n, k)-> add(add(phi(c)*phi(d)*8^(n*k/ilcm(c, d)),
c=divisors(n)), d=divisors(k))/(n*k):
seq(seq(T(n, 1+d-n), n=1..d), d=1..8); # Alois P. Heinz, Aug 20 2017
-
T[n_, k_] := (1/(n*k))*Sum[Sum[EulerPhi[c]*EulerPhi[d]*8^(n*(k/LCM[c, d])), {d, Divisors[k]}], {c, Divisors[n]}]; Table[T[n - k + 1, k], {n, 1, 8}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 30 2017, after Alois P. Heinz *)
-
T(n, k) = (1/(n*k)) * sumdiv(n, c, sumdiv(k, d, eulerphi(c) * eulerphi(d) * 8^(n*k/lcm(c,d)))); \\ Andrew Howroyd, Sep 27 2017
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
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
-
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}]
A368304
Table read by antidiagonals: T(n,k) is the number of tilings of the n X k torus up to horizontal and vertical reflections by an asymmetric tile.
Original entry on oeis.org
1, 4, 4, 6, 28, 6, 23, 194, 194, 23, 52, 2196, 7296, 2196, 52, 194, 26524, 350573, 350573, 26524, 194, 586, 351588, 17895736, 67136624, 17895736, 351588, 586, 2131, 4798174, 954495904, 13744131446, 13744131446, 954495904, 4798174, 2131
Offset: 1
Table begins:
n\k| 1 2 3 4 5
---+----------------------------------------------------
1 | 1 4 6 23 52
2 | 4 28 194 2196 26524
3 | 6 194 7296 350573 17895736
4 | 23 2196 350573 67136624 13744131446
5 | 52 26524 17895736 13744131446 11258999068672
6 | 194 351588 954495904 2932037300956 9607679419823148
-
A368304[n_,m_]:=1/(4*n*m) (DivisorSum[n, Function[d,DivisorSum[m,Function[c,EulerPhi[c]EulerPhi[d]4^(m*n/LCM[c,d])]]]]+If[EvenQ[n],n/2*DivisorSum[m, EulerPhi[#](4^(n*m/LCM[2,#])+4^((n-2)*m/LCM[2,#])*4^(2m/#)*Boole[EvenQ[#]])&],n*DivisorSum[m,EulerPhi[#](4^(n*m/#))&,EvenQ]]+If[EvenQ[m], m/2*DivisorSum[n,EulerPhi[#](4^(n*m/LCM[2,#])+4^((m-2)*n/LCM[2,#])*4^(2n/#)*Boole[EvenQ[#]])&],m*DivisorSum[n, EulerPhi[#](4^(m*n/#))&,EvenQ]]+Which[EvenQ[n]&&EvenQ[m],(n*m)/4 (3*2^(n*m)),OddQ[n*m],0,OddQ[n+m],(n*m)/2 (2^(n*m))])
Comments