A321584 Number of connected (0,1)-matrices with n ones and no zero rows or columns.

1, 1, 2, 6, 27, 159, 1154, 9968, 99861, 1138234, 14544650, 205927012, 3199714508, 54131864317, 990455375968, 19488387266842, 410328328297512, 9205128127109576, 219191041679766542, 5521387415218119528, 146689867860276432637, 4099255234885039058842, 120199458455807733040338

Offset

0,3

Comments

A matrix is connected if the positions in each row (or each column) of the nonzero entries form a connected hypergraph.

Links

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

Example

The a(4) = 27 matrices:
  [1111]
.
  [111][111][111][11][110][110][101][101][100][011][011][010][001]
  [100][010][001][11][101][011][110][011][111][110][101][111][111]
.
  [11][11][11][11][10][10][10][10][01][01][01][01]
  [10][10][01][01][11][11][10][01][11][11][10][01]
  [10][01][10][01][10][01][11][11][10][01][11][11]
.
  [1]
  [1]
  [1]
  [1]

Mathematica

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Union[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Tuples[Range[n], 2], {n}], And[Union[First/@#]==Range[Max@@First/@#], Union[Last/@#]==Range[Max@@Last/@#], Length[csm[Map[Last, GatherBy[#, First], {2}]]]==1]&]], {n, 6}] (* Mathematica 7.0+ *)

Prog

(PARI)
NonZeroCols(M)={my(C=Vec(M)); Mat(vector(#C, n, sum(k=1, n, (-1)^(n-k)*binomial(n, k)*C[k])))}
ConnectedMats(M)={my([m, n]=matsize(M), R=matrix(m, n)); for(m=1, m, for(n=1, n, R[m, n] = M[m, n] - sum(i=1, m-1, sum(j=1, n-1, binomial(m-1, i-1)*binomial(n, j)*R[i, j]*M[m-i, n-j])))); R}
seq(n)={my(M=matrix(n, n, i, j, sum(k=1, n, binomial(i*j, k)*x^k, O(x*x^n) ))); Vec(1 + vecsum(vecsum(Vec( ConnectedMats( NonZeroCols( NonZeroCols(M)~)) ))))} \\ Andrew Howroyd, Jan 17 2024

Crossrefs

Cf. A007716, A007718, A049311, A056156, A101370, A104602, A120733, A283877, A319557, A319647, A319616-A319629, A321585.

Sequence in context: A307595 A058133 A306857 * A009308 A032186 A122938

Adjacent sequences: A321581 A321582 A321583 * A321585 A321586 A321587

Keyword

nonn

Author

Gus Wiseman, Nov 13 2018

Extensions

a(7) onwards from Andrew Howroyd, Jan 17 2024

Status

approved