OFFSET
1,3
COMMENTS
The array is read by falling antidiagonals.
Each row lists the number of inequivalent matrices of size 1 X 1, then 2 X 1, 2 X 2, then 3 X 1, 3 X 2, 3 X 3, etc., with coefficients in Z/nZ (or equivalently, in {1, ..., n}). See Examples for more.
Row 1 counts the zero matrices, there is only one of any size. Row 2 counts binary matrices, this is the lower triangular part of A028657, without the trivial row & column 0. (This table might have been extended with a trivial column 0 = A000012 (counting the 1 matrix of size 0) and row 0 = A000007 counting the number of r X c matrices with no entry, as done in A246106.)
The square matrices (size 1 X 1, 2 X 2, 3 X 3, ...) are counted in columns with triangular numbers, k = T(r) = r(r+1)/2 = (1, 3, 6, 10, 15, ...) = A000217.
LINKS
FORMULA
Let k = c(c-1)/2 + r, 1 <= r <= c, then
T(n, c, r) := T(n, k) = Sum_{p in P(c), q in P(r)} n^S(p, q)/(N(p)*N(q)), where P(r) are the partitions of r, S(p, q) = Sum_{i in p, j in q} gcd(i, j), N(p) = Product_{distinct parts x in p} x^m(x)*m(x)!, m(x) = multiplicity of x in p.
(See, e.g., A080577 for a list of partitions of positive integers.)
In particular:
T(n, 1) = n, T(n, 2) = n(n+1)/2 = A000217(n), T(n, 4) = C(n+2, 3) = A000292(n), T(n, 7) = C(n+3, 4) = A000332(n+3), etc.: T(n, k(k+1)/2 + 1) = C(n+k, k+1),
T(n, k(k+1)/2) = A246106(k, n).
EXAMPLE
The table starts
n \ k=1, 2, 3, 4, 5, 6, ...: T(n,k)
----+--------------------------------------
1 | 1 1 1 1 1 1 ...
2 | 2 3 7 4 13 36 ...
3 | 3 6 27 10 92 738 ...
4 | 4 10 76 20 430 8240 ...
5 | 5 15 175 35 1505 57675 ...
...
Columns 2, 3 and 4, 5, 6 correspond to matrices of size 1 X 2, 2 X 2 and 1 X 3, 2 X 3, 3 X 3, respectively.
Column 4 says that there are (1, 4, 10, 20, 35, ...) inequivalent matrices of size 1 X 3 with entries in Z/nZ (n = 1, 2, 3, 4, ...); these numbers are given by (n+2 choose 3) = binomial(n+2, 3) = n(n+1)(n+2)/6 = A000292(n).
PROG
(PARI) A353585(n, k, r)={if(!r, r=sqrtint(8*k)\/2; k-=r*(r-1)\2); my(m(c, p=1, L=0)=for(i=1, #c, if(i==#c || c[i+1]!=c[i], p *= c[i]^(i-L)*(i-L)!; L=i )); p, S=0); forpart(P=k, my(T=0); forpart(Q=r, T += n^sum(i=1, #P, sum(j=1, #Q, gcd(P[i], Q[j]) ))/m(Q)); S += T/m(P)); S}
CROSSREFS
All of the following related sequences can be expressed in terms of T(n, k, r) := T(n, k(k-1)/2 + r), WLOG r <= k:
A052264(n) = T(2,n,5): size n X 5,
A052269(n) = T(3,n,n): number of inequivalent ternary matrices of size n X n,
A052271(n) = T(4,n,n): number of inequivalent matrices over Z/4Z of size n X n,
A052272(n) = T(5,n,n): number of inequivalent matrices over Z/5Z of size n X n,
KEYWORD
nonn,tabl
AUTHOR
M. F. Hasler, Apr 28 2022
STATUS
approved