A317794 -id:A317794 - cp's OEIS frontend

A330059 Number of set-systems with n vertices and no endpoints.

1, 1, 2, 63, 29471, 2144945976, 9223371624669871587, 170141183460469227599616678821978424151, 57896044618658097711785492504343953752410420469299789800819363538011879603532

Offset: 0

Gus Wiseman, Dec 01 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 a(2) = 2 set-systems are {} and {{1},{2},{1,2}}. The a(3) = 63 set-systems are:
  0                 {2}{3}{12}{13}       {1}{3}{12}{13}{23}
  {1}{2}{12}        {2}{12}{13}{23}      {2}{3}{12}{13}{23}
  {1}{3}{13}        {2}{3}{12}{123}      {1}{2}{12}{23}{123}
  {2}{3}{23}        {2}{3}{13}{123}      {1}{2}{13}{23}{123}
  {12}{13}{23}      {3}{12}{13}{23}      {1}{3}{12}{13}{123}
  {1}{23}{123}      {1}{13}{23}{123}     {1}{3}{12}{23}{123}
  {2}{13}{123}      {2}{12}{13}{123}     {1}{3}{13}{23}{123}
  {3}{12}{123}      {2}{12}{23}{123}     {2}{3}{12}{13}{123}
  {12}{13}{123}     {2}{13}{23}{123}     {2}{3}{12}{23}{123}
  {12}{23}{123}     {3}{12}{13}{123}     {2}{3}{13}{23}{123}
  {13}{23}{123}     {3}{12}{23}{123}     {1}{12}{13}{23}{123}
  {1}{2}{13}{23}    {3}{13}{23}{123}     {2}{12}{13}{23}{123}
  {1}{2}{3}{123}    {12}{13}{23}{123}    {3}{12}{13}{23}{123}
  {1}{3}{12}{23}    {1}{2}{3}{12}{13}    {1}{2}{3}{12}{13}{23}
  {1}{12}{13}{23}   {1}{2}{3}{12}{23}    {1}{2}{3}{12}{13}{123}
  {1}{2}{13}{123}   {1}{2}{3}{13}{23}    {1}{2}{3}{12}{23}{123}
  {1}{2}{23}{123}   {1}{2}{12}{13}{23}   {1}{2}{3}{13}{23}{123}
  {1}{3}{12}{123}   {1}{2}{3}{12}{123}   {1}{2}{12}{13}{23}{123}
  {1}{3}{23}{123}   {1}{2}{3}{13}{123}   {1}{3}{12}{13}{23}{123}
  {1}{12}{13}{123}  {1}{2}{3}{23}{123}   {2}{3}{12}{13}{23}{123}
  {1}{12}{23}{123}  {1}{2}{12}{13}{123}  {1}{2}{3}{12}{13}{23}{123}

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

The case with no singletons is A330056.
The unlabeled version is A330054 (by weight) or A330124 (by vertices).
Set-systems with no singletons are A016031.
Non-isomorphic set-systems with no singletons are A306005 (by weight).
Cf. A000612, A007716, A055621, A302545, A317533, A317794, A319559, A320665, A321405, A330052, A330057, A330058.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Min@@Length/@Split[Sort[Join@@#]]>1&]],{n,0,4}]

a(n) = {sum(k=0, n, (-1)^k*binomial(n,k)*2^(2^(n-k)-1)*sum(j=0, k, stirling(k,j,2)*2^(j*(n-k)) ))} \\ Andrew Howroyd, Jan 16 2023

a(n) = Sum_{k=0..n} Sum_{j=0..k} (-1)^k * binomial(n,k) * 2^(2^(n-k)-1) * Stirling2(k,j) * 2^(j*(n-k)). - Andrew Howroyd, Jan 16 2023

Terms a(5) and beyond from Andrew Howroyd, Jan 16 2023

A330057 Number of set-systems covering n vertices with no singletons or endpoints.

Original entry on oeis.org

1, 0, 0, 5, 1703, 66954642, 144115175199102143, 1329227995784915808340204290157341181, 226156424291633194186662080095093568664788471116325389572604136316742486364

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 a(3) = 5 set-systems:
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,2,3}}
  {{1,2},{2,3},{1,2,3}}
  {{1,3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

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

The version for non-isomorphic set-systems is A330055 (by weight).
The non-covering version is A330056.
Set-systems with no singletons are A016031.
Set-systems with no endpoints are A330059.
Non-isomorphic set-systems with no singletons are A306005 (by weight).
Non-isomorphic set-systems with no endpoints are A330054 (by weight).
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, A320665, A321405, A330052, A330058.

Table[Length[Select[Subsets[Subsets[Range[n],{2,n}]],Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]>1&]],{n,0,4}]

\\ here b(n) is A330056(n).
AS2(n, k) = {sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) )}
b(n) = {sum(k=0, n, (-1)^k*binomial(n,k)*2^(2^(n-k)-(n-k)-1) * sum(j=0, k\2, sum(i=0, k-2*j, binomial(k,i) * AS2(k-i, j) * (2^(n-k)-1)^i * 2^(j*(n-k)) )))}
a(n) = {sum(k=0, n, (-1)^k*binomial(n,k)*b(n-k))} \\ Andrew Howroyd, Jan 16 2023

