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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 13 2018
EXTENSIONS
a(7) onwards from Andrew Howroyd, Jan 17 2024
STATUS
approved