A246106 -id:A246106 - cp's OEIS frontend

A058001 Number of 3 X 3 matrices with entries mod n, up to row and column permutation.

1, 36, 738, 8240, 57675, 289716, 1144836, 3780288, 10865205, 27969700, 65834406, 143887536, 295467263, 575308020, 1069960200, 1911933696, 3298486761, 5516122788, 8972008810, 14233690800, 22078652211, 33555443636, 50058302988, 73417387200, 106006948125

Offset: 1

Vladeta Jovovic, Nov 04 2000

Number of k X l matrices with entries mod n, up to row and column permutation is Z(S_k X S_l; n,n,...) where Z(S_k X S_l; x_1,x_2,...) is cycle index of Cartesian product of symmetric groups S_k and S_l of degree k and l, respectively.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Marko R. Riedel, Number of equivalence classes of matrices, Math Stackexchange.
Marko R. Riedel, Computing the cycle index for arbitary k x l matrices using Maple
Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-210,252,-210,120,-45,10,-1).

Cf. A058002, A058003, A058004, A002724, A052271, A052272.

Row n=3 of A246106.

CoefficientList[Series[x (12x^7+369x^6+2514x^5+4375x^4+2360x^3+423x^2+26x+1)/(x-1)^10,{x,0,30}],x] (* or *) LinearRecurrence[{10,-45,120,-210,252,-210,120,-45,10,-1},{0,1,36,738,8240,57675,289716,1144836,3780288,10865205},30] (* Harvey P. Dale, Nov 23 2024 *)

a(n) = (1/3!^2)*(n^9 + 6*n^6 + 9*n^5 + 8*n^3 + 12*n^2).

G.f.: x*(12*x^7+369*x^6+2514*x^5+4375*x^4+2360*x^3+423*x^2+26*x+1) / (x-1)^10. - Colin Barker, Jul 09 2013

A058004 Number of 6 X 6 matrices with entries mod n, up to row and column permutation.

Original entry on oeis.org

1, 251610, 302752867740, 9178323524804624, 28125393244553141210, 19909522361922032493690, 5116530046996205504668323, 626072069382507442113224128, 43460016875695276108491159279

Offset: 1

Vladeta Jovovic, Nov 04 2000

Number of k X l matrices with entries mod n, up to row and column permutation is Z(S_k X S_l; n,n,...) where Z(S_k X S_l; x_1,x_2,...) is cycle index of Cartesian product of symmetric groups S_k and S_l of degree k and l, respectively.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A039623, A058001-A058003, A002724, A052271, A052272.

Row n=6 of A246106.

a(n)=(1/6!^2)*(n^36 + 30*n^30 + 225*n^26 + 170*n^24 + 1350*n^22 + 3225*n^20 + 4075*n^18 + 9900*n^16 + 28500*n^14 + 56048*n^12 + 61020*n^10 + 77616*n^8 + 153840*n^6 + 87840*n^4 + 34560*n^2).

A058003 Number of 5 X 5 matrices with entries mod n, up to row and column permutation.

Original entry on oeis.org

1, 5624, 64796982, 79846389608, 20834113243925, 1979525296377132, 93242242505023122, 2625154125717590496, 49871029909245781491, 694584034909225304800, 7525039263469551291908, 66252712846754819753160

Offset: 1

Vladeta Jovovic, Nov 04 2000

Number of k X l matrices with entries mod n, up to row and column permutation is Z(S_k X S_l; n,n,...) where Z(S_k X S_l; x_1,x_2,...) is cycle index of Cartesian product of symmetric groups S_k and S_l of degree k and l, respectively.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A039623, A058001, A058002, A058004, A002724, A052271, A052272.

Row n=5 of A246106.

a(n)=(1/5!^2)*(n^25 + 20*n^20 + 100*n^17 + 70*n^15 + 300*n^14 + 225*n^13 + 400*n^12 + 400*n^11 + 100*n^10 + 1600*n^9 + 2300*n^8 + 1300*n^7 + 1200*n^6 + 1824*n^5 + 480*n^4 + 1680*n^3 + 2400*n^2).

