A016031 -id:A016031 - cp's OEIS frontend

A340030 Triangle read by rows: T(n,k) is the number of hypergraphs on n labeled vertices with k edges and all vertices having even degree, 0 <= k < 2^n.

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 7, 7, 0, 0, 1, 1, 0, 0, 35, 105, 168, 280, 435, 435, 280, 168, 105, 35, 0, 0, 1, 1, 0, 0, 155, 1085, 5208, 22568, 82615, 247845, 628680, 1383096, 2648919, 4414865, 6440560, 8280720, 9398115, 9398115, 8280720, 6440560, 4414865, 2648919, 1383096, 628680, 247845, 82615, 22568, 5208, 1085, 155, 0, 0, 1

Offset: 0

Andrew Howroyd, Jan 09 2021

Hypergraphs are graphs in which an edge is connected to a nonempty subset of vertices rather than exactly two of them. An edge is a nonempty subset of vertices.
Equivalently, T(n,k) is the number of subsets of {1..2^n-1} with k elements such that the bitwise-xor of the elements is zero.
Also the coefficients of polynomials p_{n}(x) which have the representation
  p_{n}(x) = (x + 1)^(2*(n - 1) - 1)*q_{n - 1}(x), where q_{n}(x) are the polynomials defined in A340263, and n >= 2. - Peter Luschny, Jan 10 2021

			Triangle begins:
[0]  1;
[1]  1, 0;
[2]  1, 0, 0,  1;
[3]  1, 0, 0,  7,   7,   0,   0,   1;
[4]  1, 0, 0, 35, 105, 168, 280, 435, 435, 280, 168, 105, 35, 0, 0, 1;

Andrew Howroyd, Table of n, a(n) for n = 0..2046 (rows 0..10)
Wikipedia, Hypergraph.

Rows 3..8 are A002394, A010085, A010086, A010087, A010088, A010089.
Row sums are A016031(n+1).
Column k=3 gives A006095.
Cf. A058878, A281123, A340312, A340263.

T(n,k) = {(binomial(2^n-1, k) + (-1)^((k+1)\2)*(2^n-1)*binomial(2^(n-1)-1, k\2))/2^n}
{ for(n=0, 5, print(vector(2^n, k, T(n,k-1)))) }

T(n,k) = (binomial(2^n-1, k) + (-1)^ceiling(k/2)*(2^n-1)*binomial(2^(n-1)-1, floor(k/2)))/2^n.
T(n,2*k) + T(n,2*k+1) = binomial(2^n-1, k)/2^n = A281123(n,k).
T(n, k) = T(n, 2^n-1-k) for n >= 2.

A323817 Number of connected set-systems covering n vertices with no singletons.

Original entry on oeis.org

1, 0, 1, 12, 1990, 67098648, 144115187673201808, 1329227995784915871895000743748659792, 226156424291633194186662080095093570015284114833799899656335137245499581360

Offset: 0

Gus Wiseman, Jan 30 2019

nonn

			The a(3) = 12 set-systems:
  {{1, 2, 3}}
  {{1, 2}, {1, 3}}
  {{1, 2}, {2, 3}}
  {{1, 3}, {2, 3}}
  {{1, 2}, {1, 2, 3}}
  {{1, 3}, {1, 2, 3}}
  {{2, 3}, {1, 2, 3}}
  {{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}}
The A323816(4) - a(4) = 3 disconnected set-systems covering n vertices with no singletons:
  {{1, 2}, {3, 4}}
  {{1, 3}, {2, 4}}
  {{1, 4}, {2, 3}}

G. C. Greubel, Table of n, a(n) for n = 0..11

Cf. A001187, A016031, A048143, A092918, A293510, A317795, A323816 (not necessarily connected), A323818 (with singletons), A323819, A323820 (unlabeled case).

m:=10;
A323816:= func< n | (&+[(-1)^(n-j)*Binomial(n,j)*2^(2^j -j-1): j in [0..n]]) >;
f:= func< x | 1 + Log((&+[A323816(j)*x^j/Factorial(j): j in [0..m+2]])) >;
R:=PowerSeriesRing(Rationals(), m+1);
Coefficients(R!(Laplace( f(x) ))); // G. C. Greubel, Oct 05 2022

b:= n-> add(2^(2^(n-j)-n+j-1)*binomial(n, j)*(-1)^j, j=0..n):
a:= proc(n) option remember; b(n)-`if`(n=0, 0, add(
       k*binomial(n, k)*b(n-k)*a(k), k=1..n-1)/n)
    end:
seq(a(n), n=0..8);  # Alois P. Heinz, Jan 30 2019

nn=10;
ser=Sum[Sum[(-1)^(n-k)*Binomial[n,k]*2^(2^k-k-1),{k,0,n}]*x^n/n!,{n,0,nn}];
Table[SeriesCoefficient[1+Log[ser],{x,0,n}]*n!,{n,0,nn}]