Binomial transform is A330056.

Terms a(5) and beyond from Andrew Howroyd, Jan 16 2023

A319876 Irregular triangle read by rows where T(n,k) is the number of permutations of {1,...,n} whose action on 2-element subsets of {1,...,n} has k cycles.

Original entry on oeis.org

1, 0, 2, 0, 2, 3, 1, 0, 0, 14, 0, 9, 0, 1, 0, 0, 24, 50, 20, 0, 15, 10, 0, 0, 1, 0, 0, 0, 264, 0, 340, 0, 40, 0, 60, 0, 15, 0, 0, 0, 1, 0, 0, 0, 720, 1764, 504, 0, 1120, 630, 0, 0, 70, 105, 105, 0, 0, 21, 0, 0, 0, 0, 1, 0, 0, 0, 0, 13488, 0, 14112, 0, 3724, 0

Offset: 1

Gus Wiseman, Dec 12 2018

The permutation
  1 -> 1
  2 -> 2
  3 -> 4
  4 -> 3
acts on unordered pairs of distinct elements of {1,2,3,4} to give
  (1,2) -> (1,2)
  (1,3) -> (1,4)
  (1,4) -> (1,3)
  (2,3) -> (2,4)
  (2,4) -> (2,3)
  (3,4) -> (3,4)
which has 4 cycles
       (1,2)
  (1,3) <-> (1,4)
  (2,3) <-> (2,4)
       (3,4)
so is counted under T(4,4).

			Triangle begins:
   1
   0   2
   0   2   3   1
   0   0  14   0   9   0   1
   0   0  24  50  20   0  15  10   0   0   1
   0   0   0 264   0 340   0  40   0  60   0  15   0   0   0   1
The T(4,4) = 9 permutations: (1243), (1324), (1432), (2134), (2143), (3214), (3412), (4231), (4321).

Row n has A000124(n - 1) terms. Row sums are the factorial numbers A000142.

Cf. A000088, A000612, A000665, A000666, A003180, A050535, A070166, A317794, A317795.

