A053304 -id:A053304 - cp's OEIS frontend

A049311 Number of (0,1) matrices with n ones and no zero rows or columns, up to row and column permutations.

1, 3, 6, 16, 34, 90, 211, 558, 1430, 3908, 10725, 30825, 90156, 273234, 848355, 2714399, 8909057, 30042866, 103859678, 368075596, 1335537312, 4958599228, 18820993913, 72980867400, 288885080660, 1166541823566, 4802259167367, 20141650236664

Offset: 1

Peter J. Cameron

Also the number of bipartite graphs with n edges, no isolated vertices and a distinguished bipartite block, up to isomorphism.
The EULERi transform (A056156) is also interesting.
a(n) is also the number of non-isomorphic set multipartitions (multisets of sets) of weight n. - Gus Wiseman, Mar 17 2017

			E.g. a(2) = 3: two ones in same row, two ones in same column, or neither.
a(3) = 6 is coefficient of x^3 in (1/36)*((1 + x)^9 + 6*(1 + x)^3*(1 + x^2)^3 + 8*(1 + x^3)^3 + 9*(1 + x)*(1 + x^2)^4 + 12*(1 + x^3)*(1 + x^6))=1 + x + 3*x^2 + 6*x^3 + 7*x^4 + 7*x^5 + 6*x^6 + 3*x^7 + x^8 + x^9.
There are a(3) = 6 binary matrices with 3 ones, with no zero rows or columns, up to row and column permutation:
  [1 0 0] [1 1 0] [1 0] [1 1] [1 1 1] [1]
  [0 1 0] [0 0 1] [1 0] [1 0] ....... [1].
  [0 0 1] ....... [0 1] ............. [1]
Non-isomorphic representatives of the a(3)=6 set multipartitions are: ((123)), ((1)(23)), ((2)(12)), ((1)(1)(1)), ((1)(2)(2)), ((1)(2)(3)). - _Gus Wiseman_, Mar 17 2017

Aliaksandr Siarhei, Table of n, a(n) for n = 1..102
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Peter J. Cameron, D. A. Gewurz and F. Merola, Product action, Discrete Math., 308 (2008), 386-394.
Peter J. Cameron, Problems on Permutation Groups, see Problem 3
Index entries for sequences related to binary matrices.