m=10
def A323816(n): return sum((-1)^j*binomial(n,j)*2^(2^(n-j) -n+j-1) for j in range(n+1))
def A323817_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( 1 + log(sum(A323816(j)*x^j/factorial(j) for j in range(m+2))) ).egf_to_ogf().list()
A323817_list(m) # G. C. Greubel, Oct 05 2022

Logarithmic transform of A323816.

A368186 Number of n-covers of an unlabeled n-set.

Original entry on oeis.org

1, 1, 2, 9, 87, 1973, 118827, 20576251, 10810818595, 17821875542809, 94589477627232498, 1651805220868992729874, 96651473179540769701281003, 19238331716776641088273777321428, 13192673305726630096303157068241728202, 31503323006770789288222386469635474844616195

Offset: 0

Gus Wiseman, Dec 19 2023

nonn

			Non-isomorphic representatives of the a(1) = 1 through a(3) = 9 set-systems:
  {{1}}  {{1},{2}}    {{1},{2},{3}}
         {{1},{1,2}}  {{1},{2},{1,3}}
                      {{1},{1,2},{1,3}}
                      {{1},{1,2},{2,3}}
                      {{1},{2},{1,2,3}}
                      {{1},{1,2},{1,2,3}}
                      {{1,2},{1,3},{2,3}}
                      {{1},{2,3},{1,2,3}}
                      {{1,2},{1,3},{1,2,3}}

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

The labeled version is A054780, ranks A367917, non-covering A367916.
The case of graphs is A006649, labeled A367863, cf. A116508, A367862.
The case of connected graphs is A001429, labeled A057500.
Covers with any number of edges are counted by A003465, unlabeled A055621.
A046165 counts minimal covers, ranks A309326.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
Cf. A000088, A002494, A006126, A055130, A133686, A140638, A305000, A317795, A326754, A367901, A367902, A367903.

