A091058 -id:A091058 - cp's OEIS frontend

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

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 5, 1, 0, 1, 1, 8, 18, 1, 0, 1, 1, 9, 139, 173, 1, 0, 1, 1, 9, 408, 15412, 2812, 1, 0, 1, 1, 9, 649, 332034, 10805764, 126446, 1, 0, 1, 1, 9, 749, 2283123, 3327329224, 50459685390, 16821330, 1, 0

Offset: 0

Alois P. Heinz, Aug 14 2014

A(n,k) = A(n,k+1) for k >= n^2.

			A(2,2) = 5:
  [1 1]  [2 1]  [2 2]  [2 1]  [2 1]
  [1 1], [1 1], [1 1], [2 1], [1 2].
Square array A(n,k) begins:
  1, 1,    1,        1,          1,            1, ...
  0, 1,    1,        1,          1,            1, ...
  0, 1,    5,        8,          9,            9, ...
  0, 1,   18,      139,        408,          649, ...
  0, 1,  173,    15412,     332034,      2283123, ...
  0, 1, 2812, 10805764, 3327329224, 173636442196, ...

Columns k=0-10 give: A000007, A000012, A091059, A091060, A091061, A091062, A246122, A246123, A246124, A246125, A246126.
Main diagonal gives A091058.
A(n,n^2) gives A091057.
Cf. A242093, A242106, A246106.

with(numtheory):
b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},
      {seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))
    end:
A:= proc(n, k) option remember; add(add(add(mul(mul(add(d*
      coeff(u, x, d), d=divisors(ilcm(i, j)))^(igcd(i, j)*
      coeff(s, x, i)*coeff(t, x, j)), j=1..degree(t)),
      i=1..degree(s))/mul(i^coeff(u, x, i)*coeff(u, x, i)!,
      i=1..degree(u))/mul(i^coeff(t, x, i)*coeff(t, x, i)!,
      i=1..degree(t))/mul(i^coeff(s, x, i)*coeff(s, x, i)!,
      i=1..degree(s)), u=b(k$2)), t=b(n$2)), s=b(n$2))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[n_, i_] := b[n, i] = If[n==0, {0}, If[i<1, {}, Flatten@Table[Map[ Function[p, p + j*x^i], b[n - i*j, i - 1]], {j, 0, n/i}]]];
A[n_, k_] := A[n, k] = Sum[Sum[Sum[Product[Product[With[{g = GCD[i, j]* Coefficient[s, x, i]*Coefficient[t, x, j]}, If[g == 0, 1, Sum[d* Coefficient[u, x, d], {d, Divisors[LCM[i, j]]}]^g]], {j, Exponent[t, x]} ],
{i, Exponent[s, x]}]/Product[i^Coefficient[u, x, i]*Coefficient[u, x, i]!,
{i, Exponent[u, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!,
{i, Exponent[t, x]}]/Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!,
{i, Exponent[s, x]}], {u, b[k, k]}], {t, b[n, n]}], {s, b[n, n]}];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Feb 21 2016, after Alois P. Heinz, updated Jan 01 2021 *)

A091057 Number of n X n matrices over symbol set {1,...,n^2} equivalent under any permutation of row, columns or the symbol set.

Original entry on oeis.org

1, 1, 9, 777, 18500104, 322286625959257, 7368376339801908226685191, 422262377369187686156418513093399998333, 105882936532098986759153041871810253870024776751177723954

Offset: 0

Christian G. Bower, Dec 17 2003

nonn

C. G. Bower, Explanation of A091057-A091062

Cf. A091058-A091062, A242095.

Row sums of A242106.