Main diagonal of A321609.
Cf. A049312, A048194, A028657, A055192, A055599, A052371, A052370, A053304, A053305, A007716, A002724.
Cf. A057149, A057150, A057151, A057152.
Cf. A034691, A056156, A089259, A116540, A283877.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
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}
K(q, t, k)={WeighT(Vec(sum(j=1, #q, gcd(t, q[j])*x^lcm(t, q[j])) + O(x*x^k), -k))}
a(n)={my(s=0); forpart(q=n, s+=permcount(q)*polcoef(exp(x*Ser(sum(t=1, n, K(q, t, n)/t))), n)); s/n!} \\ Andrew Howroyd, Jan 16 2023

Calculate number of connected bipartite graphs + number of connected bipartite graphs with no duality automorphism, then apply EULER transform.

a(n) is the coefficient of x^n in the cycle index Z(S_n X S_n; 1+x, 1+x^2, ...), where S_n X S_n is Cartesian product of symmetric groups S_n of degree n.

More terms and formula from Vladeta Jovovic, Jul 29 2000
a(19)-a(28) from Max Alekseyev, Jul 22 2009
a(29)-a(102) from Aliaksandr Siarhei, Dec 13 2013
Name edited by Gus Wiseman, Dec 18 2018

A052371 Triangle T(n,k) of n X n binary matrices with k=0...n^2 ones up to row and column permutations.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 6, 7, 7, 6, 3, 1, 1, 1, 1, 3, 6, 16, 21, 39, 44, 55, 44, 39, 21, 16, 6, 3, 1, 1, 1, 1, 3, 6, 16, 34, 69, 130, 234, 367, 527, 669, 755, 755, 669, 527, 367, 234, 130, 69, 34, 16, 6, 3, 1, 1

Offset: 0

Vladeta Jovovic, Mar 08 2000

			Triangle begins:
  1;
  1, 1;
  1, 1, 3, 1, 1;
  1, 1, 3, 6, 7, 7, 6, 3, 1, 1;
  1, 1, 3, 6, 16, 21, 39, 44, 55, 44, 39, 21, 16, 6, 3, 1, 1;
  ...
(the last block giving the numbers of 4 X 4 binary matrices with k=0..16 ones up to row and column permutations).

Andrew Howroyd, Table of n, a(n) for n = 0..2890 (rows n=0..20)

Rows 6..8 are A052370, A053304, A053305.
Row sums are A002724.
Cf. A049311.

permcount[v_] := Module[{m = 1, s = 0, t, i, k = 0}, 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_, q_] := Product[(1 + x^LCM[p[[i]], q[[j]]])^GCD[p[[i]], q[[j]]], {i, 1, Length[p]}, {j, 1, Length[q]}];
row[n_] := Module[{s = 0}, Do[Do[s += permcount[p]*permcount[q]*c[p, q], {q, IntegerPartitions[n]}], {p, IntegerPartitions[n]}]; CoefficientList[ s/(n!^2), x]]
row /@ Range[0, 5] // Flatten (* Jean-François Alcover, Sep 22 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)={prod(i=1, #p, prod(j=1, #q, (1 + x^lcm(p[i], q[j]))^gcd(p[i], q[j])))}
row(n)={my(s=0); forpart(p=n, forpart(q=n, s+=permcount(p) * permcount(q) * c(p, q))); Vec(s/(n!^2))}
for(n=1, 5, print(row(n))) \\ Andrew Howroyd, Nov 14 2018

a(0)=1 prepended by Andrew Howroyd, Nov 14 2018

A121231 Number of n X n binary matrices M (that is, real matrices with entries 0 and 1) such that M^2 is also a binary matrix.

Original entry on oeis.org

1, 2, 11, 172, 6327, 474286, 67147431, 17080038508

Offset: 0

Dan Dima, Aug 21 2006

Comments from Brendan McKay, Aug 21 2006: Equivalently, directed graphs (simple but loops allowed) without a few small forbidden subgraphs (those allowing 2 distinct paths of length 2 from vertex x to vertex y for some x,y; I think there are 6 possibilities). One can also consider isomorphism classes of those digraphs.
Comment from  Rob Pratt, Aug 03 2008: A121294 provides a lower bound on the maximum number of 1's in such a matrix M. There are cases where a higher number is reached; the following 5 X 5 matrix has 11 ones and its square is binary:
0 0 1 0 0
0 0 0 0 1
1 1 0 0 1
1 1 0 1 0
1 1 0 1 0.
The optimal values seem to match A070214, verified for n <= 7.
Term (5,1) of the n-th power of the 5 X 5 matrix shown is A001045(n), the Jacobsthal sequence. - Gary W. Adamson, Oct 03 2008
a(n) >= A226321(n).

Eric Weisstein's World of Mathematics, Background information about adjacency matrices
E. W. Weisstein, (0,1)-Matrix, MathWorld. [P. Petsie, Aug 03 2008]
Wikipedia, Background information about adjacency matrices
Index entries for matrices, binary, which are squares

Cf. A226321, A225371, A055084, A052264, A051589, A069452, A053304, A001045, A121294, A070214.

Edited by R. J. Mathar, Oct 01 2008
a(7) from R. H. Hardin, Jun 19 2012. This makes it clear that the old A122527 was really a badly-described version of this sequence, and that a(7) was earlier found by Balakrishnan (bvarada2(AT)jhu.edu), Sep 17 2006. - N. J. A. Sloane, Jun 19 2012
Entry revised by N. J. A. Sloane, Jun 19 2012

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.

A052370 Number of 6 X 6 binary matrices with n=0...36 ones up to row and column permutations.

Original entry on oeis.org

1, 1, 3, 6, 16, 34, 90, 182, 425, 870, 1799, 3323, 5973, 9595, 14570, 19865, 25191, 28706, 30310, 28706, 25191, 19865, 14570, 9595, 5973, 3323, 1799, 870, 425, 182, 90, 34, 16, 6, 3, 1, 1

Offset: 0

Vladeta Jovovic, Mar 08 2000

Sum_{k=0..36}a(n)=A002724(6)

Cf. A049311, A053304, A053305.

A056079 Number of 7 X 7 binary matrices with n ones, with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 2, 15, 79, 420, 1744, 6197, 18715, 50042, 118121, 250025, 475791, 820987, 1287695, 1845875, 2423114, 2923474, 3246721, 3327677, 3150758, 2761802, 2242711, 1690526, 1183725, 771951, 469281, 267108, 142542, 71844, 34271, 15685, 6861, 2948, 1223, 513, 209, 90, 34, 16, 6, 3, 1, 1

Offset: 7

Vladeta Jovovic, Aug 04 2000

Sum_{k=0..49} a(n)=A054976(7).

Cf. A053304.

G.f. : Z(S_7 X S_7; x_1, x_2, ...)-2*Z(S_7 X S_6; x_1, x_2, ...)+Z(S_6 X S_6; x_1, x_2, ...) if we replace x_i by 1+x^i, where Z(S_i X S_j; x_1, x_2, ...) is cycle index of Cartesian product of symmetric groups S_i and S_j of degree i and j, respectively.

More terms from Sean A. Irvine, Apr 14 2022

A052373 Number of nonnegative integer 7 X 7 matrices with sum of elements equal to n, under row and column permutations.

Original entry on oeis.org

1, 1, 4, 10, 33, 91, 298, 910, 2974, 9655, 32287, 108274, 367489, 1246921, 4229171, 14246120, 47542245, 156588539, 507914513, 1618965097, 5064384168, 15531406244, 46670874679, 137372332583, 396053582039, 1118577433593

Offset: 0

Vladeta Jovovic, Mar 08 2000

nonn

a(n) = A007716(n) for n=0..7.

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Row 7 of A318795.

Cf. A002724, A053307, A053304.

cp's OEIS Frontend

A049311 Number of (0,1) matrices with n ones and no zero rows or columns, up to row and column permutations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A052371 Triangle T(n,k) of n X n binary matrices with k=0...n^2 ones up to row and column permutations.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A121231 Number of n X n binary matrices M (that is, real matrices with entries 0 and 1) such that M^2 is also a binary matrix.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

A052370 Number of 6 X 6 binary matrices with n=0...36 ones up to row and column permutations.

Views

Author

Keywords

Comments

Crossrefs

A056079 Number of 7 X 7 binary matrices with n ones, with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A052373 Number of nonnegative integer 7 X 7 matrices with sum of elements equal to n, under row and column permutations.

Views

Author

Keywords

Comments

Links

Crossrefs