brute[m_]:=Table[Sort[Sort/@(m/.Rule@@@Table[{i, p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}];
Table[Length[Union[First[Sort[brute[#]]]& /@ Select[Subsets[Rest[Subsets[Range[n]]],{n}], Union@@#==Range[n]&]]], {n,0,3}]

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)={2^sum(j=1, #q, gcd(t, q[j])) - 1}
G(n,m)={if(n==0, 1, my(s=0); forpart(q=n, my(g=sum(t=1, m, K(q,t)*x^t/t, O(x*x^m))); s+=permcount(q)*exp(g - subst(g,x,x^2))); s/n!)}
a(n)=if(n ==0, 1, polcoef(G(n,n) - G(n-1,n), n)) \\ Andrew Howroyd, Jan 03 2024

a(n) = A055130(n, n) for n > 0. - Andrew Howroyd, Jan 03 2024

Terms a(6) and beyond from Andrew Howroyd, Jan 03 2024

A323816 Number of set-systems covering n vertices with no singletons.

Original entry on oeis.org

1, 0, 1, 12, 1993, 67098768, 144115187673233113, 1329227995784915871895000745158568460, 226156424291633194186662080095093570015284114833799899660370362545578585265

Offset: 0

Gus Wiseman, Jan 30 2019

nonn

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

G. C. Greubel, Table of n, a(n) for n = 0..11

Cf. A000295, A000371, A000612, A003465 (with singletons), A006129 (covers by pairs), A016031, A055154, A055621, A305001, A317795 (unlabeled case), A323817 (connected case).

[(&+[(-1)^(n-j)*Binomial(n,j)*2^(2^j -j-1): j in [0..n]]): n in [0..12]]; // G. C. Greubel, Oct 05 2022

a:= n-> add(2^(2^(n-j)-n+j-1)*binomial(n, j)*(-1)^j, j=0..n):
seq(a(n), n=0..8);  # Alois P. Heinz, Jan 30 2019

Table[Sum[(-1)^(n-k)*Binomial[n,k]*2^(2^k-k-1),{k,0,n}],{n,0,8}]

def A323816(n): return sum((-1)^j*binomial(n,j)*2^(2^(n-j) -n+j-1) for j in range(n+1))
[A323816(n) for n in range(12)] # G. C. Greubel, Oct 05 2022

Inverse binomial transform of A016031 shifted once to the left.

A330056 Number of set-systems with n vertices and no singletons or endpoints.

Original entry on oeis.org

1, 1, 1, 6, 1724, 66963208, 144115175600855641, 1329227995784915809349010517957163445, 226156424291633194186662080095093568675422295082604716043360995547325655259

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) = 6 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 covering case is A330057.
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, A008299, A302545, A317533, A317794, A319559, A320665, A321405, A330052, A330058.

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

\\ Here AS2(n,k) is A008299 (associated Stirling of 2nd kind)
AS2(n, k) = {sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) )}
a(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)) )))} \\ Andrew Howroyd, Jan 16 2023

Binomial transform of A330057.

a(n) = Sum_{k=0..n} Sum_{j=0..floor(k/2)} Sum_{i=0..k-2*j} (-1)^k * binomial(n,k) * 2^(2^(n-k)-(n-k)-1) * binomial(k,i) * AS2(k-i, j) * (2^(n-k)-1)^i * 2^(j*(n-k)) where AS2(n,k) are the associated Stirling numbers of the 2nd kind (A008299). - Andrew Howroyd, Jan 16 2023

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

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

Original entry on oeis.org

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

A330218 Least BII-number of a set-system with n distinct representatives obtainable by permuting the vertices.

Original entry on oeis.org

0, 5, 12, 180, 35636, 13

Offset: 1

Gus Wiseman, Dec 09 2019

nonn

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

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

			The sequence of set-systems together with their BII-numbers begins:
      0: {}
      5: {{1},{1,2}}
     12: {{1,2},{3}}
    180: {{1,2},{1,3},{2,3},{4}}
  35636: {{1,2},{1,3},{2,3},{1,4},{2,4},{3,4},{5}}
     13: {{1},{1,2},{3}}

Positions of first appearances in A330231.
The MM-number version is A330230.
Achiral set-systems are counted by A083323.
BII-numbers of fully chiral set-systems are A330226.
Cf. A000120, A003238, A007716, A016031, A048793, A055621, A070939, A214577, A326031, A326702, A330098, A330101, A330195, A330217, A330229, A330233.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
graprms[m_]:=Union[Table[Sort[Sort/@(m/.Apply[Rule,Table[{p[[i]],i},{i,Length[p]}],{1}])],{p,Permutations[Union@@m]}]];
dv=Table[Length[graprms[bpe/@bpe[n]]],{n,0,1000}];
Table[Position[dv,i][[1,1]]-1,{i,First[Split[Union[dv],#1+1==#2&]]}]

A330282 Number of fully chiral set-systems on n vertices.

Original entry on oeis.org

1, 2, 5, 52, 21521

Offset: 0

Gus Wiseman, Dec 10 2019

A set-system is a finite set of finite nonempty sets. It is fully chiral if every permutation of the covered vertices gives a different representative.

			The a(0) = 1 through a(2) = 5 set-systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1},{1,2}}
             {{2},{1,2}}

Costrict (or T_0) set-systems are A326940.
The covering case is A330229.
The unlabeled version is A330294, with covering case A330295.
Achiral set-systems are A083323.
BII-numbers of fully chiral set-systems are A330226.
Non-isomorphic fully chiral multiset partitions are A330227.
Fully chiral partitions are A330228.
Fully chiral factorizations are A330235.
MM-numbers of fully chiral multisets of multisets are A330236.
Cf. A000612, A016031, A319637, A330098, A330231, A330232, A330234.

graprms[m_]:=Union[Table[Sort[Sort/@(m/.Rule@@@Table[{p[[i]],i},{i,Length[p]}])],{p,Permutations[Union@@m]}]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Length[graprms[#]]==Length[Union@@#]!&]],{n,0,3}]

Binomial transform of A330229.

A330294 Number of non-isomorphic fully chiral set-systems on n vertices.

Original entry on oeis.org

1, 2, 3, 10, 899

Offset: 0

Gus Wiseman, Dec 10 2019

A set-system is a finite set of finite nonempty sets. It is fully chiral if every permutation of the covered vertices gives a different representative.

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

The labeled version is A330282.
Partial sums of A330295 (the covering case).
Unlabeled costrict (or T_0) set-systems are A326946.
BII-numbers of fully chiral set-systems are A330226.
Non-isomorphic fully chiral multiset partitions are A330227.
Fully chiral partitions are A330228.
Fully chiral factorizations are A330235.
MM-numbers of fully chiral multisets of multisets are A330236.
Cf. A000612, A016031, A055621, A083323, A283877, A319637, A330098, A330231, A330232, A330234.

A330295 Number of non-isomorphic fully chiral set-systems covering n vertices.

Original entry on oeis.org

1, 1, 1, 7, 889

Offset: 0

Gus Wiseman, Dec 10 2019

A set-system is a finite set of finite nonempty sets. It is fully chiral if every permutation of the covered vertices gives a different representative.

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

The labeled version is A330229.
First differences of A330294 (the non-covering case).
Unlabeled costrict (or T_0) set-systems are A326946.
BII-numbers of fully chiral set-systems are A330226.
Non-isomorphic fully chiral multiset partitions are A330227.
Fully chiral partitions are A330228.
Fully chiral factorizations are A330235.
MM-numbers of fully chiral multisets of multisets are A330236.
Cf. A000612, A016031, A055621, A083323, A283877, A319637, A330098, A330231, A330232, A330234, A330282.

cp's OEIS Frontend

A340030 Triangle read by rows: T(n,k) is the number of hypergraphs on n labeled vertices with k edges and all vertices having even degree, 0 <= k < 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A323817 Number of connected set-systems covering n vertices with no singletons.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A368186 Number of n-covers of an unlabeled n-set.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A323816 Number of set-systems covering n vertices with no singletons.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A330056 Number of set-systems with n vertices and no singletons or endpoints.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A330218 Least BII-number of a set-system with n distinct representatives obtainable by permuting the vertices.

Views

Author

Keywords