b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Flatten @ Table[Map[Function[p, p + j*x^i], b[n - i*j, i - 1]], {j, 0, n/i}]]];
A242095[n_, k_] := A242095[n, k] = With[{co = Coefficient, ex = Exponent}, Sum[Sum[Sum[Product[Product[With[{g = GCD[i, j]*co[s, x, i]*co[t, x, j]}, If[g == 0, 1, Sum[d*co[u, x, d], {d, Divisors[LCM[i, j]]}]^g]], {j, ex[t, x]}], {i, ex[s, x]}]/Product[i^co[u, x, i]*co[u, x, i]!, {i, ex[u, x]}]/Product[i^co[t, x, i]*co[t, x, i]!, {i, ex[t, x]}]/Product[i^co[s, x, i]*co[s, x, i]!, {i, ex[s, x]}], {u, b[k, k]}], {t, b[n, n]}], {s, b[n, n]}]];
a[n_] := A242095[n, n^2];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 6}] (* Jean-François Alcover, May 29 2023, after Alois P. Heinz in A242095 *)

a(n) = Sum_{1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n, 1*u_1+2*u_2+...=n^2} (fixA[s_1, s_2, ...; t_1, t_2, ...; u_1, u_2, ...]/ (1^s_1*s_1!*2^s_2*s_2!*...*1^t_1*t_1!*2^t_2*t_2!*...*1^u_1*u_1!*2^u_2*u_2!*...)) where fixA[...] = Product_{i,j>=1} ((Sum_{d|lcm(i, j)} (d*u_d))^(gcd(i, j)*s_i*t_j)). - corrected by Max Alekseyev, Jun 03 2023

a(7), a(8) from Max Alekseyev, Feb 09 2010

A353585 Square array T(n,k): row n lists the number of inequivalent matrices over Z/nZ, modulo permutations of rows and columns, of size r X c, 1 <= r <= c, c >= 1.

Original entry on oeis.org

1, 1, 2, 1, 3, 3, 1, 7, 6, 4, 1, 4, 27, 10, 5, 1, 13, 10, 76, 15, 6, 1, 36, 92, 20, 175, 21, 7, 1, 5, 738, 430, 35, 351, 28, 8, 1, 22, 15, 8240, 1505, 56, 637, 36, 9, 1, 87, 267, 35, 57675, 4291, 84, 1072, 45, 10, 1, 317, 5053, 1996, 70, 289716, 10528, 120, 1701, 55, 11

Offset: 1

M. F. Hasler, Apr 28 2022

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.

			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).

OEIS Index to number of inequivalent matrices modulo permutation of row and columns.

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:
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.

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}

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).

A360660 Number of inequivalent n X n {0,1} matrices modulo permutation of the rows, with exactly n 1's.

Original entry on oeis.org

1, 1, 4, 20, 133, 1027, 9259, 94033, 1062814, 13176444, 177427145, 2573224238, 39924120823, 658921572675, 11513293227271, 212109149134617, 4105637511110979, 83238756058333277, 1762856698153603049, 38905470655863251479, 892840913430059075405

Offset: 0

Alois P. Heinz, Feb 15 2023

nonn

Also the number of multisets of n words of length n over binary alphabet where the first letter occurs n times. E.g., a(2) = 4: {aa,bb}, {ab,ab}, {ab,ba}, {ba,ba}.

			a(3) = 20: [111/000/000], [110/100/000], [110/010/000], [110/001/000], [101/100/000], [101/010/000], [101/001/000], [100/100/100], [100/100/010], [100/100/001], [100/011/000], [100/010/010], [100/010/001], [100/001/001], [011/010/000], [011/001/000], [010/010/010], [010/010/001], [010/001/001], [001/001/001].

Alois P. Heinz, Table of n, a(n) for n = 0..200

Main diagonal of A220886.

Cf. A091058, A091059, A154323, A246107, A256070, A360664, A383073.

g:= proc(n, i, j) option remember; expand(`if`(j=0, 1, `if`(i<0, 0, add(
      g(n, i-1, j-k)*x^(i*k)*binomial(binomial(n, i)+k-1, k), k=0..j))))
    end:
a:= n-> coeff(g(n$3), x, n):
seq(a(n), n=0..20);

