A091057 -id:A091057 - 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 *)

A091062 Number of n X n matrices over symbol set {1,2,3,4,5} equivalent under any permutation of row, columns or the symbol set.

Original entry on oeis.org

1, 1, 9, 649, 2283123, 173636442196, 234378355489344704, 5830719097591168695360621, 2779203181367458204944451774688032, 26174539685600184383643311230836752183522328, 4992259182572292655057303928366260085844535079288641049

Offset: 0

Christian G. Bower, Dec 17 2003

nonn

Cf. A091057-A091061.

Column k=5 of A242095.

a(n) = sum_{1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n, 1*u_1+2*u_2+...=5} (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[...] = prod_{i, j>=1} ( (sum_{d|lcm(i, j)} (d*u_d))^(gcd(i, j)*s_i*t_j)).

a(10) from Alois P. Heinz, Aug 14 2014

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

Original entry on oeis.org

1, 1, 5, 18, 173, 2812, 126446, 16821330, 7343033248, 10733521835504, 52867612881649880, 882178115128903807148, 50227997322259477864188380, 9837048598740464300126599181536, 6681839615514161335727724211992609234, 15867777966020615016155969700335142344866474

Offset: 0

Christian G. Bower, Dec 17 2003

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..20
C. G. Bower, Explanation of A091057-A091062
Index to number of inequivalent matrices modulo permutation of rows and columns

Cf. A091057-A091062.
Main diagonal of A242093.
Column k=2 of A242095.

a(n) = sum {1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n, 1*u_1+2*u_2=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[...] = prod {i, j>=1} ( (sum {d|lcm(i, j)} (d*u_d))^(gcd(i, j)*s_i*t_j)).

a(15) from Alois P. Heinz, Aug 14 2014

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

Original entry on oeis.org

1, 1, 5, 139, 332034, 173636442196, 27652322898323351716, 2006943506669869627232430791792, 95763314593596534914617136274432901605313744, 4114852471732264714685900791520508800628430894815984377778000

Offset: 0

Christian G. Bower, Dec 17 2003

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..14
C. G. Bower, Explanation of A091057-A091062
Index to number of inequivalent matrices modulo permutation of rows and columns

Cf. A091057, A091059, A091060, A091061, A091062.

Main diagonal of A242095.

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];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 12}] (* Jean-François Alcover, May 29 2023, after Alois P. Heinz in A242095 *)

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=2):
    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} (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)).

a(n) asymptotic to n^(n^2)/(n!^3) = A002489(n)/(A000142(n)^3).

a(9) from Alois P. Heinz, Aug 14 2014

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

Original entry on oeis.org

1, 1, 9, 408, 332034, 3327329224, 382430372929443, 521184164586987473279, 8728898357751671813141271503, 1850296785573740600565249566845514268, 5085095493754879591102840109774321148107411672, 184819445887199812520846920949561110945504502827686252918

Offset: 0

Christian G. Bower, Dec 17 2003

nonn

Cf. A091057-A091062.

Column k=4 of A242095.