Table[Length[Select[Permutations[Range[n]],PermutationCycles[Ordering[Map[Sort,Subsets[Range[n],{2}]/.Rule@@@Table[{i,#[[i]]},{i,n}],{1}]],Length]==k&]],{n,5},{k,0,n*(n-1)/2}]

A000088(n) = (1/n!) * Sum_k 2^k * T(n,k).

A330124 Number of unlabeled set-systems with n vertices and no endpoints.

Original entry on oeis.org

1, 1, 2, 22, 1776

Offset: 0

Gus Wiseman, Dec 05 2019

A set-system is a finite set of finite nonempty sets. An endpoint is a vertex appearing only once (degree 1).

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

Partial sums of the covering case A330196.
The labeled version is A330059.
The "multi" version is A302545.
Unlabeled set-systems with no endpoints counted by weight are A330054.
Unlabeled set-systems with no singletons are A317794.
Unlabeled set-systems counted by vertices are A000612.
Unlabeled set-systems counted by weight are A283877.
The case with no singletons is A320665.
Cf. A007716, A016031, A306005, A317795, A321405, A330052, A330055.

A368096 Triangle read by rows where T(n,k) is the number of non-isomorphic set-systems of length k and weight n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 5, 8, 3, 1, 0, 1, 8, 18, 13, 3, 1, 0, 1, 9, 32, 37, 15, 3, 1, 0, 1, 13, 55, 96, 59, 16, 3, 1, 0, 1, 14, 91, 209, 196, 74, 16, 3, 1, 0, 1, 19, 138, 449, 573, 313, 82, 16, 3, 1, 0, 1, 20, 206, 863, 1529, 1147, 403, 84, 16, 3, 1

Offset: 0

Gus Wiseman, Dec 28 2023

A set-system is a finite set of finite nonempty sets.

Conjecture: Column k = 2 is A101881.

			Triangle begins:
   1
   0   1
   0   1   1
   0   1   2   1
   0   1   4   3   1
   0   1   5   8   3   1
   0   1   8  18  13   3   1
   0   1   9  32  37  15   3   1
   0   1  13  55  96  59  16   3   1
   0   1  14  91 209 196  74  16   3   1
   0   1  19 138 449 573 313  82  16   3   1
   ...
Non-isomorphic representatives of the set-systems counted in row n = 5:
  .  {12345}  {1}{1234}  {1}{2}{123}  {1}{2}{3}{12}  {1}{2}{3}{4}{5}
              {1}{2345}  {1}{2}{134}  {1}{2}{3}{14}
              {12}{123}  {1}{2}{345}  {1}{2}{3}{45}
              {12}{134}  {1}{12}{13}
              {12}{345}  {1}{12}{23}
                         {1}{12}{34}
                         {1}{23}{24}
                         {1}{23}{45}

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

Row sums are A283877, connected case A300913.
For multiset partitions we have A317533.
Counting connected components instead of edges gives A321194.
For set multipartitions we have A334550.
For strict multiset partitions we have A368099.
A000110 counts set-partitions, non-isomorphic A000041.
A003465 counts covering set-systems, unlabeled A055621.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A049311 counts non-isomorphic set multipartitions, connected A056156.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A316980 counts non-isomorphic strict multiset partitions, connected A319557.
A319559 counts non-isomorphic T_0 set-systems, connected A319566.
Cf. A101881, A255903, A302545, A306005, A317532, A317794, A317795, A319560, A321405, A368094, A368095.

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],UnsameQ@@#&&And@@UnsameQ@@@#&&Length[#]==k&]]], {n,0,5},{k,0,n}]

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)={WeighT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k))}
G(n)={my(s=0); forpart(q=n, my(p=sum(t=1, n, y^t*subst(x*Ser(K(q, t, n\t))/t, x, x^t))); s+=permcount(q)*exp(p-subst(subst(p, x, x^2), y, y^2))); s/n!}
T(n)={[Vecrev(p) | p <- Vec(G(n))]}
{ my(A=T(10)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 11 2024

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

A368099 Triangle read by rows where T(n,k) is the number of non-isomorphic k-element sets of finite nonempty multisets with cardinalities summing to n, or strict multiset partitions of weight n and length k.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 3, 4, 1, 0, 5, 12, 5, 1, 0, 7, 28, 22, 5, 1, 0, 11, 66, 83, 31, 5, 1, 0, 15, 134, 252, 147, 34, 5, 1, 0, 22, 280, 726, 620, 203, 35, 5, 1, 0, 30, 536, 1946, 2283, 1069, 235, 35, 5, 1, 0, 42, 1043, 4982, 7890, 5019, 1469, 248, 35, 5, 1

Offset: 0

Gus Wiseman, Dec 31 2023

			Triangle begins:
    1
    0    1
    0    2    1
    0    3    4    1
    0    5   12    5    1
    0    7   28   22    5    1
    0   11   66   83   31    5    1
    0   15  134  252  147   34    5    1
    0   22  280  726  620  203   35    5    1
    0   30  536 1946 2283 1069  235   35    5    1
    0   42 1043 4982 7890 5019 1469  248   35    5    1
    ...
Row n = 4 counts the following representatives:
  .  {{1,1,1,1}}  {{1},{1,1,1}}  {{1},{2},{1,1}}  {{1},{2},{3},{4}}
     {{1,1,1,2}}  {{1},{1,1,2}}  {{1},{2},{1,2}}
     {{1,1,2,2}}  {{1},{1,2,2}}  {{1},{2},{1,3}}
     {{1,1,2,3}}  {{1},{1,2,3}}  {{1},{2},{3,3}}
     {{1,2,3,4}}  {{1},{2,2,2}}  {{1},{2},{3,4}}
                  {{1},{2,2,3}}
                  {{1},{2,3,4}}
                  {{1,1},{1,2}}
                  {{1,1},{2,2}}
                  {{1,1},{2,3}}
                  {{1,2},{1,3}}
                  {{1,2},{3,4}}

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

Row sums are A316980, connected case A319557.
For multiset partitions we have A317533, connected A322133.
Counting connected components instead of edges gives A321194.
For normal multiset partitions we have A330787, row sums A317776.
For set multipartitions we have A334550.
For set-systems we have A368096, row-sums A283877 (connected A300913).
A000110 counts set-partitions, non-isomorphic A000041.
A003465 counts covering set-systems, unlabeled A055621.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A049311 counts non-isomorphic set multipartitions, connected A056156.
A058891 counts set-systems, unlabeled A000612, connected A323818.
Cf. A255903, A296122, A302545, A306005, A317532, A317775, A317794, A317795, A319560, A368094, A368095.

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],UnsameQ@@#&&Length[#]==k&]]], {n,0,5},{k,0,n}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, 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)={EulerT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k))}
G(n)={my(s=0); forpart(q=n, my(p=sum(t=1, n, y^t*subst(x*Ser(K(q, t, n\t))/t, x, x^t))); s+=permcount(q)*exp(p-subst(subst(p, x, x^2), y, y^2))); s/n!}
T(n)={[Vecrev(p) | p <- Vec(G(n))]}
{ my(A=T(10)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 11 2024

A330196 Number of unlabeled set-systems covering n vertices with no endpoints.

Original entry on oeis.org

1, 0, 1, 20, 1754

Offset: 0

Gus Wiseman, Dec 05 2019

A set-system is a finite set of finite nonempty sets. An endpoint is a vertex appearing only once (degree 1).

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

First differences of the non-covering version A330124.
The "multi" version is A302545.
Unlabeled set-systems with no endpoints counted by vertices are A317794.
Unlabeled set-systems with no endpoints counted by weight are A330054.
Unlabeled set-systems counted by vertices are A000612.
Unlabeled set-systems counted by weight are A283877.
Cf. A007716, A016031, A306005, A317795, A320665, A330052, A330053, A330055.

A317792 Number of non-isomorphic multiset partitions, using normal multisets, of normal multisets of size n.

Original entry on oeis.org

1, 1, 3, 6, 15, 31, 73, 154, 345, 742, 1627, 3499

Offset: 0

Gus Wiseman, Aug 07 2018

A multiset is normal if it spans an initial interval of positive integers, and strongly normal if it has weakly decreasing multiplicities. Neither condition is necessarily preserved under isomorphism. For example, {{2},{1,1,1,2}} is isomorphic to {{1},{1,2,2,2}}, but only the latter has normal blocks, while only the former has strongly normal multiset union.

			Non-isomorphic representatives of the a(4) = 15 normal multiset partitions:
  {1111}, {1112}, {1122}, {1123}, {1234},
  {1}{111}, {1}{112}, {1}{122}, {1}{123}, {11}{11}, {11}{12}, {12}{12},
  {1}{1}{11}, {1}{1}{12},
  {1}{1}{1}{1}.

Cf. A001055, A007716, A045778, A281116, A317533, A317757, A317791, A317794, A317795.

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]]]];
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]]}]])]];
allnorm[n_]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Length[Union[sysnorm/@Select[Join@@mps/@allnorm[n],And@@(Union[#]==Range[Max@@#]&)/@#&]]],{n,6}]

a(10)-a(11) from Robert Price, Sep 15 2018

cp's OEIS Frontend

A330059 Number of set-systems with n vertices and no endpoints.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A330057 Number of set-systems covering n vertices with no singletons or endpoints.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A319876 Irregular triangle read by rows where T(n,k) is the number of permutations of {1,...,n} whose action on 2-element subsets of {1,...,n} has k cycles.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A330124 Number of unlabeled set-systems with n vertices and no endpoints.

Views

Author

Keywords

Comments

Examples

Crossrefs

A368096 Triangle read by rows where T(n,k) is the number of non-isomorphic set-systems of length k and weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A368099 Triangle read by rows where T(n,k) is the number of non-isomorphic k-element sets of finite nonempty multisets with cardinalities summing to n, or strict multiset partitions of weight n and length k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A330196 Number of unlabeled set-systems covering n vertices with no endpoints.

Views

Author

Keywords

Comments

Examples

Crossrefs

A317792 Number of non-isomorphic multiset partitions, using normal multisets, of normal multisets of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs