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

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.

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

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