A306005 -id:A306005 - cp's OEIS frontend

A321194 Regular triangle where T(n,k) is the number of non-isomorphic multiset partitions of weight n with k connected components.

1, 3, 1, 6, 3, 1, 17, 12, 3, 1, 40, 35, 12, 3, 1, 125, 112, 45, 12, 3, 1, 354, 347, 148, 45, 12, 3, 1, 1159, 1122, 512, 163, 45, 12, 3, 1, 3774, 3651, 1724, 572, 163, 45, 12, 3, 1, 13113, 12320, 5937, 2020, 593, 163, 45, 12, 3, 1, 46426, 42407, 20492, 7117, 2110, 593, 163, 45, 12, 3, 1

Offset: 1

Gus Wiseman, Oct 29 2018

			Triangle begins:
      1
      3     1
      6     3     1
     17    12     3     1
     40    35    12     3     1
    125   112    45    12     3     1
    354   347   148    45    12     3     1
   1159  1122   512   163    45    12     3     1
   3774  3651  1724   572   163    45    12     3     1
  13113 12320  5937  2020   593   163    45    12     3     1
The fourth row counts the following non-isomorphic multiset partitions.
  {{1,1,1,1}}        {{1,1},{2,2}}      {{1},{2},{3,3}}    {{1},{2},{3},{4}}
  {{1,1,2,2}}        {{1},{2,2,2}}      {{1},{2},{3,4}}
  {{1,2,2,2}}        {{1},{2,3,3}}      {{1},{2},{3},{3}}
  {{1,2,3,3}}        {{1,2},{3,3}}
  {{1,2,3,4}}        {{1},{2,3,4}}
  {{1},{1,1,1}}      {{1,2},{3,4}}
  {{1,1},{1,1}}      {{1},{1},{2,2}}
  {{1},{1,2,2}}      {{1},{1},{2,3}}
  {{1,2},{1,2}}      {{1},{2},{2,2}}
  {{1,2},{2,2}}      {{1},{3},{2,3}}
  {{1,3},{2,3}}      {{1},{1},{2},{2}}
  {{2},{1,2,2}}      {{1},{2},{2},{2}}
  {{3},{1,2,3}}
  {{1},{1},{1,1}}
  {{1},{2},{1,2}}
  {{2},{2},{1,2}}
  {{1},{1},{1},{1}}

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

First column is A007718. Row sums are A007716.

Cf. A006126, A048143, A143543, A306005, A316983, A317672, A317674, A319616, A321155.

O.g.f.: Product 1/(1 - t*x^n)^A007718(n).

Terms a(56) and beyond from Andrew Howroyd, Jan 11 2024

A317795 Number of non-isomorphic set-systems spanning n vertices with no singletons.

Original entry on oeis.org

1, 0, 1, 6, 172, 611852, 200253853704512, 263735716028826427334553305221120, 5609038300883759793482640992086670066496449147691597380832361377955840

Offset: 0

Gus Wiseman, Aug 07 2018

nonn

			Non-isomorphic representatives of the a(3) = 6 set-systems:
  {123}
  {12}{13}
  {12}{123}
  {12}{13}{23}
  {12}{13}{123}
  {12}{13}{23}{123}

First differences of A317794.

Cf. A000088, A000612, A003180, A007716, A055621, A283877, A300913, A306005, A317533, A317757, A319876.

