cp's OEIS Frontend

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

%I A091058 #29 Jul 27 2023 12:17:09
%S A091058 1,1,5,139,332034,173636442196,27652322898323351716,
%T A091058 2006943506669869627232430791792,
%U A091058 95763314593596534914617136274432901605313744,4114852471732264714685900791520508800628430894815984377778000
%N A091058 Number of n X n matrices over symbol set {1,...,n} equivalent under any permutation of row, columns or the symbol set.
%H A091058 Alois P. Heinz, <a href="/A091058/b091058.txt">Table of n, a(n) for n = 0..14</a>
%H A091058 C. G. Bower, <a href="/A091057/a091057.html">Explanation of A091057-A091062</a>
%H A091058 <a href="/index/Mat#inequiv">Index to number of inequivalent matrices modulo permutation of rows and columns</a>
%F A091058 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)).
%F A091058 a(n) asymptotic to n^(n^2)/(n!^3) = A002489(n)/(A000142(n)^3).
%t A091058 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}]]];
%t A091058 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]}]];
%t A091058 a[n_] := A242095[n, n];
%t A091058 Table[Print[n, " ", a[n]]; a[n], {n, 0, 12}] (* _Jean-François Alcover_, May 29 2023, after _Alois P. Heinz_ in A242095 *)
%o A091058 (Sage)
%o A091058 Pol.<x> = InfinitePolynomialRing(QQ)
%o A091058 @cached_function
%o A091058 def Z(n):
%o A091058     if n == 0: return Pol.one()
%o A091058     return sum(x[k]*Z(n-k) for k in (1..n))/n
%o A091058 @cached_function
%o A091058 def monprod(M):
%o A091058     p = Pol.one()
%o A091058     V = [m.variables() for m in M]
%o A091058     T = cartesian_product(V)
%o A091058     for t in T:
%o A091058         r = [Pol.varname_key(str(u))[1] for u in t]
%o A091058         j = [Pol(M[u[0]]).degree(u[1]) for u in enumerate(t)]
%o A091058         lcm_r = lcm(r)
%o A091058         p *= x[lcm_r]^(prod(r)/lcm_r*prod(j))
%o A091058     return p
%o A091058 @cached_function
%o A091058 def pol_isotop(n,k):
%o A091058     P = Z(n)
%o A091058     p = Pol.zero()
%o A091058     coeffs = P.coefficients()
%o A091058     mons = P.monomials()
%o A091058     C = cartesian_product(k*[mons])
%o A091058     Csorted = [tuple(sorted(u)) for u in C]
%o A091058     Cset = set(Csorted)
%o A091058     for c in Cset:
%o A091058         p += Csorted.count(c)*prod([coeffs[mons.index(u)] for u in c])*monprod(c)
%o A091058     return p
%o A091058 @cached_function
%o A091058 def rule_sub(r,m):
%o A091058     D = 0
%o A091058     for d in divisors(r):
%o A091058         try: D += d*m.degrees()[-d-1]
%o A091058         except: break
%o A091058     return D
%o A091058 def a(n,k=2):
%o A091058     P = Z(n)
%o A091058     coeffs = P.coefficients()
%o A091058     Q = pol_isotop(n,k)
%o A091058     inds = [Pol.varname_key(str(u))[1] for u in Q.variables()]
%o A091058     p = 0
%o A091058     for mon in enumerate(P.monomials()):
%o A091058         m = Pol(mon[1])
%o A091058         p += coeffs[mon[0]]*Q.subs({x[i]:rule_sub(i,m) for i in inds})
%o A091058     return p
%o A091058 # _Philip Turecek_, Jun 17 2023
%Y A091058 Cf. A091057, A091059, A091060, A091061, A091062.
%Y A091058 Main diagonal of A242095.
%K A091058 nonn
%O A091058 0,3
%A A091058 _Christian G. Bower_, Dec 17 2003
%E A091058 a(9) from _Alois P. Heinz_, Aug 14 2014