[seqfan] Re: Inequivalent matrices

[M. F. Hasler]

On Thu, Apr 28, 2022 at 8:46 PM Neil Sloane <> wrote:

> > Maybe we should leave a map to future generations
> That is exactly what the Index to the OEIS is for.
> Please make some entries there!
>

OK, I'll do that. I also propose oeis.org/draft/A353585
which contains all of the "number of inequivalent r X c matrices over Z/nZ"
(equivalence modulo permutation of rows & col's) in one table:
row n is for Z/nZ (i.e., entries in {0..n-1} or {1..n} if one prefers)
and in each row, all possible sizes are listed as 1 <= r <= c = 1,2,3,....
I.e., 1X1, 1X2, 2X2; 1X3, 2X3, 3X3; etc.
My goal was in fact to contribute one function that can be used for any (n,
r, c).
The function I found is very nice and simple
(much simpler than the huge formulas given by Christian Bower for some
special cases,
as mentioned by Brendan McKay, and also GFs contributed among others by
Vladeta Jovovic),
so nice that I want to share it here:
It is a double sum over all partitions p of r and q of c:

N(n, r, c) = Sum_{p in P(r), q in P(c)} n^Sum{i in p, j in q} gcd(i,j) /
(M(p) M(q))

with  M(p) = Sum_{distinct parts x in p} x^m(x) * m(x)!
where m(x) is the multiplicity of x in the partition p.

This function allows to compute very efficiently all of the following:

A028657(n,k) = A353585(2,n,k): inequivalent m X n binary matrices,
A002723(n) = T(2,n,2): size n X 2, A002724(n) = T(2,n,n): size n X n,
A002727(n) = T(2,n,3): size n X 3, A002725(n) = T(2,n,n+1): size n X (n+1),
A006148(n) = T(2,n,4): size n X 4, A002728(n) = T(2,n,n+2): size n X (n+2)
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,
A246106(n,k) = A353585(k,n,n): number of inequivalent n X n matrices over
Z/kZ, and its diagonal A091058 and columns 1, 2, ..., 10: A000012, A091059,
A091060, A091061, A091062, A246122, A246123, A246124, A246125, A246126.

The  last one(s) are from Alois Heinz who also contributed:

A256069 = number of inequivalent n X n matrices with *exactly* k different
entries,
which is the inverse binomial transform of A246106 (above!),

and (note the almost identical A-number as A246106 above!) :
A242106 = inequivalent n X n matrices using exactly k different symbols,
where equivalence is modulo permutations of rows, cols *and the symbol set*

which in turn can be computed as first differences of
A242095 =  inequivalent n X n matrices with entries from [k],
where equivalence means permutations of rows or columns *or the symbol set*.

- Maximilian

On Wed, Apr 27, 2022 at 11:48 PM M. F. Hasler wrote:
> > On Wed, Apr 27, 2022 at 10:42 PM Brendan McKay wrote:
> >> All of these except Z/Z6 have formulas provided by Christian Bower.
> >> A246106   is a 2-D version.  [MH: i.e., column k  for entries in Z/kZ ]
> >
> > Great!  Thank you very much!
> > Some further refs : (...)
>