A246106 Number A(n,k) of inequivalent n X n matrices with entries from [k], where equivalence means permutations of rows or columns; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 7, 1, 0, 1, 4, 27, 36, 1, 0, 1, 5, 76, 738, 317, 1, 0, 1, 6, 175, 8240, 90492, 5624, 1, 0, 1, 7, 351, 57675, 7880456, 64796982, 251610, 1, 0, 1, 8, 637, 289716, 270656150, 79846389608, 302752867740, 33642660, 1, 0

Offset: 0

Author

Alois P. Heinz, Aug 13 2014

Keywords

• nonn
• tabl

Examples

			Square array A(n,k) begins:
  1, 1,    1,        1,           1,              1, ...
  0, 1,    2,        3,           4,              5, ...
  0, 1,    7,       27,          76,            175, ...
  0, 1,   36,      738,        8240,          57675, ...
  0, 1,  317,    90492,     7880456,      270656150, ...
  0, 1, 5624, 64796982, 79846389608, 20834113243925, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..27, flattened
• Index to number of inequivalent matrices modulo permutation of rows and columns

Crossrefs

Columns k = 0-10 give: A000007, A000012, A002724, A052269, A052271, A052272, A246112, A246113, A246114, A246115, A246116.

Rows n = 0-10 give: A000012, A001477, A039623, A058001, A058002, A058003, A058004, A246108, A246109, A246110, A246111.

Main diagonal gives A246107.

A028657, A242106, A353585 are related tables.

Cf. A242095, A256069.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, [[]],
      `if`(i<1, [], [b(n, i-1)[], seq(map(p->[p[], [i, j]],
       b(n-i*j, i-1))[], j=1..n/i)]))
    end:
A:= proc(n, k) option remember; add(add(k^add(add(i[2]*j[2]*
      igcd(i[1], j[1]), j=t), i=s) /mul(i[1]^i[2]*i[2]!, i=s)
      /mul(i[1]^i[2]*i[2]!, i=t), t=b(n$2)), s=b(n$2))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..10);

PARI

A246106(n,k)=A353585(k,n,n) \\ M. F. Hasler, May 01 2022

Formula

A(n,k) = Sum_{i=0..k} C(k,i) * A256069(n,i).

A(n,k) = Sum_{p,q in P(n)} k^Sum_{i in p, j in q} gcd(i, j) / (N(p)*N(q)) where N(p) = Product_{distinct parts x in p} x^m(x)*m(x)!, m(x) = multiplicity of x in p. - M. F. Hasler, Apr 30 2022 [corrected by Anders Kaseorg, Oct 04 2024]