More terms from James Sellers, Nov 08 2000

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

A321609 Array read by antidiagonals: T(n,k) is the number of inequivalent binary n X n matrices with k ones, under row and column permutations.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 3, 1, 1, 0, 0, 1, 3, 1, 1, 0, 0, 1, 6, 3, 1, 1, 0, 0, 0, 7, 6, 3, 1, 1, 0, 0, 0, 7, 16, 6, 3, 1, 1, 0, 0, 0, 6, 21, 16, 6, 3, 1, 1, 0, 0, 0, 3, 39, 34, 16, 6, 3, 1, 1, 0, 0, 0, 1, 44, 69, 34, 16, 6, 3, 1, 1, 0, 0, 0, 1, 55, 130, 90, 34, 16, 6, 3, 1, 1

Offset: 0

Andrew Howroyd, Nov 14 2018

			Array begins:
==========================================================
n\k| 0  1  2  3  4  5  6   7   8    9   10    11    12
---+------------------------------------------------------
0  | 1  0  0  0  0  0  0   0   0    0    0     0     0 ...
1  | 1  1  0  0  0  0  0   0   0    0    0     0     0 ...
2  | 1  1  3  1  1  0  0   0   0    0    0     0     0 ...
3  | 1  1  3  6  7  7  6   3   1    1    0     0     0 ...
4  | 1  1  3  6 16 21 39  44  55   44   39    21    16 ...
5  | 1  1  3  6 16 34 69 130 234  367  527   669   755 ...
6  | 1  1  3  6 16 34 90 182 425  870 1799  3323  5973 ...
7  | 1  1  3  6 16 34 90 211 515 1229 2960  6893 15753 ...
8  | 1  1  3  6 16 34 90 211 558 1371 3601  9209 24110 ...
9  | 1  1  3  6 16 34 90 211 558 1430 3825 10278 28427 ...
...

Rows n=6..8 are A052370, A053304, A053305.
Main diagonal is A049311.
Row sums are A002724.
Cf. A052371 (as triangle), A057150, A246106, A318795.

