A294792 -id:A294792 - cp's OEIS frontend

A294791 Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly two colors under translational symmetry and swappable colors.

0, 1, 4, 1, 7, 31, 3, 23, 179, 2107, 3, 55, 1095, 26271, 671103, 7, 189, 7327, 350063, 17896831, 954459519, 9, 595, 49939, 4794087, 490853415, 52357746895, 5744387279871, 19, 2101, 349715, 67115111, 13743921631, 2932032057731, 643371380132743, 144115188277194943, 29, 7315, 2485591, 954444607, 390937468407, 166799988703927, 73201365371896619

Offset: 1

Marko Riedel, Nov 08 2017

Two colorings are equivalent if there is a permutation of the colors that takes one to the other in addition to translational symmetries on the torus. (Power Group Enumeration.)

			For the 2 X 2 grid and two colors we find T(2,2) = 4:
  +---+  +---+  +---+  +---+
  |X| |  |X| |  |X|X|  |X| |
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | |X|  | | |  |X| |
  +-+-+  +-+-+  +-+-+  +-+-+

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.

Marko Riedel et al., Burnside lemma and translational symmetries of the torus.
Marko Riedel, Maple code for sequences A294791, A294792, A294793, A294794.

Cf. A152175, A294684, A294685, A294686, A294687, A294792, A294793, A294794, A295197. T(n,1) is A056295.

T(n,k) = (1/(n*k*Q!))*(Sum_{sigma in S_Q} Sum_{d|n} Sum_{f|k} phi(d) phi(f) [[forall j_l(sigma) > 0 : l|lcm(d,f) ]] P(gcd(d,f)*(n/d)*(k/f), sigma)) where P(F, sigma) = F! [z^F] Product_{l=1..Q} (exp(lz)-1)^j_l(sigma) with Q=2. The notation j_l(sigma) is from the Harary text and gives the number of cycles of length l in the permutation sigma. [[.]] is an Iverson bracket.

A294793 Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly four colors under translational symmetry and swappable colors.

Original entry on oeis.org

0, 0, 1, 0, 13, 874, 1, 235, 51075, 10741819, 2, 3437, 2823766, 2261625725, 1870851589562, 13, 51275, 155495153, 486711524815, 1600136051453135, 5465007068038102643, 50, 742651, 8643289534, 107092397450897, 1405227969932349726, 19188864521773558375127, 269482732023591671431784330, 221, 10741763, 486710971595, 24009547064476683

Offset: 1

Marko Riedel, Nov 08 2017

Two colorings are equivalent if there is a permutation of the colors that takes one to the other in addition to translational symmetries on the torus. (Power Group Enumeration.)

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.

Marko Riedel et al., Burnside lemma and translational symmetries of the torus.

Cf. A294684, A294685, A294686, A294687, A294791, A294792, A294794, A295197. T(n,1) is A056297.

T(n,k) = (1/(n*k*Q!))*(Sum_{sigma in S_Q} Sum_{d|n} Sum_{f|k} phi(d) phi(f) [[forall j_l(sigma) > 0 : l|lcm(d,f) ]] P(gcd(d,f)*(n/d)*(k/f), sigma)) where P(F, sigma) = F! [z^F] Product_{l=1..Q} (exp(lz)-1)^j_l(sigma) with Q=4. The notation j_l(sigma) is from the Harary text and gives the number of cycles of length l in the permutation sigma. [[.]] is an Iverson bracket.

A294684 Triangle read by rows: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using exactly two colors under translational symmetry, 1 <= k <= n.

Original entry on oeis.org

0, 1, 5, 2, 12, 62, 4, 38, 350, 4154, 6, 106, 2190, 52486, 1342206, 12, 360, 14622, 699598, 35792566, 1908897150, 18, 1180, 99878, 9587578, 981706830, 104715443850, 11488774559742, 34, 4148, 699250, 134223974, 27487816990, 5864063066498, 1286742755471398, 288230376353050814

Offset: 1

Marko Riedel, Nov 06 2017

Colors are not being permuted, i.e., Power Group Enumeration does not apply here.

			Triangle begins:
   0;
   1,    5;
   2,   12,    62;
   4,   38,   350,    4154;
   6,  106,  2190,   52486,   1342206;
  12,  360, 14622,  699598,  35792566,   1908897150;
  18, 1180, 99878, 9587578, 981706830, 104715443850, 11488774559742;
  ...