sysnorm[{}]:={};sysnorm[m_]:=If[Union@@m!=Range[Max@@Flatten[m]],sysnorm[m/.Rule@@@Table[{(Union@@m)[[i]],i},{i,Length[Union@@m]}]],First[Sort[sysnorm[m,1]]]];sysnorm[m_,aft_]:=If[Length[Union@@m]<=aft,{m},With[{mx=Table[Count[m,i,{2}],{i,Select[Union@@m,#>=aft&]}]},Union@@(sysnorm[#,aft+1]&/@Union[Table[Map[Sort,m/.{par+aft-1->aft,aft->par+aft-1},{0,1}],{par,First/@Position[mx,Max[mx]]}]])]];
Table[Length[Union[sysnorm/@Select[Subsets[Select[Subsets[Range[n]],Length[#]>1&]],Union@@#==Range[n]&]]],{n,4}]

More terms from Gus Wiseman, Dec 13 2018

A368409 Number of non-isomorphic connected set-systems of weight n contradicting a strict version of the axiom of choice.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 3, 5, 16, 41, 130

Offset: 0

Gus Wiseman, Dec 25 2023

A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			Non-isomorphic representatives of the a(4) = 1 through a(8) = 16 set-systems:
  {1}{2}{12}  .  {1}{2}{13}{23}  {1}{3}{23}{123}    {1}{5}{15}{2345}
                 {1}{2}{3}{123}  {1}{4}{14}{234}    {2}{13}{23}{123}
                 {2}{3}{13}{23}  {2}{3}{23}{123}    {3}{13}{23}{123}
                                 {3}{12}{13}{23}    {3}{4}{34}{1234}
                                 {1}{2}{3}{13}{23}  {1}{2}{13}{24}{34}
                                                    {1}{2}{3}{14}{234}
                                                    {1}{2}{3}{23}{123}
                                                    {1}{2}{3}{4}{1234}
                                                    {1}{3}{4}{14}{234}
                                                    {2}{3}{12}{13}{23}
                                                    {2}{3}{13}{24}{34}
                                                    {2}{3}{14}{24}{34}
                                                    {2}{3}{4}{14}{234}
                                                    {2}{4}{13}{24}{34}
                                                    {3}{4}{13}{24}{34}
                                                    {3}{4}{14}{24}{34}

Wikipedia, Axiom of choice.

For unlabeled graphs we have A140636, connected case of A140637.
For labeled graphs: A140638, connected case of A367867 (complement A133686).
This is the connected case of A368094.
The complement is A368410, connected case of A368095.
Allowing repeats: A368411, connected case of A368097, ranks A355529.
Complement with repeats: A368412, connected case of A368098, ranks A368100.
Allowing repeat edges only: connected case of A368421 (complement A368422).
A000110 counts set partitions, non-isomorphic A000041.
A003465 counts covering set-systems, unlabeled A055621.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A134964, A302545, A306005, A317533, A321405, A326031, A367903, A367907, A368187, A368413.

sps[{}]:={{}}; sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]&/@sps[Range[n]]],{s,Flatten[MapIndexed[Table[#2, {#1}]&,#]]&/@IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{i,p[[i]]}, {i,Length[p]}])],{p,Permutations[Union@@m]}]]];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}],Length[Intersection@@s[[#]]]>0&]}, If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[brute/@Select[mpm[n], UnsameQ@@#&&And@@UnsameQ@@@#&&Length[csm[#]]==1&&Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,6}]

A330055 Number of non-isomorphic set-systems of weight n with no singletons or endpoints.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 1, 3, 5, 16, 24, 90, 179, 567, 1475, 4623, 13650, 44475, 144110, 492017, 1706956, 6124330, 22442687, 84406276, 324298231, 1273955153, 5106977701, 20885538133, 87046940269, 369534837538, 1596793560371, 7019424870960, 31374394197536, 142514998263015

Offset: 0

Gus Wiseman, Nov 30 2019

nonn

A set-system is a finite set of finite nonempty set of positive integers. A singleton is an edge of size 1. 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.

			Non-isomorphic representatives of the a(7) = 1 through a(10) = 16 set-systems:
  {12}{13}{123}  {12}{134}{234}    {12}{134}{1234}    {12}{1345}{2345}
                 {12}{34}{1234}    {123}{124}{134}    {123}{124}{1234}
                 {12}{13}{24}{34}  {12}{13}{14}{234}  {123}{145}{2345}
                                   {12}{13}{23}{123}  {12}{345}{12345}
                                   {12}{13}{24}{134}  {12}{13}{124}{134}
                                                      {12}{13}{124}{234}
                                                      {12}{13}{14}{1234}
                                                      {12}{13}{24}{1234}
                                                      {12}{13}{245}{345}
                                                      {12}{13}{45}{2345}
                                                      {12}{34}{123}{124}
                                                      {12}{34}{125}{345}
                                                      {12}{34}{135}{245}
                                                      {13}{24}{123}{124}
                                                      {12}{13}{14}{23}{24}
                                                      {12}{13}{24}{35}{45}

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

The labeled version is A330056.
The "multi" version is A320665.
Non-isomorphic set-systems with no singletons are A306005.
Non-isomorphic set-systems with no endpoints are A330054.
Non-isomorphic set-systems counted by vertices are A000612.
Non-isomorphic set-systems counted by weight are A283877.
Cf. A007716, A055621, A302545, A317533, A317794, A319559, A321405, A330052, A330058.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={my(g=x*Ser(WeighT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k)))); (1-x)*g-subst(g,x,x^2)}
S(q, t, k)={(x-x^2)*sum(j=1, #q, if(t%q[j]==0, q[j])) + O(x*x^k)}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, s+=permcount(q)*polcoef(exp(sum(t=1, n, subst(K(q, t, n\t)-S(q,t,n\t),x,x^t)/t )), n)); s/n!)} \\ Andrew Howroyd, Jan 27 2024

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

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

Original entry on oeis.org

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

Gus Wiseman, Nov 30 2019

nonn

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.

			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}

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

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.

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

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

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

A330054 Number of non-isomorphic set-systems of weight n with no endpoints.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 4, 4, 16, 26, 87, 181, 570, 1453, 4464, 13038, 41548, 132217, 442603, 1506803, 5305174, 19092816, 70548770, 266495254, 1029835424, 4063610148, 16366919221, 67217627966, 281326631801, 1199048810660, 5201341196693, 22950740113039, 102957953031700

Offset: 0

Gus Wiseman, Nov 30 2019

nonn

A set-system is a finite set of finite nonempty set 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.

			Non-isomorphic representatives of the a(0) = 1 through a(8) = 16 multiset partitions (empty columns not shown):
  0  {1}{2}{12}  {12}{13}{23}    {13}{23}{123}      {12}{134}{234}
                 {1}{23}{123}    {1}{3}{23}{123}    {1}{234}{1234}
                 {1}{2}{13}{23}  {3}{12}{13}{23}    {12}{34}{1234}
                 {1}{2}{3}{123}  {1}{2}{3}{13}{23}  {1}{12}{34}{234}
                                                    {12}{13}{24}{34}
                                                    {1}{2}{134}{234}
                                                    {1}{2}{34}{1234}
                                                    {2}{13}{14}{234}
                                                    {2}{13}{23}{123}
                                                    {3}{13}{23}{123}
                                                    {1}{2}{13}{24}{34}
                                                    {1}{2}{3}{14}{234}
                                                    {1}{2}{3}{23}{123}
                                                    {1}{2}{3}{4}{1234}
                                                    {2}{3}{12}{13}{23}
                                                    {1}{2}{3}{4}{12}{34}

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

The complement is counted by A330052.
The multiset partition version is A302545.
Non-isomorphic set-systems with no singletons are A306005.
Non-isomorphic set-systems counted by vertices are A000612.
Non-isomorphic set-systems counted by weight are A283877.
Cf. A007716, A055621, A317533, A317794, A319559, A320665, A330055, A330056, A330058.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={my(g=1+x*Ser(WeighT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k)))); (1-x)*g - subst(g,x,x^2)}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, s+=permcount(q)*polcoef(exp(sum(t=1, n, subst(K(q,t,n\t)/t,x,x^t) )), n)); s/n!)} \\ Andrew Howroyd, Jan 27 2024

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

A368422 Number of non-isomorphic set multipartitions of weight n satisfying a strict version of the axiom of choice.

Original entry on oeis.org

1, 1, 2, 4, 9, 18, 43, 95, 233, 569

Offset: 0

Gus Wiseman, Dec 26 2023

A set multipartition is a finite multiset of finite nonempty sets. The weight of a set multipartition is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

The axiom of choice says that, given any sequence of nonempty sets, it is possible to choose a sequence containing an element from each. In the strict version, the elements of this sequence must be distinct, meaning none is chosen more than once.

			Non-isomorphic representatives of the a(1) = 1 through a(5) = 18 set multipartitions:
  {{1}}  {{1,2}}    {{1,2,3}}      {{1,2,3,4}}        {{1,2,3,4,5}}
         {{1},{2}}  {{1},{2,3}}    {{1,2},{1,2}}      {{1},{2,3,4,5}}
                    {{2},{1,2}}    {{1},{2,3,4}}      {{1,2},{3,4,5}}
                    {{1},{2},{3}}  {{1,2},{3,4}}      {{1,4},{2,3,4}}
                                   {{1,3},{2,3}}      {{2,3},{1,2,3}}
                                   {{3},{1,2,3}}      {{4},{1,2,3,4}}
                                   {{1},{2},{3,4}}    {{1},{2,3},{2,3}}
                                   {{1},{3},{2,3}}    {{1},{2},{3,4,5}}
                                   {{1},{2},{3},{4}}  {{1},{2,3},{4,5}}
                                                      {{1},{2,4},{3,4}}
                                                      {{1},{4},{2,3,4}}
                                                      {{2},{1,3},{2,3}}
                                                      {{2},{3},{1,2,3}}
                                                      {{3},{1,3},{2,3}}
                                                      {{4},{1,2},{3,4}}
                                                      {{1},{2},{3},{4,5}}
                                                      {{1},{2},{4},{3,4}}
                                                      {{1},{2},{3},{4},{5}}

Wikipedia, Axiom of choice.

The case of unlabeled graphs is A134964, complement A140637.
Set multipartitions have ranks A302478, cf. A073576.
The case of labeled graphs is A133686, complement A367867.
The complement without repeats is A368094 connected A368409.
Without repeats we have A368095, connected A368410.
The complement allowing repeats is A368097, ranks A355529.
Allowing repeated elements gives A368098, ranks A368100.
Factorizations of this type are counted by A368414, complement A368413.
The complement is counted by A368421.
A000110 counts set partitions, non-isomorphic A000041.
A003465 counts covering set-systems, unlabeled A055621.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A302545, A306005, A317533, A318360, A367903.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]&/@sps[Range[n]]],{s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
Table[Length[Union[brute /@ Select[mpm[n],And@@UnsameQ@@@#&&Select[Tuples[#], UnsameQ@@#&]!={}&]]],{n,0,6}]

A322109 Heinz numbers of integer partitions that are the vertex-degrees of some set multipartition (multiset of nonempty sets) with no singletons.

Original entry on oeis.org

1, 4, 8, 9, 12, 16, 18, 24, 25, 27, 30, 32, 36, 40, 45, 48, 49, 50, 54, 60, 63, 64, 70, 72, 75, 80, 81, 84, 90, 96, 98, 100, 105, 108, 112, 120, 121, 125, 126, 128, 135, 140, 144, 147, 150, 154, 160, 162, 165, 168, 169, 175, 180, 189, 192, 196, 198, 200, 210

Offset: 1

Gus Wiseman, Nov 26 2018

nonn

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

Also Heinz numbers of partitions whose greatest part is less than or equal to half the sum of parts, i.e., numbers n whose sum of prime indices A056239(n) is at least twice the greatest prime index A061395(n). - Gus Wiseman, May 23 2021

			Each term paired with its Heinz partition and a realizing set multipartition with no singletons:
   1:      (): {}
   4:    (11): {{1,2}}
   8:   (111): {{1,2,3}}
   9:    (22): {{1,2},{1,2}}
  12:   (211): {{1,2},{1,3}}
  16:  (1111): {{1,2,3,4}}
  18:   (221): {{1,2},{1,2,3}}
  24:  (2111): {{1,2},{1,3,4}}
  25:    (33): {{1,2},{1,2},{1,2}}
  27:   (222): {{1,2,3},{1,2,3}}
  30:   (321): {{1,2},{1,2},{1,3}}
  32: (11111): {{1,2,3,4,5}}
  36:  (2211): {{1,2},{1,2,3,4}}
  40:  (3111): {{1,2},{1,3},{1,4}}

These partitions are counted by A110618.
The even-weight version is A320924.
The conjugate case of equality is A340387.
The conjugate version is A344291.
The opposite conjugate version is A344296.
The opposite version is A344414.
The case of equality is A344415.
The opposite even-weight version is A344416.
A000070 counts non-multigraphical partitions.
A025065 counts palindromic partitions.
A035363 counts partitions into even parts.
A056239 adds up prime indices, row sums of A112798.
A058696 counts partitions of even numbers, ranked by A300061.
A334201 adds up all prime indices except the greatest.
Cf. A000041, A000569, A265640, A283877, A306005, A318361, A320922, A320923, A320925.

nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
sqnopfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[sqnopfacs[n/d],Min@@#>=d&]],{d,Select[Rest[Divisors[n]],!PrimeQ[#]&&SquareFreeQ[#]&]}]]
Select[Range[100],Length[sqnopfacs[Times@@Prime/@nrmptn[#]]]>0&]

A061395(a(n)) <= A056239(a(n))/2.

A330058 Number of non-isomorphic multiset partitions of weight n with at least one endpoint.

Original entry on oeis.org

0, 1, 2, 7, 21, 68, 214, 706, 2335, 7968, 27661, 98366, 357212, 1326169, 5027377, 19459252, 76850284, 309531069, 1270740646, 5314727630, 22633477157, 98096319485, 432490992805, 1938762984374, 8832924638252, 40882143931620, 192148753444380, 916747097916418

Offset: 0

Gus Wiseman, Nov 30 2019

nonn

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
An endpoint is a vertex appearing only once (degree 1).
Also the number of non-isomorphic multiset partitions of weight n with at least one singleton.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions:
  {1}  {12}    {122}      {1222}
       {1}{2}  {123}      {1233}
               {1}{22}    {1234}
               {1}{23}    {1}{222}
               {2}{12}    {12}{22}
               {1}{2}{2}  {1}{233}
               {1}{2}{3}  {12}{33}
                          {1}{234}
                          {12}{34}
                          {13}{23}
                          {2}{122}
                          {3}{123}
                          {1}{1}{23}
                          {1}{2}{22}
                          {1}{2}{33}
                          {1}{2}{34}
                          {1}{3}{23}
                          {2}{2}{12}
                          {1}{2}{2}{2}
                          {1}{2}{3}{3}
                          {1}{2}{3}{4}

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

The case of set-systems is A330053 (singletons) or A330052 (endpoints).
The complement is counted by A302545.
Cf. A007716, A283877, A306005, A330054, A330055, A330059.

a(n) = A007716(n) - A302545(n). - Andrew Howroyd, Jan 15 2023

Terms a(11) and beyond from Andrew Howroyd, Jan 15 2023

A368410 Number of non-isomorphic connected set-systems of weight n satisfying a strict version of the axiom of choice.

Original entry on oeis.org

0, 1, 1, 2, 3, 7, 15, 32, 80, 198, 528

Offset: 0

Gus Wiseman, Dec 25 2023

A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			Non-isomorphic representatives of the a(1) = 1 through a(6) = 15 set-systems:
  {1}  {12}  {123}    {1234}    {12345}      {123456}
             {2}{12}  {13}{23}  {14}{234}    {125}{345}
                      {3}{123}  {23}{123}    {134}{234}
                                {4}{1234}    {15}{2345}
                                {2}{13}{23}  {34}{1234}
                                {2}{3}{123}  {5}{12345}
                                {3}{13}{23}  {1}{14}{234}
                                             {12}{13}{23}
                                             {1}{23}{123}
                                             {13}{24}{34}
                                             {14}{24}{34}
                                             {3}{14}{234}
                                             {3}{23}{123}
                                             {3}{4}{1234}
                                             {4}{14}{234}

Wikipedia, Axiom of choice.

For unlabeled graphs we have A005703, connected case of A134964.
For labeled graphs we have A129271, connected case of A133686.
The complement for labeled graphs is A140638, connected case of A367867.
The complement without connectedness is A367903, ranks A367907.
Without connectedness we have A368095, ranks A367906,
Complement with repeats: A368097, connected case of A368411, ranks A355529.
The complement is counted by A368409, connected case of A368094.
With repeats allowed: A368412, connected case of A368098, ranks A368100.
A000110 counts set-partitions, non-isomorphic A000041.
A003465 counts covering set-systems, unlabeled A055621.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A001055, A140637, A302545, A306005, A321194, A321405, A367902, A368414, A368422.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort/@(#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]],{s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{i,p[[i]]}, {i,Length[p]}])],{p,Permutations[Union@@m]}]]];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]}, If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[brute/@Select[mpm[n], UnsameQ@@#&&And@@UnsameQ@@@#&&Length[csm[#]]==1&&Select[Tuples[#], UnsameQ@@#&]!={}&]]],{n,0,6}]

cp's OEIS Frontend

A321194 Regular triangle where T(n,k) is the number of non-isomorphic multiset partitions of weight n with k connected components.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A317795 Number of non-isomorphic set-systems spanning n vertices with no singletons.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

A368409 Number of non-isomorphic connected set-systems of weight n contradicting a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A330055 Number of non-isomorphic set-systems of weight n with no singletons or endpoints.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A330054 Number of non-isomorphic set-systems of weight n with no endpoints.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A368422 Number of non-isomorphic set multipartitions of weight n satisfying a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A322109 Heinz numbers of integer partitions that are the vertex-degrees of some set multipartition (multiset of nonempty sets) with no singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs