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,3

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.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..50

Wikipedia, Degree (graph theory)

Formula

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

Example

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}

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}]

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.

Sequence in context: A288309 A096813 A058387 * A317787 A019231 A333865

Adjacent sequences: A330049 A330050 A330051 * A330053 A330054 A330055

Keyword

nonn

Author

Gus Wiseman, Nov 30 2019

Extensions

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

Status

approved