login
Number of non-isomorphic set-systems of weight n with at least one endpoint.
10

%I #9 Jan 27 2024 16:06:01

%S 0,1,2,4,8,18,40,94,228,579,1508,4092,11478,33337,100016,309916,

%T 990008,3257196,11021851,38314009,136657181,499570867,1869792499,

%U 7158070137,28003286261,111857491266,455852284867,1893959499405,8017007560487,34552315237016,151534813272661

%N Number of non-isomorphic set-systems of weight n with at least one endpoint.

%C A set-system is a finite set of finite nonempty sets of positive integers. An endpoint is a vertex appearing only once (degree 1). The weight of a set-system is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

%H Andrew Howroyd, <a href="/A330052/b330052.txt">Table of n, a(n) for n = 0..50</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Degree_(graph_theory)">Degree (graph theory)</a>

%F a(n) = A283877(n) - A330054(n). - _Andrew Howroyd_, Jan 27 2024

%e Non-isomorphic representatives of the a(1) = 1 through a(5) = 18 multiset partitions:

%e {1} {12} {123} {1234} {12345}

%e {1}{2} {1}{12} {1}{123} {1}{1234}

%e {1}{23} {12}{13} {12}{123}

%e {1}{2}{3} {1}{234} {12}{134}

%e {12}{34} {1}{2345}

%e {1}{2}{13} {12}{345}

%e {1}{2}{34} {1}{12}{13}

%e {1}{2}{3}{4} {1}{12}{23}

%e {1}{12}{34}

%e {1}{2}{123}

%e {1}{2}{134}

%e {1}{2}{345}

%e {1}{23}{45}

%e {2}{13}{14}

%e {1}{2}{3}{12}

%e {1}{2}{3}{14}

%e {1}{2}{3}{45}

%e {1}{2}{3}{4}{5}

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

%t strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];

%t brute[{}]:={};brute[m_]:=If[Union@@m!={}&&Union@@m!=Range[Max@@Flatten[m]],brute[m/.Rule@@@Table[{(Union@@m)[[i]],i},{i,Length[Union@@m]}]],First[Sort[brute[m,1]]]];brute[m_,1]:=Table[Sort[Sort/@(m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])],{p,Permutations[Union@@m]}];

%t Table[Length[Select[Union[brute/@Join@@mps/@strnorm[n]],UnsameQ@@#&&And@@UnsameQ@@@#&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]

%Y The complement is counted by A330054.

%Y The multiset partition version is A330058.

%Y Non-isomorphic set-systems with at least one singleton are A330053.

%Y Non-isomorphic set-systems counted by vertices are A000612.

%Y Non-isomorphic set-systems counted by weight are A283877.

%Y Cf. A007716, A055621, A306005, A317533, A317794, A319559, A320665, A330055, A330056.

%K nonn

%O 0,3

%A _Gus Wiseman_, Nov 30 2019

%E a(11) onwards from _Andrew Howroyd_, Jan 27 2024