permcount[v_List] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
c[p_List, q_List, k_] := SeriesCoefficient[Product[Product[(1 + O[x]^(k + 1) + x^LCM[p[[i]], q[[j]]])^GCD[p[[i]], q[[j]]], {j, 1, Length[q]}], {i, 1, Length[p]}], {x, 0, k}];
M[m_, n_, k_] := Module[{s = 0}, Do[Do[s += permcount[p]*permcount[q]*c[p, q, k], {q, IntegerPartitions[n]}], {p, IntegerPartitions[m]}]; s/(m!*n!)]
Table[M[n - k, n - k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Sep 10 2019, after Andrew Howroyd *)

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
c(p, q, k)={polcoef(prod(i=1, #p, prod(j=1, #q, (1 + x^lcm(p[i], q[j]) + O(x*x^k))^gcd(p[i], q[j]))), k)}
M(m, n, k)={my(s=0); forpart(p=m, forpart(q=n, s+=permcount(p) * permcount(q) * c(p, q, k))); s/(m!*n!)}
for(n=0, 10, for(k=0, 12, print1(M(n, n, k), ", ")); print); \\ Andrew Howroyd, Nov 14 2018

T(n,k) = T(k,k) for n > k.

T(n,k) = 0 for k > n^2.

A058002 Number of 4 X 4 matrices with entries mod n, up to row and column permutation.

Original entry on oeis.org

1, 317, 90492, 7880456, 270656150, 4947097821, 58002778967, 490172624992, 3223155968811, 17382581357725, 79840867013666, 321169288917192, 1155731257886192, 3782368364610941, 11406226119319725, 32031530635953536, 84493500676300117, 210856844364222717

Offset: 1

Vladeta Jovovic, Nov 04 2000

Number of k X l matrices with entries mod n, up to row and column permutation is Z(S_k X S_l; n,n,...) where Z(S_k X S_l; x_1,x_2,...) is cycle index of Cartesian product of symmetric groups S_k and S_l of degree k and l, respectively.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A058001, A058003, A058004, A002724, A052271, A052272.

Row n=4 of A246106.

a(n)=(1/4!^2)*(n^16 + 12*n^12 + 36*n^10 + 67*n^8 + 160*n^6 + 204*n^4 + 96*n^2).

G.f.: -x*(x +1)*(x^14 +299*x^13 +84940*x^12 +6299584*x^11 +142482546*x^10 +1214416453*x^9 +4351647617*x^8 +6732281120*x^7 +4351647617*x^6 +1214416453*x^5 +142482546*x^4 +6299584*x^3 +84940*x^2 +299*x +1) / (x -1)^17. - Colin Barker, Jul 09 2013

More terms from Colin Barker, Jul 09 2013

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

A246107 Number of inequivalent n X n matrices with entries from [n], where equivalence means permutations of rows or columns.

Original entry on oeis.org

1, 1, 7, 738, 7880456, 20834113243925, 19909522361922032493690, 10114980502439545115146468340980932, 3861175753082201291221743022346066208381644388448, 1493197587365241166689220567691206411606485768307602552950789523519

Offset: 0

Alois P. Heinz, Aug 13 2014

nonn

Main diagonal of A246106.

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:
a:= n-> A(n$2):
seq(a(n), n=0..12);

a(n) = A246106(2n,n).

A256069 Number T(n,k) of inequivalent n X n matrices with entry set {1,...,k}, where equivalence means permutations of rows or columns; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 5, 0, 1, 34, 633, 0, 1, 315, 89544, 7520386, 0, 1, 5622, 64780113, 79587235420, 20435529209470, 0, 1, 251608, 302752112913, 9177112514843320, 28079504654455279395, 19740907671252532135134

Offset: 0

Alois P. Heinz, Mar 13 2015

			T(2,2) = 5:
  [1 1]  [1 2]  [1 2]  [1 1]  [1 2]
  [1 2]  [2 2]  [1 2]  [2 2]  [2 1].
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,    5;
  0, 1,   34,      633;
  0, 1,  315,    89544,     7520386;
  0, 1, 5622, 64780113, 79587235420, 20435529209470;

Cf. A246106.

Main diagonal gives A256070.

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:
T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..8);

T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A246106(n,k-i).

A256070 Number of inequivalent n X n matrices with entry set {1,...,n}, where equivalence means permutations of rows or columns.

Original entry on oeis.org

1, 1, 5, 633, 7520386, 20435529209470, 19740907671252532135134, 10077866175951324796988844418739012, 3855174405512686506030123555473042980898031518176, 1492231601551989489818761885384738502799149242563553845787532236092

Offset: 0

Alois P. Heinz, Mar 13 2015

nonn

			a(2) = 5:
   [1 1]  [1 2]  [1 2]  [1 1]  [1 2]
   [1 2]  [2 2]  [1 2]  [2 2]  [2 1].

Main diagonal of A256069.

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:
a:= n-> add(A(n, n-i)*(-1)^i*binomial(n, i), i=0..n):
seq(a(n), n=0..10);

a(n) = Sum_{i=0..n} (-1)^i * C(n,i) * A246106(n,n-i).

cp's OEIS Frontend

A058001 Number of 3 X 3 matrices with entries mod n, up to row and column permutation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A058004 Number of 6 X 6 matrices with entries mod n, up to row and column permutation.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A058003 Number of 5 X 5 matrices with entries mod n, up to row and column permutation.

Views

Author

Keywords

Comments

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

A321609 Array read by antidiagonals: T(n,k) is the number of inequivalent binary n X n matrices with k ones, under row and column permutations.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A058002 Number of 4 X 4 matrices with entries mod n, up to row and column permutation.

Views

Author

Keywords

Comments

Links

Crossrefs

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

A246107 Number of inequivalent n X n matrices with entries from [n], where equivalence means permutations of rows or columns.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A256069 Number T(n,k) of inequivalent n X n matrices with entry set {1,...,k}, where equivalence means permutations of rows or columns; triangle T(n,k), n>=0, 0<=k<=n, read by rows.