For the 2 X 2 and two colors we find
  +---+  +---+  +---+  +---+  +---+
  |X| |  | |X|  |X| |  |X|X|  |X| |
  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  |X|X|  | |X|  | | |  |X| |
  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)
Marko Riedel et al., Burnside lemma and translational symmetries of the torus.
Marko Riedel, Maple code for sequences A294684, A294685, A294686, A294687.

Main diagonal is A376822.

Cf. A184271, A294685, A294686, A294687, A294791, A294792, A294793, A294794. T(n,1) is A052823.

With[{Q = 2}, Table[(Q!/n/k) Sum[Sum[EulerPhi[d] EulerPhi[f] StirlingS2[GCD[d, f] (n/d) (k/f), Q], {f, Divisors@ k}], {d, Divisors@ n}], {n, 8}, {k, n}]] // Flatten (* Michael De Vlieger, Nov 08 2017 *)

T(n,m) = {2*sumdiv(n, d, sumdiv(m, e, eulerphi(d) * eulerphi(e) * stirling(n*m/lcm(d,e), 2, 2) ))/(n*m)} \\ Andrew Howroyd, Oct 05 2024

T(n,k) = (Q!/(n*k))*(Sum_{d|n} Sum_{f|k} phi(d) phi(f) S(gcd(d,f)*(n/d)*(k/f), Q)) with Q=2 and S(n,k) Stirling numbers of the second kind.

T(n,k) = A184271(n,k) - 2. - Andrew Howroyd, Oct 05 2024

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

Marko Riedel, Nov 06 2017

Colors are not being permuted, i.e., Power Group Enumeration does not apply here.

			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.

Andrew Howroyd, Table of n, a(n) for n = 1..820 (first 40 rows)
Marko Riedel et al., Burnside lemma and translational symmetries of the torus.

Main diagonal is A376823.

Cf. A184271, A184284, A294684, A294686, A294687, A294791, A294792, A294793, A294794. T(n,1) is A056283.

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

T(n,k) = (Q!/(n*k))*(Sum_{d|n} Sum_{f|k} phi(d) phi(f) S(gcd(d,f)*(n/d)*(k/f), Q)) with Q=3 and S(n,k) Stirling numbers of the second kind.

T(n,k) = A184284(n,k) - 3*A184271(n,k) + 3. - 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

Marko Riedel, Nov 06 2017

Colors are not being permuted, i.e., Power Group Enumeration does not apply here.

			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.

Andrew Howroyd, Table of n, a(n) for n = 1..820 (first 40 rows)
Marko Riedel et al., Burnside lemma and translational symmetries of the torus.

Main diagonal is A376824.
Cf. A294684, A294685, A294687, A294791, A294792, A294793, A294794. T(n,1) is A056284.
Cf. A184271, A184284, A184277.

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

T(n,k) = (Q!/(n*k))*(Sum_{d|n} Sum_{f|k} phi(d) phi(f) S(gcd(d,f)*(n/d)*(k/f), Q)) with Q=4 and S(n,k) Stirling numbers of the second kind.

T(n,k) = A184277(n,k) - 4*A184284(n,k) + 6*A184271(n,k) - 4. - Andrew Howroyd, Oct 05 2024

A294687 Triangle read by rows: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using exactly five colors under translational symmetry, 1 <= k <= n.

Original entry on oeis.org

0, 0, 0, 0, 300, 92680, 0, 15750, 13794150, 8221452750, 24, 510312, 1686135376, 4495236798162, 11696087875731720, 300, 13794450, 193054017440, 2425003938178050, 30852000867277668428, 403564024914127655401650, 2400, 343501500, 21664357535320, 1317601563731383350, 82985159653854019928352, 5411356249329837891442095560

Offset: 1

Marko Riedel, Nov 06 2017

Colors are not being permuted, i.e., Power Group Enumeration does not apply here.

			Triangle begins:
   0;
   0,      0;
   0,    300,      92680;
   0,  15750,   13794150,    8221452750;
  24, 510312, 1686135376, 4495236798162, 11696087875731720;
  ...

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.

Andrew Howroyd, Table of n, a(n) for n = 1..325 (first 25 rows).
Marko Riedel et al., Burnside lemma and translational symmetries of the torus.

Main diagonal is A376825.

