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

A120732 Number of square matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n.

Original entry on oeis.org

1, 1, 3, 15, 107, 991, 11267, 151721, 2360375, 41650861, 821881709, 17932031225, 428630422697, 11138928977049, 312680873171465, 9428701154866535, 303957777464447449, 10431949496859168189, 379755239311735494421

Offset: 0

Vladeta Jovovic, Aug 18 2006

nonn

			From _Gus Wiseman_, Nov 14 2018: (Start)
The a(3) = 15 matrices:
  [3]
.
  [2 0] [1 1] [1 1] [1 0] [1 0] [0 2] [0 1] [0 1]
  [0 1] [1 0] [0 1] [1 1] [0 2] [1 0] [2 0] [1 1]
.
  [1 0 0] [1 0 0] [0 1 0] [0 1 0] [0 0 1] [0 0 1]
  [0 1 0] [0 0 1] [1 0 0] [0 0 1] [1 0 0] [0 1 0]
  [0 0 1] [0 1 0] [0 0 1] [1 0 0] [0 1 0] [1 0 0]
(End)

G. C. Greubel, Table of n, a(n) for n = 0..250

Cf. A007716, A048291, A054976, A057149, A057150, A057151, A104601, A104602, A120733, A138178, A316983, A319616.

Table[1/n!*Sum[(-1)^(n-k)*StirlingS1[n,k]*Sum[(m!)^2*StirlingS2[k,m]^2,{m,0,k}],{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, May 07 2014 *)
multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]]; Table[Length[Select[multsubs[Tuples[Range[n],2],n],Union[First/@#]==Union[Last/@#]==Range[Max@@First/@#]&]],{n,5}] (* Gus Wiseman, Nov 14 2018 *)

a(n) = (1/n!)*Sum_{k=0..n} (-1)^(n-k)*Stirling1(n,k)*A048144(k).
G.f.: Sum_{n>=0} Sum_{j=0..n} (-1)^(n-j)*binomial(n,j)*((1-x)^(-j)-1)^n.
a(n) ~ c * n! / (sqrt(n) * (log(2))^(2*n)), where c = 0.4670932578797312973586879293426... . - Vaclav Kotesovec, May 07 2014
In closed form, c = 2^(log(2)/2-2) / (log(2) * sqrt(Pi*(1-log(2)))). - Vaclav Kotesovec, May 03 2015
G.f.: Sum_{n>=0} (1-x)^n * (1 - (1-x)^n)^n. - Paul D. Hanna, Mar 26 2018

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

Original entry on oeis.org

1, 3, 17, 179, 3835, 200082, 29610804, 13702979132, 20677458750966, 103609939177198046, 1745061194503344181714, 99860890306900024150675406, 19611238933283757244479826044874, 13340750149227624084760722122669739026, 31706433098827528779057124372265863803044450

Offset: 1

Vladeta Jovovic, May 27 2000

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

			From _Gus Wiseman_, Nov 18 2018: (Start)
Inequivalent representatives of the a(3) = 17 matrices:
  100 100 100 100 100 010 010 001 001 001 001 110 101 101 011 011 111
  100 010 001 011 011 001 101 001 101 011 111 101 011 011 011 111 111
  011 001 011 011 111 111 011 111 011 111 111 011 011 111 111 111 111
Non-isomorphic representatives of the a(1) = 1 through a(3) = 17 set multipartitions:
  {{1}}  {{1},{2}}      {{1},{2},{3}}
         {{2},{1,2}}    {{1},{1},{2,3}}
         {{1,2},{1,2}}  {{1},{3},{2,3}}
                        {{1},{2,3},{2,3}}
                        {{2},{1,3},{2,3}}
                        {{2},{3},{1,2,3}}
                        {{3},{1,3},{2,3}}
                        {{3},{3},{1,2,3}}
                        {{1,2},{1,3},{2,3}}
                        {{1},{2,3},{1,2,3}}
                        {{1,3},{2,3},{2,3}}
                        {{3},{2,3},{1,2,3}}
                        {{1,3},{2,3},{1,2,3}}
                        {{2,3},{2,3},{1,2,3}}
                        {{3},{1,2,3},{1,2,3}}
                        {{2,3},{1,2,3},{1,2,3}}
                        {{1,2,3},{1,2,3},{1,2,3}}
(End)

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

Column sums of A057150.

Cf. A007716, A048291 (labeled), A049311, A057149, A057151, A104601, A104602, A319616, A320808.

A002724 = Cases[Import["https://oeis.org/A002724/b002724.txt", "Table"], {, }][[All, 2]];
A002725 = Cases[Import["https://oeis.org/A002725/b002725.txt", "Table"], {, }][[All, 2]];
a[n_] := A002724[[n + 1]] - 2 A002725[[n]] + A002724[[n]];
a /@ Range[1, 13] (* Jean-François Alcover, Sep 14 2019 *)

a(n) = A002724(n) - 2*A002725(n-1) + A002724(n-1).

More terms from David Wasserman, Mar 06 2002

Terms a(14) and beyond from Andrew Howroyd, Apr 11 2020

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

Original entry on oeis.org

1, 1, 2, 4, 8, 18, 41, 102, 252, 666, 1789, 5031, 14486, 43280, 132777, 420267, 1366307, 4566966, 15661086, 55081118, 198425478, 731661754, 2758808581, 10629386376, 41814350148, 167830018952, 686822393793, 2864024856054, 12162059027416, 52564545391789

Offset: 1

Vladeta Jovovic, Aug 14 2000

nonn

Number of square binary matrices with n ones and with no zero rows or columns is A104602(n). - Vladeta Jovovic, Mar 25 2006

Also the number of non-isomorphic square set multipartitions (multisets of sets) of weight n. A multiset partition or hypergraph is square if its length (number of blocks or edges) is equal to its number of vertices. The weight of a multiset partition is the sum of sizes of its parts. - Gus Wiseman, Nov 16 2018

			There are 666 square binary matrices with 10 ones, with no zero rows or columns, up to row and column permutation: 33 of size 4 X 4, 248 of size 5 X 5, 288 of size 6 X 6, 79 of size 7 X 7, 15 of size 8 X 8, 2 of size 9 X 9 and 1 of size 10 X 10. Cf. A057150.
From _Gus Wiseman_, Nov 16 2018: (Start)
Non-isomorphic representatives of the a(1) = 1 through a(6) = 18 square set multipartitions:
  {1}  {1}{2}  {2}{12}    {12}{12}      {1}{23}{23}      {12}{13}{23}
               {1}{2}{3}  {1}{1}{23}    {2}{13}{23}      {1}{23}{123}
                          {1}{3}{23}    {2}{3}{123}      {13}{23}{23}
                          {1}{2}{3}{4}  {3}{13}{23}      {3}{23}{123}
                                        {3}{3}{123}      {1}{1}{1}{234}
                                        {1}{2}{2}{34}    {1}{1}{24}{34}
                                        {1}{2}{4}{34}    {1}{1}{4}{234}
                                        {1}{2}{3}{4}{5}  {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}
                                                         {1}{2}{3}{3}{45}
                                                         {1}{2}{3}{5}{45}
                                                         {1}{2}{3}{4}{5}{6}
(End)

Max Alekseyev, Table of n, a(n) for n = 1..30

Cf. A049311, A056037, A056079, A056080, A057149, A057150, A057152.

Cf. A054976, A101370, A104601, A104602, A120732, A283877, A319616.

More terms from Max Alekseyev, May 31 2007

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

A321615 Triangle read by rows: T(n,k) is the number of k X k integer matrices with sum of elements n, 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, 1, 6, 3, 1, 0, 1, 9, 13, 3, 1, 0, 1, 17, 38, 20, 3, 1, 0, 1, 23, 97, 82, 23, 3, 1, 0, 1, 36, 217, 311, 126, 24, 3, 1, 0, 1, 46, 453, 968, 624, 151, 24, 3, 1, 0, 1, 65, 868, 2825, 2637, 933, 162, 24, 3, 1, 0, 1, 80, 1585, 7394, 10098, 4942, 1132, 165, 24, 3, 1

Offset: 0

Andrew Howroyd, Nov 14 2018

Also the number of non-isomorphic multiset partitions of weight n with k parts and k vertices, where the weight of a multiset partition is the sum of sizes of its parts. - Gus Wiseman, Nov 18 2018

			Triangle begins:
    1
    0  1
    0  1    1
    0  1    2    1
    0  1    6    3    1
    0  1    9   13    3    1
    0  1   17   38   20    3    1
    0  1   23   97   82   23    3    1
    0  1   36  217  311  126   24    3    1
    0  1   46  453  968  624  151   24    3    1
    0  1   65  868 2825 2637  933  162   24    3    1

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Columns k=0..3 are A000007, A000012, A054974, A054975.
Row sums are A319616.
Cf. A007716, A048291, A054976, A057149, A057150, A104601, A120732, A318795, A320808.

(* See A318795 for M[m, n, k]. *)
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, 11}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 24 2018, from PARI *)

\\ See A318795 for M.
T(n, k) = if(k==0, n==0, M(k, k, n) - 2*M(k, k-1, n) + M(k-1, k-1, n));

\\ See A340652 for G.
T(n)={[Vecrev(p) | p<-Vec(1 + sum(k=1, n, y^k*(polcoef(G(k, n, n, y), k, y) - polcoef(G(k-1, n, n, y), k, y))))]}
{ my(A=T(10)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Jan 16 2024

Column k=0 inserted by Andrew Howroyd, Jan 17 2024

A057152 Limiting number of m X m binary matrices with m+n ones, with no zero rows or columns, up to row and column permutations, as m tends to infinity.

Original entry on oeis.org

1, 2, 15, 83, 545, 3493, 24006, 169419, 1249225, 9542846, 75621458, 620011391, 5253319121

Offset: 0

Vladeta Jovovic, Aug 14 2000

Cf. A056080, A056037, A056079, A057149-A057151, A049311.

a(n) = limit of A057149(m,m+n) as m tends to infinity

a(n) = A057149(3*n,4*n)

Formula and a(6)-a(8) added by Max Alekseyev, Jan 24 2010

a(9)-a(12) from Max Alekseyev, Feb 17 2010

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

A120732 Number of square matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A321615 Triangle read by rows: T(n,k) is the number of k X k integer matrices with sum of elements n, with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A057152 Limiting number of m X m binary matrices with m+n ones, with no zero rows or columns, up to row and column permutations, as m tends to infinity.

Views

Author

Keywords

Crossrefs

Formula

Extensions