A327903 - OEIS

A327903

Number of set-systems covering n vertices where every edge has a different sum.

%I #8 Oct 03 2019 16:46:19

%S 1,1,5,77,7369,10561753,839653402893,15924566366443524837,

%T 315320784127456186118309342769,

%U 29238175285109256786706269143580213236526609,59347643832090275881798554403880633753161146711444051797893301

%N Number of set-systems covering n vertices where every edge has a different sum.

%C A set-system is a set of nonempty sets. It is covering if there are no isolated (uncovered) vertices.

%H Andrew Howroyd, <a href="/A327903/b327903.txt">Table of n, a(n) for n = 0..20</a>

%H Gus Wiseman, <a href="/A038041/a038041.txt">Sequences counting and ranking multiset partitions whose part lengths, sums, or averages are constant or strict.</a>

%e The a(3) = 77 set-systems:

%e 123 1-23 1-2-3 1-2-3-13 1-2-3-13-23 1-2-3-13-23-123

%e 2-13 1-2-13 1-2-3-23 1-2-12-13-23 1-2-12-13-23-123

%e 1-123 1-2-23 1-2-12-13 1-2-3-13-123

%e 12-13 1-3-23 1-2-12-23 1-2-3-23-123

%e 12-23 2-3-13 1-2-13-23 1-2-12-13-123

%e 13-23 1-12-13 1-2-3-123 1-2-12-23-123

%e 2-123 1-12-23 1-3-13-23 1-2-13-23-123

%e 3-123 1-13-23 2-3-13-23 1-3-13-23-123

%e 12-123 1-2-123 1-12-13-23 2-3-13-23-123

%e 13-123 1-3-123 1-2-12-123 1-12-13-23-123

%e 23-123 2-12-13 1-2-13-123 2-12-13-23-123

%e 2-12-23 1-2-23-123

%e 2-13-23 1-3-13-123

%e 2-3-123 1-3-23-123

%e 3-13-23 2-12-13-23

%e 1-12-123 2-3-13-123

%e 1-13-123 2-3-23-123

%e 12-13-23 1-12-13-123

%e 1-23-123 1-12-23-123

%e 2-12-123 1-13-23-123

%e 2-13-123 2-12-13-123

%e 2-23-123 2-12-23-123

%e 3-13-123 2-13-23-123

%e 3-23-123 3-13-23-123

%e 12-13-123 12-13-23-123

%e 12-23-123

%e 13-23-123

%t stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];

%t qes[n_]:=Select[stableSets[Subsets[Range[n],{1,n}],Total[#1]==Total[#2]&],Union@@#==Range[n]&];

%t Table[Length[qes[n]],{n,0,4}]

%o (PARI) \\ by inclusion/exclusion on covered vertices.

%o C(v)={my(u=Vecrev(-1 + prod(k=1, #v, 1 + x^v[k]))); prod(i=1, #u, 1 + u[i])}

%o a(n)={my(s=0); forsubset(n, v, s += (-1)^(n-#v)*C(v)); s} \\ _Andrew Howroyd_, Oct 02 2019

%Y The antichain case is A326572.

%Y The graphical case is A327904.

%Y Cf. A003465, A006126, A035470, A275780, A321469, A326030, A326519, A326535, A326565, A326571, A326573.

%K nonn

%O 0,3

%A _Gus Wiseman_, Sep 30 2019

%E Terms a(4) and beyond from _Andrew Howroyd_, Oct 02 2019