A321609 -id:A321609 - 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

A057150 Triangle read by rows: T(n,k) = number of k X k binary matrices with n ones, with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 0, 5, 2, 1, 0, 0, 4, 11, 2, 1, 0, 0, 3, 21, 14, 2, 1, 0, 0, 1, 34, 49, 15, 2, 1, 0, 0, 1, 33, 131, 69, 15, 2, 1, 0, 0, 0, 33, 248, 288, 79, 15, 2, 1, 0, 0, 0, 19, 410, 840, 420, 82, 15, 2, 1, 0, 0, 0, 14, 531, 2144, 1744, 497, 83, 15, 2, 1

Offset: 1

Vladeta Jovovic, Aug 14 2000

Also the number of non-isomorphic set multipartitions (multisets of sets) of weight n with k parts and k vertices. - Gus Wiseman, Nov 14 2018

			[1], [0,1], [0,1,1], [0,1,2,1], [0,0,5,2,1], [0,0,4,11,2,1], ...;
There are 8 square binary matrices with 5 ones, with no zero rows or columns, up to row and column permutation: 5 of size 3 X 3:
[0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1]
[0 0 1] [0 1 0] [0 1 1] [0 1 1] [1 1 0]
[1 1 1] [1 1 1] [1 0 1] [1 1 0] [1 1 0]
2 of size 4 X 4:
[0 0 0 1] [0 0 0 1]
[0 0 0 1] [0 0 1 0]
[0 0 1 0] [0 1 0 0]
[1 1 0 0] [1 0 0 1]
and 1 of size 5 X 5:
[0 0 0 0 1]
[0 0 0 1 0]
[0 0 1 0 0]
[0 1 0 0 0]
[1 0 0 0 0].
From _Gus Wiseman_, Nov 14 2018: (Start)
Triangle begins:
   1
   0   1
   0   1   1
   0   1   2   1
   0   0   5   2   1
   0   0   4  11   2   1
   0   0   3  21  14   2   1
   0   0   1  34  49  15   2   1
   0   0   1  33 131  69  15   2   1
   0   0   0  33 248 288  79  15   2   1
Non-isomorphic representatives of the multiset partitions counted in row 6 {0,0,4,11,2,1} are:
  {{12}{13}{23}}  {{1}{1}{1}{234}}  {{1}{2}{3}{3}{45}}  {{1}{2}{3}{4}{5}{6}}
  {{1}{23}{123}}  {{1}{1}{24}{34}}  {{1}{2}{3}{5}{45}}
  {{13}{23}{23}}  {{1}{1}{4}{234}}
  {{3}{23}{123}}  {{1}{2}{34}{34}}
                  {{1}{3}{24}{34}}
                  {{1}{3}{4}{234}}
                  {{1}{4}{24}{34}}
                  {{1}{4}{4}{234}}
                  {{2}{4}{12}{34}}
                  {{3}{4}{12}{34}}
                  {{4}{4}{12}{34}}
(End)

Row sums give A057151.
Cf. A049311, A056037, A056079, A056080, A057149, A057151, A057152.
Cf. A007716, A048291, A054976, A101370, A104601, A104602, A120732, A120733, A135588, A319616, A321609, A321615.

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_] := 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!)];
T[n_, k_] := M[k, k, n] - 2*M[k, k - 1, n] + M[k - 1, k - 1, n];
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 10 2019, after Andrew Howroyd *)

\\ See A321609 for M.
T(n,k) = M(k,k,n) - 2*M(k,k-1,n) + M(k-1,k-1,n); \\ Andrew Howroyd, Nov 14 2018

Duplicate seventh row removed by Gus Wiseman, Nov 14 2018

A053304 Number of 7 X 7 binary matrices with n=0..49 ones up to row and column permutations.

Original entry on oeis.org

1, 1, 3, 6, 16, 34, 90, 211, 515, 1229, 2960, 6893, 15753, 34450, 72235, 143477, 269186, 473945, 781713, 1203617, 1728192, 2310376, 2874232, 3325215, 3576980, 3576980, 3325215, 2874232, 2310376, 1728192, 1203617, 781713, 473945, 269186

Offset: 0