Cf. A294684, A294685, A294686, A294791, A294792, A294793, A294794. T(n,1) is A056285.

T(n,m)=my(k=5); 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

T(n,k) = (Q!/(n*k))*(Sum_{d|n} Sum_{f|k} phi(d) phi(f) S(gcd(d,f)*(n/d)*(k/f), Q)) with Q=5 and S(n,k) Stirling numbers of the second kind.

A294794 Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly five colors under translational symmetry and swappable colors.

Original entry on oeis.org

0, 0, 0, 0, 3, 775, 0, 145, 115100, 68522769, 1, 4281, 14051164, 37460388596, 97467398965031, 3, 115381, 1608801153, 20208371722051, 257100007425866689, 3363033541015148835823, 20, 2863227, 180536313547, 10980013072900632, 691542997115450167856, 45094635411084308447578413, 3020745549854628001139950947779, 136, 68522707

Offset: 1

Marko Riedel, Nov 08 2017

Two colorings are equivalent if there is a permutation of the colors that takes one to the other in addition to translational symmetries on the torus. (Power Group Enumeration.)

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.

Marko Riedel et al., Burnside lemma and translational symmetries of the torus.

Cf. A294684, A294685, A294686, A294687, A294791, A294792, A294793, A295197. T(n,1) is A056298.

T(n,k) = (1/(n*k*Q!))*(Sum_{sigma in S_Q} Sum_{d|n} Sum_{f|k} phi(d) phi(f) [[forall j_l(sigma) > 0 : l|lcm(d,f) ]] P(gcd(d,f)*(n/d)*(k/f), sigma)) where P(F, sigma) = F! [z^F] Product_{l=1..Q} (exp(lz)-1)^j_l(sigma) with Q=5. The notation j_l(sigma) is from the Harary text and gives the number of cycles of length l in the permutation sigma. [[.]] is an Iverson bracket.

A295197 Triangle read by rows: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using any number of swappable colors, 1 <= k <= n.

Original entry on oeis.org

1, 2, 9, 3, 43, 2387, 7, 587, 351773, 655089857, 12, 11703, 92197523, 2586209749712, 185543613289205809, 43, 352902, 37893376167, 18581620064907130, 28224967150633208580385, 106103186941524316132396201360, 127, 13639372, 22612848403571, 220019264470242220839, 8045720086273150473238405274, 851013076163633746725692124186472539, 218900758256599151027392153440612298654753249

Offset: 1

Marko Riedel, Nov 16 2017

Two colorings are equivalent if there is a permutation of the colors that takes one to the other in addition to translational symmetries on the torus. (Power Group Enumeration.) Maximum number of colors is n * k.

			The two-by-two with swappable colors has one monochrome coloring, four colorings with two colors, three colorings with three colors (determined by the color that appears twice) and one coloring with four colors.
Triangle begins:
   1;
   2,     9;
   3,    43,     2387;
   7,   587,   351773,     655089857;
  12, 11703, 92197523, 2586209749712, 185543613289205809;
  ...

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.

Andrew Howroyd, Table of n, a(n) for n = 1..300 (24 rows; first 36 terms from Marko Riedel)
Marko Riedel et al., Burnside lemma and translational symmetries of the torus.
Marko Riedel, Maple code for sequence A295197, computing all colorings at once with no prior classification.
Marko Riedel, Maple code for sequence A295197, classifying by the exact number of colors that appear.

Main diagonal is A376808.

Cf. A162663, A294791, A294792, A294793, A294794. T(n,1) is A084423.