g[n_, i_, j_] := g[n, i, j] = Expand[If[j == 0, 1, If[i < 0, 0, Sum[g[n, i - 1, j - k]*x^(i*k)*Binomial[Binomial[n, i] + k - 1, k], {k, 0, j}]]]];
a[n_] := SeriesCoefficient[g[n, n, n], {x, 0, n}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 28 2023, after Alois P. Heinz *)
Table[SeriesCoefficient[Product[1/(1 - x^k)^Binomial[n, k], {k, 1, n}], {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Apr 15 2025 *)

a(n) = A220886(n,n).

a(n) = [x^n] Product_{k=1..n} 1/(1 - x^k)^binomial(n,k). - Vaclav Kotesovec, Apr 15 2025

A091511 Number of n X n X n 3-D matrices over symbol set {1,...,n} equivalent under any permutation of rows, columns, stacks or the symbol set.

Original entry on oeis.org

1, 1, 30, 5887172299, 1025638889935309161425800069552344, 11337715575060644543768059040620852798601554512475786008052416860406653219312996

Offset: 0

Christian G. Bower, Jan 16 2004

nonn

Philip Turecek, Table of n, a(n) for n = 0..8

Cf. A091058, A091510.

Pol. = InfinitePolynomialRing(QQ)
@cached_function
def Z(n):
    if n == 0: return Pol.one()
    return sum(x[k]*Z(n-k) for k in (1..n))/n
@cached_function
def monprod(M):
    p = Pol.one()
    V = [m.variables() for m in M]
    T = cartesian_product(V)
    for t in T:
        r = [Pol.varname_key(str(u))[1] for u in t]
        j = [Pol(M[u[0]]).degree(u[1]) for u in enumerate(t)]
        lcm_r = lcm(r)
        p *= x[lcm_r]^(prod(r)/lcm_r*prod(j))
    return p
@cached_function
def pol_isotop(n,k):
    P = Z(n)
    p = Pol.zero()
    coeffs = P.coefficients()
    mons = P.monomials()
    C = cartesian_product(k*[mons])
    Csorted = [tuple(sorted(u)) for u in C]
    Cset = set(Csorted)
    for c in Cset:
        p += Csorted.count(c)*prod([coeffs[mons.index(u)] for u in c])*monprod(c)
    return p
@cached_function
def rule_sub(r,m):
    D = 0
    for d in divisors(r):
        try: D += d*m.degrees()[-d-1]
        except: break
    return D
def a(n,k=3):
    P = Z(n)
    coeffs = P.coefficients()
    Q = pol_isotop(n,k)
    inds = [Pol.varname_key(str(u))[1] for u in Q.variables()]
    p = 0
    for mon in enumerate(P.monomials()):
        m = Pol(mon[1])
        p += coeffs[mon[0]]*Q.subs({x[i]:rule_sub(i,m) for i in inds})
    return p
# Philip Turecek, Jun 17 2023

a(n) = Sum_{1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n, 1*u_1+2*u_2+...=n, 1*v_1+2*v_2+...=n} (fixA[s_1, s_2, ...;t_1, t_2, ...;u_1, u_2, ...;v_1, v_2, ...]/ (1^s_1*s_1!*2^s_2*s_2!*... *1^t_1*t_1!*2^t_2*t_2!*... *1^u_1*u_1!*2^u_2*u_2!*... *1^v_1*v_1!*2^v_2*v_2!*...)) where fixA[...] = Product_{i, j, k>=1} ( (Sum_{d|lcm(i, j, k)} (d*v_d))^(s_i*t_j*u_k *lcm(i, j, k)/(i*j*k))).

a(n) asymptotic to n^(n^3)/(n!^4).

a(2) corrected by Philip Turecek, Jun 13 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A091057 Number of n X n matrices over symbol set {1,...,n^2} equivalent under any permutation of row, columns or the symbol set.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A353585 Square array T(n,k): row n lists the number of inequivalent matrices over Z/nZ, modulo permutations of rows and columns, of size r X c, 1 <= r <= c, c >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A360660 Number of inequivalent n X n {0,1} matrices modulo permutation of the rows, with exactly n 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A091511 Number of n X n X n 3-D matrices over symbol set {1,...,n} equivalent under any permutation of rows, columns, stacks or the symbol set.

Views

Author

Keywords

Links

Crossrefs

Programs

Sage

Formula

Extensions