A282613 -id:A282613 - cp's OEIS frontend

A283026 Number of inequivalent 4 X 4 matrices with entries in {1,2,3,..,n} up to row permutations.

0, 1, 3876, 1929501, 183181376, 6419043125, 118091211876, 1388168405001, 11745311589376, 77279801651001, 416916712502500, 1915356782994501, 7705740009485376, 27731516944463501, 90762229896563876, 273716119247180625, 768684707117285376, 2027695320242670001

Offset: 0

David Nacin, Feb 27 2017

Cycle index of symmetry group S4 acting on the 16 entries is (6*s(2)^4s(1)^8 + 8*s(3)^4s(1)^4 + 3*s(2)^8 + 6*s(4)^4 + s(1)^{16})/24.

			For n=2 we get a(2)=3876 inequivalent 4x4 binary matrices up to row permutations.

Cf. A282613, A282614, A283027, A283028, A283029, A283031, A283032, A283033. A283030 (5x5 version). A282612 (3x3 version). A037270 (2x2 version).

Table[n^4*(n^4 + 1)*(n^4 + 2)*(n^4 + 3)/24,{n,0,30}]

a(n) = n^4*(n^4 + 1)*(n^4 + 2)*(n^4 + 3)/24; \\ Indranil Ghosh, Feb 27 2017

def A283026(n) : return n**4*(n**4 + 1)*(n**4 + 2)*(n**4 + 3)/24 # Indranil Ghosh, Feb 27 2017

a(n) = n^4*(n^4 + 1)*(n^4 + 2)*(n^4 + 3)/24.
From Chai Wah Wu, Dec 07 2018: (Start)
a(n) = 17*a(n-1) - 136*a(n-2) + 680*a(n-3) - 2380*a(n-4) + 6188*a(n-5) - 12376*a(n-6) + 19448*a(n-7) - 24310*a(n-8) + 24310*a(n-9) - 19448*a(n-10) + 12376*a(n-11) - 6188*a(n-12) + 2380*a(n-13) - 680*a(n-14) + 136*a(n-15) - 17*a(n-16) + a(n-17) for n > 16.
G.f.: -x*(x + 1)*(x^14 + 3858*x^13 + 1859887*x^12 + 149046428*x^11 + 3415692141*x^10 + 29161611758*x^9 + 104450960739*x^8 + 161533106376*x^7 + 104450960739*x^6 + 29161611758*x^5 + 3415692141*x^4 + 149046428*x^3 + 1859887*x^2 + 3858*x + 1)/(x - 1)^17. (End)

A285522 Array read by antidiagonals: T(m,n) = number of circulant digraphs up to Cayley isomorphism on n vertices with edges colored according to step value using a maximum of m-1 colors.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 6, 6, 4, 1, 1, 6, 18, 10, 5, 1, 1, 20, 24, 40, 15, 6, 1, 1, 14, 135, 70, 75, 21, 7, 1, 1, 48, 130, 544, 165, 126, 28, 8, 1, 1, 52, 648, 700, 1625, 336, 196, 36, 9, 1, 1, 140, 1137, 4480, 2635, 3996, 616, 288, 45, 10, 1

Offset: 1

Andrew Howroyd, Apr 20 2017

For the base case of m=2 the sequence counts circulant digraphs 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 Liskovets reference for a proof.)
Alternatively, the number of mappings with domain {1..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 {1..n-1}. This sequence differs from A132191 only in that sequence also includes 0 in the domain which introduces an extra factor of m into the results since zero multiplied by anything is zero.
All column sequences are polynomials of order n-1 and these are the cycle index polynomials.
This sequence is also related to A075195(n, m) which counts necklaces and A285548(m, n) which is the sequence described in the Titsworth reference. In particular, A075195 is the analogous array with equivalence determined through the additive group instead of by multiplication whereas A285548 allows for both addition and multiplication.

			Table starts:
\n  1 2  3   4    5    6    7     8      9      10
m\ ---------------------------------------------------
1 | 1 1  1   1    1    1    1     1      1       1 ...
2 | 1 2  3   6    6   20   14    48     52     140 ...
3 | 1 3  6  18   24  135  130   648   1137    4995 ...
4 | 1 4 10  40   70  544  700  4480  11056   65824 ...
5 | 1 5 15  75  165 1625 2635 20625  65425  489125 ...
6 | 1 6 21 126  336 3996 7826 72576 280596 2521476 ...
...
Case n=10:
Only 1, 3, 7, 9 are prime to 10.
Multiplication modulo 10 is described by the following multiplication table.
  1, 2, 3, 4, 5, 6, 7, 8, 9  => (1)(2)(3)(4)(5)(6)(7)(8)(9) => m^9
  3, 6, 9, 2, 5, 8, 1, 4, 7  => (1397)(2684)(5)             => m^3
  7, 4, 1, 8, 5, 2, 9, 6, 3  => (1793)(2486)(5)             => m^3
  9, 8, 7, 6, 5, 4, 3, 2, 1  => (19)(28)(37)(46)(5)         => m^5
Each row of the multiplication table can be viewed as a permutation and together these form a commutative group on 4 elements. In this case the group is isomorphic to the cyclic group C_4. Each permutation can be represented in cycle notation. (shown above to the right of the corresponding multiplication table row). In order to count the equivalence classes using Polya's enumeration theorem only the number of cycles in each permutation is needed.
This gives the cycle index polynomial (1/4)*(m^9 + m^5 + 2*m^3). Putting m = 1..4 gives 1, 140, 4995, 65824.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders.
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.
Eric Weisstein's World of Mathematics, Circulant Graph.
Wikipedia, Polya enumeration theorem.

Row 2 is A056391.
Columns include A002411, A006528, A168178, A006565, A282613, A054624.
Cf. A132191, A075195, A285548, A002729.

A132191[m_, n_] := (1/EulerPhi[n])*Sum[If[GCD[k, n] == 1, m^DivisorSum[n, EulerPhi[#] / MultiplicativeOrder[k, #] &], 0], {k, 1, n}];
T[m_, n_] := A132191[m, n]/m;
Table[T[m - n + 1, n], {m, 1, 11}, {n, m, 1, -1}] // Flatten (* Jean-François Alcover, Jun 06 2017 *)

a(n,x)=sum(k=1, n, if(gcd(k, n)==1, x^(sumdiv(n, d, eulerphi(d)/znorder(Mod(k, d)))-1), 0))/eulerphi(n);
for(m=1, 6, for(n=1, 10, print1( a(n,m), ", ") ); print(); );

T(m, n) = A132191(m, n) / m.

cp's OEIS Frontend

A283026 Number of inequivalent 4 X 4 matrices with entries in {1,2,3,..,n} up to row permutations.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula