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

0, 1, 2, 4, 8, 18, 40, 94, 228, 579, 1508, 4092, 11478, 33337, 100016, 309916, 990008, 3257196, 11021851, 38314009, 136657181, 499570867, 1869792499, 7158070137, 28003286261, 111857491266, 455852284867, 1893959499405, 8017007560487, 34552315237016, 151534813272661

Offset: 0

Author

Gus Wiseman, Nov 30 2019

Keywords

• nonn

Comments

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.

Examples

			Non-isomorphic representatives of the a(1) = 1 through a(5) = 18 multiset partitions:
  {1}  {12}    {123}      {1234}        {12345}
       {1}{2}  {1}{12}    {1}{123}      {1}{1234}
               {1}{23}    {12}{13}      {12}{123}
               {1}{2}{3}  {1}{234}      {12}{134}
                          {12}{34}      {1}{2345}
                          {1}{2}{13}    {12}{345}
                          {1}{2}{34}    {1}{12}{13}
                          {1}{2}{3}{4}  {1}{12}{23}
                                        {1}{12}{34}
                                        {1}{2}{123}
                                        {1}{2}{134}
                                        {1}{2}{345}
                                        {1}{23}{45}
                                        {2}{13}{14}
                                        {1}{2}{3}{12}
                                        {1}{2}{3}{14}
                                        {1}{2}{3}{45}
                                        {1}{2}{3}{4}{5}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50
• Wikipedia, Degree (graph theory)

Crossrefs

The complement is counted by A330054.

The multiset partition version is A330058.

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

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

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

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

Programs

Mathematica

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
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]}];
Table[Length[Select[Union[brute/@Join@@mps/@strnorm[n]],UnsameQ@@#&&And@@UnsameQ@@@#&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]

Formula

a(n) = A283877(n) - A330054(n). - Andrew Howroyd, Jan 27 2024

Extensions

a(11) onwards from Andrew Howroyd, Jan 27 2024