login
Number of connected nonnegative integer matrices with sum of entries equal to n and no zero rows or columns.
6

%I #14 Jan 19 2024 10:55:25

%S 1,1,3,11,52,312,2290,19920,200522,2293677,29389005,416998371,

%T 6490825772,109972169413,2014696874717,39684502845893,836348775861331,

%U 18777970539419957,447471215460930665,11279275874429302811,299844572529989373703,8383794111721619471384,245956060268568277412668

%N Number of connected nonnegative integer matrices with sum of entries equal to n and no zero rows or columns.

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

%H Andrew Howroyd, <a href="/A321585/b321585.txt">Table of n, a(n) for n = 0..100</a>

%e The a(3) = 11 matrices:

%e [3] [2 1] [1 2] [1 1 1]

%e .

%e [2] [1 1] [1 1] [1] [1 0] [0 1]

%e [1] [1 0] [0 1] [2] [1 1] [1 1]

%e .

%e [1]

%e [1]

%e [1]

%t multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]];

%t 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 Table[Length[Select[multsubs[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,5}] (* Mathematica 7.0+ *)

%o (PARI)

%o NonZeroCols(M)={my(C=Vec(M)); Mat(vector(#C, n, sum(k=1, n, (-1)^(n-k)*binomial(n,k)*C[k])))}

%o 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 seq(n)={my(M=matrix(n,n,i,j,sum(k=1, n, binomial(i*j+k-1,k)*x^k, O(x*x^n) ))); Vec(1 + vecsum(vecsum(Vec( ConnectedMats( NonZeroCols( NonZeroCols(M)~))))))} \\ _Andrew Howroyd_, Jan 17 2024

%Y Cf. A007718, A056156, A120733, A319557, A319565, A319647, A319616-A319629, A321584.

%K nonn

%O 0,3

%A _Gus Wiseman_, Nov 13 2018

%E a(7) onwards from _Andrew Howroyd_, Jan 17 2024