\\ B(m,n) is A162663(n,m).
B(m,n)={n!*polcoef(exp(sumdiv(m,d, (exp(d*x + O(x*x^n))-1)/d)), n)}
T(n,k)={my(v=vector(lcm(n,k))); fordiv(n,d, fordiv(k,e, v[lcm(d,e)] += eulerphi(d) * eulerphi(e) )); sumdiv(#v, g, v[g]*B(g,n*k/g))/(n*k)} \\ Andrew Howroyd, Oct 06 2024

T(n,k) = Sum_{Q=1..n*k} (1/(n*k*Q!))*(Sum_{sigma in S_Q} Sum_{d|n} Sum_{f|k} phi(d) phi(f) [[forall j_l(sigma) > 0 : l|lcm(d,f) ]] P(gcd(d,f)*(n/d)*(k/f), sigma)) where P(F, sigma) = F! [z^F] Product_{l=1..Q} (exp(lz)-1)^j_l(sigma). The notation j_l(sigma) is from the Harary text and gives the number of cycles of length l in the permutation sigma. [[.]] is an Iverson bracket.

T(n,k) = (Sum_{d|n} Sum_{f|k} phi(d) * phi(f) * A162663(n*k/lcm(d,f), lcm(d,f)))/(n*k). - Andrew Howroyd, Oct 06 2024

A376808 Number of non-isomorphic colorings of a toroidal n X n grid using any number of swappable colors.

Original entry on oeis.org

1, 9, 2387, 655089857, 185543613289205809, 106103186941524316132396201360, 218900758256599151027392153440612298654753249, 2689595989958732045849530682270318547733917269644639109073775285

Offset: 1

Marko Riedel, Oct 04 2024

nonn

Two colorings are equivalent if there is a permutation of the colors that takes one to the other in addition to translational symmetries on the torus (Power Group Enumeration). The maximum number of colors is n * n.

			For the 2x2 we find
  +-+-+   +-+-+   +-+-+   +-+-+   +-+-+
  |X|X|   |X|X|   |X|X|   |X| |   |X| |
  +-+-+   +-+-+   +-+-+   +-+-+   +-+-+
  |X|X|   |X| |   | | |   |X| |   | |X|
  +-+-+   +-+-+   +-+-+   +-+-+   +-+-+
  +-+-+   +-+-+   +-+-+   +-+-+
  |X|Y|   |X| |   |X| |   |X|Y|
  +-+-+   +-+-+   +-+-+   +-+-+
  | | |   |Y| |   | |Y|   |Z| |
  +-+-+   +-+-+   +-+-+   +-+-+
so a(2) = 9.

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.

Andrew Howroyd, Table of n, a(n) for n = 1..24
Marko Riedel et al., Burnside lemma and translational symmetries of the torus.
Marko Riedel, Maple code for sequence by PGE.

Main diagonal of A295197.

Cf. A294791, A294792, A294793, A294794.

a(n) = Sum_{Q=1..n^2} (1/(n^2*Q!))*(Sum_{sigma in S_Q} Sum_{d|n} Sum_{f|n} phi(d) phi(f) [[forall j_l(sigma) > 0 : l|lcm(d,f) ]] P(gcd(d,f)*(n/d)*(n/f), sigma)) where P(F, sigma) = F! [z^F] Product_{l=1..Q} (exp(lz)-1)^j_l(sigma). The notation j_l(sigma) is from the Harary text and gives the number of cycles of length l in the permutation sigma. [[.]] is an Iverson bracket.

A376748 Number of non-isomorphic colorings of a toroidal n X n grid using exactly three swappable colors.

Original entry on oeis.org

0, 3, 345, 447156, 5647919665, 694881637942816, 813943290958393433377, 8941884948534360647405572800, 912400181570021638669407666368774097, 858962534553352212055863239761275173880606456, 7425662396340624836407113113710889289196975262054947345, 587417576454184723055270940786413231085263155884260701824558793960

Offset: 1

Marko Riedel, Oct 03 2024

nonn

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973.

Marko Riedel et al., Burnside lemma and translational symmetries of the torus.
Marko Riedel, Maple code for sequence.

Main diagonal of A294792.

Cf. A376747, A376749, A376808, A376823.

a(n) = (1/(n^2*3!))*(Sum_{sigma in S_3} Sum_{d|n} Sum_{f|n} phi(d) phi(f) [[forall j_l(sigma) > 0 : l|lcm(d,f) ]] P(gcd(d,f)*(n/d)*(n/f), sigma)) where P(F, sigma) = F! [z^F] Product_{l=1..3} (exp(lz)-1)^j_l(sigma). The notation j_l(sigma) is from the Harary text and gives the number of cycles of length l in the permutation sigma. [[.]] is an Iverson bracket.

cp's OEIS Frontend

A294791 Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly two colors under translational symmetry and swappable colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A294793 Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly four colors under translational symmetry and swappable colors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A294684 Triangle read by rows: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using exactly two colors under translational symmetry, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A294687 Triangle read by rows: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using exactly five colors under translational symmetry, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A294794 Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly five colors under translational symmetry and swappable colors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A295197 Triangle read by rows: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using any number of swappable colors, 1 <= k <= n.

Views