A002724
Number of inequivalent n X n binary matrices, where equivalence means permutations of rows or columns.
Original entry on oeis.org
1, 2, 7, 36, 317, 5624, 251610, 33642660, 14685630688, 21467043671008, 105735224248507784, 1764356230257807614296, 100455994644460412263071692, 19674097197480928600253198363072, 13363679231028322645152300040033513414, 31735555932041230032311939400670284689732948
Offset: 0
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..26 from Alois P. Heinz)
- Manuel Kauers and Jakob Moosbauer, Good pivots for small sparse matrices, arXiv:2006.01623 [cs.SC], 2020.
- A. Kerber, Experimentelle Mathematik, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 19 (1988), 77-83. [Annotated scanned copy]
- Mathematics Stack Exchange, How many n-by-m binary matrices are there up to row and column permutations
- B. Misek, On the number of classes of strongly equivalent incidence matrices, (Czech with English summary) Casopis Pest. Mat. 89 1964 211-218.
- Marko Riedel, Maple code with two different algorithms
- M. Zivkovic, Classification of small (0,1) matrices, arXiv:math/0511636 [math.CO], 2005.
- Index entries for sequences related to binary matrices
- Index to number of inequivalent matrices modulo permutation of rows and columns
Cf.
A002623,
A002727,
A006148,
A002728,
A002725,
A052269,
A052271,
A052272,
A091059,
A363845,
A363846,
A000595.
-
# See Marko Riedel link.
-
b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Union[Flatten[Table[ Function[{p}, p + j*x^i] /@ b[n - i*j, i - 1], {j, 0, n/i}]]]]];
g[n_, k_] := g[n, k] = Sum[Sum[2^Sum[Sum[GCD[i, j]*Coefficient[s, x, i]* Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}]/ Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n + k, n + k]}], {s, b[n, n]}];
A[n_, k_] := g[Min[n, k], Abs[n - k]];
Table[A[n, n], {n, 0, 15}] (* Jean-François Alcover, Aug 10 2018, after Alois P. Heinz *)
-
a(n) = A(n,n) \\ A defined in A028657. - Andrew Howroyd, Mar 01 2023
a(15) from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 24 2008
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.
Original entry on oeis.org
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
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.
-
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 *)
A242093
Number A(n,k) of inequivalent n X k binary matrices, where equivalence means permutations of rows or columns or the symbol set; square array A(n,k), n>=0, k>=0, read by antidiagonals.
Original entry on oeis.org
1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 5, 2, 1, 1, 3, 8, 8, 3, 1, 1, 3, 14, 18, 14, 3, 1, 1, 4, 20, 47, 47, 20, 4, 1, 1, 4, 30, 95, 173, 95, 30, 4, 1, 1, 5, 40, 200, 545, 545, 200, 40, 5, 1, 1, 5, 55, 367, 1682, 2812, 1682, 367, 55, 5, 1, 1, 6, 70, 674, 4745, 14386, 14386, 4745, 674, 70, 6, 1
Offset: 0
A(1,4) = 3: [0 0 0 0], [1 0 0 0], [1 1 0 0].
A(1,5) = 3: [0 0 0 0 0], [1 0 0 0 0], [1 1 0 0 0].
A(2,2) = 5:
[0 0] [1 0] [1 1] [1 0] [1 0]
[0 0], [0 0], [0 0], [1 0], [0 1].
A(3,2) = 8:
[0 0] [1 0] [1 1] [1 0] [1 0] [1 0] [1 0] [1 1]
[0 0], [0 0], [0 0], [1 0], [0 1], [1 0], [0 1], [1 0].
[0 0] [0 0] [0 0] [0 0] [0 0] [1 0] [1 0] [0 0]
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 2, 2, 3, 3, 4, 4, ...
1, 2, 5, 8, 14, 20, 30, 40, ...
1, 2, 8, 18, 47, 95, 200, 367, ...
1, 3, 14, 47, 173, 545, 1682, 4745, ...
1, 3, 20, 95, 545, 2812, 14386, 68379, ...
1, 4, 30, 200, 1682, 14386, 126446, 1072086, ...
1, 4, 40, 367, 4745, 68379, 1072086, 16821330, ...
Columns (or rows) k=0-10 give:
A000012,
A008619,
A006918(n+1),
A246148,
A246149,
A246150,
A246151,
A246152,
A246153,
A246154,
A246155.
-
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:
g:= 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(2$2)), t=b(n$2)), s=b(k$2))
end:
A:= (n, k)-> g(sort([n, k])[]):
seq(seq(A(n, d-n), n=0..d), d=0..12);
-
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}]]]];
g[n_, k_] := g[n, k] = Sum[Sum[Sum[Product[Product[With[{gc = GCD[i, j]* Coefficient[s, x, i]*Coefficient[t, x, j]}, If[gc == 0, 1, Sum[d* Coefficient[u, x, d], {d, Divisors[LCM[i, j]]}]^gc]], {j, 1, 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[2, 2]}], {t, b[n, n]}], {s, b[k, k]}];
A[n_, k_] := g @@ Sort[{n, k}];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Apr 25 2016, adapted from Maple, updated Jan 01 2021 *)
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
-
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
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
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).
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:
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),
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}
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
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].
-
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 *)
Showing 1-6 of 6 results.
Comments