Vladeta Jovovic, Mar 05 2000

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

Row 7 of A052371 and A321609.

Cf. A002724, A049311.

\\ See A321609 for M.
vector(50, n, M(7,7,n-1))

a(n) = A049311(n) for n <= 7.

Sum_{n=0..49} a(n) = 33642660 = A002724(7).

A053305 Number of 8 X 8 binary matrices with n=0..64 ones up to row and column permutations.

Original entry on oeis.org

1, 1, 3, 6, 16, 34, 90, 211, 558, 1371, 3601, 9209, 24110, 61740, 157559, 390832, 946490, 2206364, 4948194, 10591141, 21606125, 41821936, 76738813, 133157386, 218402867, 338187004, 494330780, 681660841, 886842587, 1088201827

Offset: 0

Vladeta Jovovic, Mar 05 2000

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

Row 8 of A052371 and A321609.

Cf. A049311, A002724.

\\ See A321609 for M.
vector(65, n, M(8, 8, n-1))

a(n) = A049311(n) for n <= 8.

Sum_{n=0..64} a(n) = 14685630688 = A002724(8).

A334550 Triangle read by rows: T(n,k) is the number of binary matrices with n ones, k columns and no zero rows or columns, up to permutations of rows and columns.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 5, 5, 5, 1, 5, 12, 9, 7, 1, 9, 23, 29, 17, 11, 1, 9, 39, 62, 57, 28, 15, 1, 14, 63, 147, 154, 110, 47, 22, 1, 14, 102, 278, 409, 329, 194, 73, 30, 1, 20, 150, 568, 991, 1023, 664, 335, 114, 42, 1, 20, 221, 1020, 2334, 2844, 2267, 1243, 549, 170, 56

Offset: 1

Andrew Howroyd, Jul 03 2020

T(n,k) is also the number of non-isomorphic set multipartitions (multisets of sets) of weight n with k parts.

			Triangle begins:
  1;
  1,  2;
  1,  2,  3;
  1,  5,  5,   5;
  1,  5, 12,   9,   7;
  1,  9, 23,  29,  17,  11;
  1,  9, 39,  62,  57,  28, 15;
  1, 14, 63, 147, 154, 110, 47, 22;
  ...
The T(4,3) = 5 matrices are:
  [1 0 0]   [1 0 0]   [1 1 0]   [1 1 1]   [1 1 0]
  [1 0 0]   [1 0 0]   [1 0 0]   [1 0 0]   [1 0 1]
  [0 1 0]   [0 1 1]   [0 0 1]
  [0 0 1]
The T(4,3) = 5 the set multipartitions are:
  {{1,2}, {3}, {4}},
  {{1,2}, {3}, {3}},
  {{1,2}, {1}, {3}},
  {{1,2}, {1}, {1}},
  {{1,2}, {1}, {2}}.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Row sums are A049311.
Main diagonal is A000041.
Cf. A317533, A321609.

\\ See A321609 for definition of M.
T(n, k)={M(k, n, n) - M(k-1, n, n)}
for(n=1, 10, for(k=1, n, print1(T(n, k), ", ")); print)

\\ Faster version.
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, n)={prod(j=1, #q, (1+x^lcm(t, q[j]) + O(x*x^n))^gcd(t, q[j]))}
G(m,n)={my(s=0); forpart(q=m, s+=permcount(q)*exp(sum(t=1, n, (K(q, t, n)-1)/t) + O(x*x^n))); s/m!}
A(n,m=n)={my(p=sum(k=0, m, G(k,n)*y^k)*(1-y)); matrix(n, m, n, k, polcoef(polcoef(p, n, x), k, y))}
{ my(T=A(10)); for(n=1, #T, print(T[n,1..n])) }

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

A057150 Triangle read by rows: T(n,k) = number of k X k binary matrices with n ones, with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A053304 Number of 7 X 7 binary matrices with n=0..49 ones up to row and column permutations.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A053305 Number of 8 X 8 binary matrices with n=0..64 ones up to row and column permutations.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A334550 Triangle read by rows: T(n,k) is the number of binary matrices with n ones, k columns and no zero rows or columns, up to permutations of rows and columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI