A318128 -id:A318128

Search: a318128 -id:a318128

Displaying 1-9 of 9 results found.

page 1

A318129

Number of sets of nonempty subsets of {1,...,n} with intersection {}.

+10
9

1, 1, 3, 91, 31827, 2147158387, 9223372011085950171, 170141183460469231602560095290109272523, 57896044618658097711785492504343953923912733397452774312538303978325772978595

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

Table of n, a(n) for n=0..8.

FORMULA

Binomial transform of A318128.

a(n) = A318130(n) - 2^(2^(n - 1) - 1).

EXAMPLE

The a(2) = 3 sets of sets are {}, {{1},{2}}, {{1},{2},{1,2}}.

MATHEMATICA

Table[Length[Select[Subsets[Rest[Subsets[Range[n]]]], Or[#=={}, Intersection@@#=={}]&]], {n, 0, 4}]

CROSSREFS

Cf. A000371, A001146, A003465, A119563, A131288.

Cf. A318128, A318130, A318131, A318132.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 18 2018

STATUS

approved

A318131

Number of non-isomorphic sets of finite (possibly empty) sets with union {1,2,...,n} and intersection {}.

+10
5

1, 1, 6, 60, 3836, 37325360, 25626412263611792, 67516342973185974276922865448446208, 2871827610052485009904013737758920847534777143951264797898686184985092096

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

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

FORMULA

a(n) = 2*(A055621(n) - A055621(n-1)) = 2*(A000612(n) - 2*A000612(n-1) + A000612(n-2)) for n >= 2. - Andrew Howroyd, Jan 29 2024

EXAMPLE

Non-isomorphic representatives of the a(2) = 6 sets of sets:

{{1},{2}}

{{},{1,2}}

{{},{1},{2}}

{{},{1},{1,2}}

{{1},{2},{1,2}}

{{},{1},{2},{1,2}}

MATHEMATICA

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[Subsets[Range[n]]], And[Union@@#===Range[n], Intersection@@#=={}]&]]], {n, 4}]

CROSSREFS

Cf. A000371, A000612, A003465, A055621, A119563, A131288, A283877, A293606, A304997.

Cf. A318128, A318129, A318130, A318132.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 18 2018

EXTENSIONS

a(5) onwards from Andrew Howroyd, Jan 29 2024

STATUS

approved

A318132

Number of non-isomorphic set-systems (finite sets of finite nonempty sets) with union {1,2,...,n} and intersection {}.

+10
5

1, 0, 2, 26, 1884, 18660728, 12813206113141264, 33758171486592987125648226573752576, 1435913805026242504952006868879460423733630400489039411798068453617852416

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

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

FORMULA

a(n) = A055621(n) - 2*A055621(n-1) = A000612(n) - 3*A000612(n-1) + 2*A000612(n-2) for n >= 2. - Andrew Howroyd, Jan 29 2024

EXAMPLE

Non-isomorphic representatives of the a(3) = 26 set-systems:

{{1},{2,3}}

{{1},{2},{3}}

{{1},{2},{1,3}}

{{1},{2},{1,2,3}}

{{1},{1,2},{2,3}}

{{1},{2,3},{1,2,3}}

{{1,2},{1,3},{2,3}}

{{1},{2},{3},{1,2}}

{{1},{2},{3},{1,2,3}}

{{1},{2},{1,2},{1,3}}

{{1},{2},{1,3},{2,3}}

{{1},{2},{1,2},{1,2,3}}

{{1},{2},{1,3},{1,2,3}}

{{1},{1,2},{1,3},{2,3}}

{{1},{1,2},{2,3},{1,2,3}}

{{1},{2},{3},{1,2},{1,3}}

{{1,2},{1,3},{2,3},{1,2,3}}

{{1},{2},{3},{1,2},{1,2,3}}

{{1},{2},{1,2},{1,3},{2,3}}

{{1},{2},{1,2},{1,3},{1,2,3}}

{{1},{2},{1,3},{2,3},{1,2,3}}

{{1},{1,2},{1,3},{2,3},{1,2,3}}

{{1},{2},{3},{1,2},{1,3},{2,3}}

{{1},{2},{3},{1,2},{1,3},{1,2,3}}

{{1},{2},{1,2},{1,3},{2,3},{1,2,3}}

{{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

MATHEMATICA

Table[Length[Union[sysnorm/@Select[Subsets[Rest[Subsets[Range[n]]]], And[Union@@#===Range[n], Intersection@@#=={}]&]]], {n, 4}]

CROSSREFS

Cf. A000371, A000612, A003465, A055621, A119563, A131288, A283877, A293606, A304997.

Cf. A318128, A318129, A318130, A318131.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 18 2018

EXTENSIONS

a(5) onwards from Andrew Howroyd, Jan 29 2024

STATUS

approved

A326365

Number of intersecting antichains with empty intersection (meaning there is no vertex in common to all the edges) covering n vertices.

+10
5

1, 0, 0, 1, 23, 1834, 1367903, 229745722873, 423295077919493525420

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

Covering means there are no isolated vertices. A set system (set of sets) is an antichain if no part is a subset of any other, and is intersecting if no two parts are disjoint.

LINKS

Table of n, a(n) for n=0..8.

EXAMPLE

The a(4) = 23 intersecting antichains with empty intersection:

{{1,2},{1,3},{2,3,4}}

{{1,2},{1,4},{2,3,4}}

{{1,2},{2,3},{1,3,4}}

{{1,2},{2,4},{1,3,4}}

{{1,3},{1,4},{2,3,4}}

{{1,3},{2,3},{1,2,4}}

{{1,3},{3,4},{1,2,4}}

{{1,4},{2,4},{1,2,3}}

{{1,4},{3,4},{1,2,3}}

{{2,3},{2,4},{1,3,4}}

{{2,3},{3,4},{1,2,4}}

{{2,4},{3,4},{1,2,3}}

{{1,2},{1,3,4},{2,3,4}}

{{1,3},{1,2,4},{2,3,4}}

{{1,4},{1,2,3},{2,3,4}}

{{2,3},{1,2,4},{1,3,4}}

{{2,4},{1,2,3},{1,3,4}}

{{3,4},{1,2,3},{1,2,4}}

{{1,2},{1,3},{1,4},{2,3,4}}

{{1,2},{2,3},{2,4},{1,3,4}}

{{1,3},{2,3},{3,4},{1,2,4}}

{{1,4},{2,4},{3,4},{1,2,3}}

{{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

MATHEMATICA

stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];

Table[Length[Select[stableSets[Subsets[Range[n], {1, n}], Or[Intersection[#1, #2]=={}, SubsetQ[#1, #2]]&], And[Union@@#==Range[n], #=={}||Intersection@@#=={}]&]], {n, 0, 4}]

CROSSREFS

Intersecting antichain covers are A305844.

Intersecting covers with empty intersection are A326364.

Antichain covers with empty intersection are A305001.

The binomial transform is the non-covering case A326366.

Covering, intersecting antichains with empty intersection are A326365.

Cf. A006126, A007363, A014466, A051185, A058891, A305843, A307249, A318128, A318129, A326361, A326362, A326363.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jul 01 2019

EXTENSIONS

a(7)-a(8) from Andrew Howroyd, Aug 14 2019

STATUS

approved

A326366

Number of intersecting antichains of nonempty subsets of {1..n} with empty intersection (meaning there is no vertex in common to all the edges).

+10
5

1, 1, 1, 2, 28, 1960, 1379273, 229755337549, 423295079757497714059

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

A set system (set of sets) is an antichain if no edge is a subset of any other, and is intersecting if no two edges are disjoint.

LINKS

Table of n, a(n) for n=0..8.

FORMULA

a(n) = A326375(n) - 1.

a(n) = A001206(n+1) + A307249(n) - A014466(n). - Andrew Howroyd, Aug 14 2019

EXAMPLE

The a(0) = 1 through a(4) = 28 intersecting antichains with empty intersection:

{} {} {} {} {}

{{12}{13}{23}} {{12}{13}{23}}

{{12}{14}{24}}

{{13}{14}{34}}

{{23}{24}{34}}

{{12}{13}{234}}

{{12}{14}{234}}

{{12}{23}{134}}

{{12}{24}{134}}

{{13}{14}{234}}

{{13}{23}{124}}

{{13}{34}{124}}

{{14}{24}{123}}

{{14}{34}{123}}

{{23}{24}{134}}

{{23}{34}{124}}

{{24}{34}{123}}

{{12}{134}{234}}

{{13}{124}{234}}

{{14}{123}{234}}

{{23}{124}{134}}

{{24}{123}{134}}

{{34}{123}{124}}

{{12}{13}{14}{234}}

{{12}{23}{24}{134}}

{{13}{23}{34}{124}}

{{14}{24}{34}{123}}

{{123}{124}{134}{234}}

MATHEMATICA

stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];

Table[Length[Select[stableSets[Subsets[Range[n], {1, n}], Or[Intersection[#1, #2]=={}, SubsetQ[#1, #2]]&], #=={}||Intersection@@#=={}&]], {n, 0, 4}]

CROSSREFS

The case with empty edges allowed is A326375.

Intersecting antichains of nonempty sets are A001206.

Intersecting set systems with empty intersection are A326373.

Antichains of nonempty sets with empty intersection are A006126 or A307249.

The inverse binomial transform is the covering case A326365.

Cf. A007363, A014466, A051185, A058891, A305001, A305843, A305844, A318128, A318129, A326361, A326362, A326363, A326364.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jul 01 2019

EXTENSIONS

a(7)-a(8) from Andrew Howroyd, Aug 14 2019

STATUS

approved

A318130

Number of sets of subsets of {1,...,n} with intersection {}.

+10
4

2, 3, 11, 219, 64595, 4294642035, 18446744047940725979, 340282366920938463334247399005993378251, 115792089237316195423570985008687907850547725730273056332267095982282337798563

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,1

LINKS

Table of n, a(n) for n=0..8.

FORMULA

Binomial transform of A131288.

Inverse binomial transform of A119563(n) = 2^(2^n) + 2^n - 1.

EXAMPLE

The a(2) = 11 sets of sets:

{}

{{}}

{{},{1}}

{{},{2}}

{{1},{2}}

{{},{1,2}}

{{},{1},{2}}

{{},{1},{1,2}}

{{},{2},{1,2}}

{{1},{2},{1,2}}

{{},{1},{2},{1,2}}

MATHEMATICA

Table[Length[Select[Subsets[Subsets[Range[n]]], Or[#=={}, Intersection@@#=={}]&]], {n, 0, 4}]

CROSSREFS

Cf. A000371, A001146, A003465, A119563, A131288, A318128, A318129.

Cf. A318128, A318129, A318131, A318132.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 18 2018

STATUS

approved

A326364

Number of intersecting set systems with empty intersection (meaning there is no vertex in common to all the edges) covering n vertices.

+10
4

1, 0, 0, 2, 426, 987404, 887044205940, 291072121051815578010398, 14704019422368226413234332571239460300433492086, 12553242487939461785560846872353486129110194397301168776798213375239447299205732561174066488

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

Covering means there are no isolated vertices. A set system (set of sets) is intersecting if no two edges are disjoint.

LINKS

Table of n, a(n) for n=0..9.

FORMULA

Inverse binomial transform of A326373. - Andrew Howroyd, Aug 12 2019

EXAMPLE

The a(3) = 2 intersecting set systems with empty intersection:

{{1,2},{1,3},{2,3}}

{{1,2},{1,3},{2,3},{1,2,3}}

MATHEMATICA

stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];

Table[Length[Select[stableSets[Subsets[Range[n], {1, n}], Intersection[#1, #2]=={}&], And[Union@@#==Range[n], #=={}||Intersection@@#=={}]&]], {n, 0, 4}]

CROSSREFS

Covering set systems with empty intersection are A318128.

Covering, intersecting set systems are A305843.

Covering, intersecting antichains with empty intersection are A326365.

Cf. A006126, A007363, A014466, A051185, A058891, A305844, A307249, A318129, A326361, A326362, A326363.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jul 01 2019

EXTENSIONS

a(6)-a(9) from Andrew Howroyd, Aug 12 2019

STATUS

approved

A326373

Number of intersecting set systems with empty intersection (meaning there is no vertex in common to all the edges) on n vertices.

+10
3

1, 1, 1, 3, 435, 989555, 887050136795, 291072121058024908202443, 14704019422368226413236661148207899662350666147, 12553242487939461785560846872353486129110194529637343578112251094358919036718815137721635299

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

A set system (set of sets) is intersecting if no two edges are disjoint.

LINKS

Table of n, a(n) for n=0..9.

FORMULA

a(n) = A051185(n) - 1 - Sum_{k=1..n-1} binomial(n,k)*A000371(k). - Andrew Howroyd, Aug 12 2019

EXAMPLE

The a(3) = 3 intersecting set systems with empty intersection:

{}

{{1,2},{1,3},{2,3}}

{{1,2},{1,3},{2,3},{1,2,3}}

MATHEMATICA

stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];

Table[Length[Select[stableSets[Subsets[Range[n], {1, n}], Intersection[#1, #2]=={}&], And[#=={}||Intersection@@#=={}]&]], {n, 0, 4}]

CROSSREFS

The inverse binomial transform is the covering case A326364.

Set systems with empty intersection are A318129.

Intersecting set systems are A051185.

Intersecting antichains with empty intersection are A326366.

Cf. A000371, A006126, A007363, A014466, A058891, A305844, A307249, A318128, A326361, A326362, A326363, A326365.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jul 01 2019

EXTENSIONS

a(6)-a(9) from Andrew Howroyd, Aug 12 2019

STATUS

approved

A326375

Number of intersecting antichains of subsets of {1..n} with empty intersection (meaning there is no vertex in common to all the edges).

+10
1

2, 2, 2, 3, 29, 1961, 1379274, 229755337550, 423295079757497714060

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,1

COMMENTS

A set system (set of sets) is an antichain if no edge is a subset of any other, and is intersecting if no two edges are disjoint.

LINKS

Table of n, a(n) for n=0..8.

FORMULA

a(n) = A326366(n) + 1.

EXAMPLE

The a(4) = 29 antichains:

{}

{{}}

{{1,2},{1,3},{2,3}}

{{1,2},{1,4},{2,4}}

{{1,3},{1,4},{3,4}}

{{2,3},{2,4},{3,4}}

{{1,2},{1,3},{2,3,4}}

{{1,2},{1,4},{2,3,4}}

{{1,2},{2,3},{1,3,4}}

{{1,2},{2,4},{1,3,4}}

{{1,3},{1,4},{2,3,4}}

{{1,3},{2,3},{1,2,4}}

{{1,3},{3,4},{1,2,4}}

{{1,4},{2,4},{1,2,3}}

{{1,4},{3,4},{1,2,3}}

{{2,3},{2,4},{1,3,4}}

{{2,3},{3,4},{1,2,4}}

{{2,4},{3,4},{1,2,3}}

{{1,2},{1,3,4},{2,3,4}}

{{1,3},{1,2,4},{2,3,4}}

{{1,4},{1,2,3},{2,3,4}}

{{2,3},{1,2,4},{1,3,4}}

{{2,4},{1,2,3},{1,3,4}}

{{3,4},{1,2,3},{1,2,4}}

{{1,2},{1,3},{1,4},{2,3,4}}

{{1,2},{2,3},{2,4},{1,3,4}}

{{1,3},{2,3},{3,4},{1,2,4}}

{{1,4},{2,4},{3,4},{1,2,3}}

{{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

MATHEMATICA

stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];

Table[Length[Select[stableSets[Subsets[Range[n]], Or[Intersection[#1, #2]=={}, SubsetQ[#1, #2]]&], #=={}||Intersection@@#=={}&]], {n, 0, 4}]

CROSSREFS

The case without empty edges is A326366.

Intersecting antichains are A326372.

Antichains of nonempty sets with empty intersection are A006126 or A307249.

Cf. A001206, A007363, A014466, A051185, A058891, A305001, A305843, A305844, A318128, A318129, A326363, A326365, A326373.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jul 03 2019

EXTENSIONS

a(7)-a(8) from Andrew Howroyd, Aug 14 2019

STATUS

approved

page 1

Search completed in 0.011 seconds