cp's OEIS Frontend

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

%I A321584 #12 Jan 17 2024 14:29:15
%S A321584 1,1,2,6,27,159,1154,9968,99861,1138234,14544650,205927012,3199714508,
%T A321584 54131864317,990455375968,19488387266842,410328328297512,
%U A321584 9205128127109576,219191041679766542,5521387415218119528,146689867860276432637,4099255234885039058842,120199458455807733040338
%N A321584 Number of connected (0,1)-matrices with n ones and no zero rows or columns.
%C A321584 A matrix is connected if the positions in each row (or each column) of the nonzero entries form a connected hypergraph.
%H A321584 Andrew Howroyd, <a href="/A321584/b321584.txt">Table of n, a(n) for n = 0..100</a>
%e A321584 The a(4) = 27 matrices:
%e A321584   [1111]
%e A321584 .
%e A321584   [111][111][111][11][110][110][101][101][100][011][011][010][001]
%e A321584   [100][010][001][11][101][011][110][011][111][110][101][111][111]
%e A321584 .
%e A321584   [11][11][11][11][10][10][10][10][01][01][01][01]
%e A321584   [10][10][01][01][11][11][10][01][11][11][10][01]
%e A321584   [10][01][10][01][10][01][11][11][10][01][11][11]
%e A321584 .
%e A321584   [1]
%e A321584   [1]
%e A321584   [1]
%e A321584   [1]
%t A321584 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]]]]]]]]];
%t A321584 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+ *)
%o A321584 (PARI)
%o A321584 NonZeroCols(M)={my(C=Vec(M)); Mat(vector(#C, n, sum(k=1, n, (-1)^(n-k)*binomial(n,k)*C[k])))}
%o A321584 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}
%o A321584 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
%Y A321584 Cf. A007716, A007718, A049311, A056156, A101370, A104602, A120733, A283877, A319557, A319647, A319616-A319629, A321585.
%K A321584 nonn
%O A321584 0,3
%A A321584 _Gus Wiseman_, Nov 13 2018
%E A321584 a(7) onwards from _Andrew Howroyd_, Jan 17 2024