a(n) = sum_{1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n, 1*u_1+2*u_2+...=4} (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[...] = prod_{i, j>=1} ( (sum_{d|lcm(i, j)} (d*u_d))^(gcd(i, j)*s_i*t_j)).

a(11) from Alois P. Heinz, Aug 14 2014

A242106 Number T(n,k) of inequivalent n X n matrices using exactly k different symbols, where equivalence means permutations of rows or columns or the symbol set; triangle T(n,k), n>=0, 0<=k<=n^2, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 4, 3, 1, 0, 1, 17, 121, 269, 241, 100, 24, 3, 1, 0, 1, 172, 15239, 316622, 1951089, 4820228, 5769214, 3768929, 1451594, 347251, 53628, 5645, 451, 37, 3, 1, 0, 1, 2811, 10802952, 3316523460, 170309112972, 2577666563670, 15839885888526

Offset: 0

Alois P. Heinz, Aug 15 2014

Note that the sequence with very similar number A246106 is related but different! - M. F. Hasler, Apr 29 2022

			T(2,2) = 4:
  [1 0]  [1 1]  [1 0]  [1 0]
  [0 0], [0 0], [1 0], [0 1].
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1, 4, 3, 1;
  0, 1, 17, 121, 269, 241, 100, 24, 3, 1;
  0, 1, 172, 15239, 316622, 1951089, 4820228, 5769214, 3768929, ...
  0, 1, 2811, 10802952, 3316523460, 170309112972, 2577666563670, ...
  0, 1, 126445, 50459558944, 382379913244053, 233995925116415261, ...

Alois P. Heinz, Rows n = 0..6, flattened

Row sums give A091057.
Main diagonal gives A360664.
Cf. A242095, 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:
T:= (n, k)-> A(n, k) -A(n, k-1):
seq(seq(T(n, k), k=0..n^2), n=0..4);

Unprotect[Power]; 0^0 = 1; Protect[Power]; b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i<1, {}, Table[Map[Function[{p}, p+j*x^i], b[n-i*j, i-1]], {j, 0, n/i}] // Flatten]]; A[n_, k_] := A[n, k] = Sum[ Sum[ Sum[ Product[ Product[ Sum[d* Coefficient[u, x, d], {d, Divisors[LCM[i, j]]}]^(GCD[i, j]*Coefficient[s, x, i] * Coefficient[t, x, j]), {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}] / Product[ i^Coefficient[u, x, i]*Coefficient[u, x, i]!, {i, 1, Exponent[u, x]}] / Product[ i^Coefficient[t, x, i]*Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}] / Product[ i^Coefficient[s, x, i]*Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}], {u, b[k, k]}], {t, b[n, n]}], {s, b[n, n]}]; T[n_, k_] := A[n, k] - A[n, k-1]; Table[ Table[T[n, k], {k, 0, n^2}], {n, 0, 4}] // Flatten (* Jean-François Alcover, Feb 13 2015, after Alois P. Heinz *)

T(n,k) = A242095(n,k) - A242095(n,k-1) for k>0. T(n,0) = A242095(n,0).

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

Original entry on oeis.org

1, 1, 8, 139, 15412, 10805764, 50459685390, 1601741458883376, 355089431048672347272, 563306081052639719480623715, 6532991278768207315727662508956920, 564259839851988012635404101255119945332425, 368759675849515285894392091271956490586673272192738

Offset: 0

Christian G. Bower, Dec 17 2003

nonn

C. G. Bower, Explanation of A091057-A091062

Cf. A091057-A091062.

Column k=3 of A242095.

a(n) = sum {1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n, 1*u_1+2*u_2+...=3} (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[...] = prod {i, j>=1} ( (sum {d|lcm(i, j)} (d*u_d))^(gcd(i, j)*s_i*t_j)).

a(11)-a(12) from Alois P. Heinz, Aug 14 2014

A154238 Number of orbits of the action g*b = b o (g x g) of the group of permutations g of an n-element set S on the set of closed binary operations b on S.

Original entry on oeis.org

1, 1, 10, 3411, 179228736, 2483590604688125, 14325593551925794051596768, 50976900379139614139041610902600299311, 155682086692129060007763454017522652304844346252853248

Offset: 0

David Pasino, Jan 05 2009, Jan 08 2009, Jan 12 2009

nonn

Here are several different ways of expressing the condition that g*b = b:
b(u, v) = b(gu, gv) for all u, v in S.
The level sets of b are closed under g x g.
The level sets of b are unions of cycles of g x g.
The cycles of g x g are subsets of level sets of b.
b is constant on cycles of g x g.
There is no requirement for g to be an automorphism of b. Given g, the fixed b are determined by simply choosing a value in S for each cycle of g x g. The product b(u, v) is defined to be that constant value for every (u, v) in the cycle.
So the number of degrees of freedom for b is the number of cycles of g x g. How many cycles does g have on S x S? If u is in a c-cycle C and v is in a d-cycle D, then (u, v) is in an lcm(c, d)-cycle and C x D is partitioned into these cycles, so there must be cd/lcm(c, d) of them, which is gcd(c, d).
So letting s_k be the number of k-cycles of g on S for each k from 1 to n, the total number of cycles of g on S x S is the sum on k and j of gcd(k, j) s_k s_j. That's the number of degrees of freedom for b and each degree has valence n, so raise n to that power. Then multiply by the well-known number of permutations of type s, which is n! divided by the factorials of the s_k and by the powers k^s_k. Add this up over all the partitions of n and divide by n!.
Additional comments from Christian G. Bower: This is the number of nonisomorphic n-state relations on a set of n elements. If at the step of raising n to the power, we raised instead some constant m to that power, the formula would give the number of isomorphism classes of m-state relations on an n-element set.

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

Cf. k-state relations: A000595 for k=2, A004105 for k=3, A001374 for k=4, A053516 for k=5.
Cf. A001329, A091057.
Cf. A000595, A004105, A001374, A053516. - Vladeta Jovovic, Jan 06 2009

a(n) = Sum_{1*s_1 + 2*s_2 + ... = n} (fixA[s_1, s_2,..]/(1^s_1*s_1!*2^s_2*s2!* ...)) where fixA[s_1, s_2, ...] = n^(Sum_{i, j>=1} gcd(i, j)*s_i*s_j).

Edited by Christian G. Bower and N. J. A. Sloane, Jan 08 2009

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

A091062 Number of n X n matrices over symbol set {1,2,3,4,5} equivalent under any permutation of row, columns or the symbol set.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A242106 Number T(n,k) of inequivalent n X n matrices using exactly k different symbols, where equivalence means permutations of rows or columns or the symbol set; triangle T(n,k), n>=0, 0<=k<=n^2, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A154238 Number of orbits of the action g*b = b o (g x g) of the group of permutations g of an n-element set S on the set of closed binary operations b on S.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions