A305843 -id:A305843 - cp's OEIS frontend

A305855 Number of unlabeled spanning intersecting antichains on n vertices.

1, 1, 1, 3, 9, 72, 3441, 47170585

Offset: 0

Gus Wiseman, Jun 11 2018

An intersecting antichain S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection, and none of which is a subset of any other. S is spanning if every vertex is contained in some edge.

			Non-isomorphic representatives of the a(4) = 9 spanning intersecting antichains:
  {{1,2,3,4}}
  {{1,4},{2,3,4}}
  {{1,3,4},{2,3,4}}
  {{1,2},{1,3,4},{2,3,4}}
  {{1,3},{1,4},{2,3,4}}
  {{1,4},{2,4},{3,4}}
  {{1,2,4},{1,3,4},{2,3,4}}
  {{1,2},{1,3},{1,4},{2,3,4}}
  {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

Cf. A001206, A006126, A051185, A261006, A283877, A304998, A305843, A305844, A305854-A305857.

a(n) = A305857(n) - A305857(n-1) for n > 0. - Andrew Howroyd, Aug 13 2019

a(6) from Andrew Howroyd, Aug 13 2019

a(7) from Brendan McKay, May 11 2020

A305856 Number of unlabeled intersecting set-systems on up to n vertices.

Original entry on oeis.org

1, 2, 4, 14, 124, 14992, 1289845584

Offset: 0

Gus Wiseman, Jun 11 2018

An intersecting set-system is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection.

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

Cf. A001206, A006126, A051185, A261006, A283877, A304982, A304996, A304998, A305843, A305844, A305854-A305857.

a(5) from Andrew Howroyd, Aug 12 2019

a(6) from Bert Dobbelaere, Apr 28 2025

A305935 Number of labeled spanning intersecting set-systems on n vertices with no singletons.

Original entry on oeis.org

1, 0, 1, 12, 809, 1146800, 899927167353, 291136684655893185321964, 14704020783497694096988185391720223222562121969, 12553242487939982849962414795232892198542733492886483991398790450208264017757788101836749760

Offset: 0

Gus Wiseman, Jun 15 2018

nonn

An intersecting set-system S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection. S is spanning if every vertex is contained in some edge. A singleton is an edge containing only one vertex.

			The a(3) = 12 spanning intersecting set-systems with no singletons:
{{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}}

Cf. A001206, A006126, A051185, A048143, A058891, A305001, A305843, A305844, A305854-A305857, A305999, A306000, A306001, A306008.

a(n) = A305843(n) - n * A003465(n-1).

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

a(6)-a(8) from Giovanni Resta, Jun 20 2018

a(9) from Andrew Howroyd, Aug 12 2019

A306000 Number of labeled intersecting set-systems with no singletons covering some subset of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 16, 864, 1150976, 899934060544, 291136684662192699604992, 14704020783497694096990514485197495566069661696, 12553242487939982849962414795232892198542733625222671042878037323112413463887484853594095616

Offset: 0

Gus Wiseman, Jun 16 2018

nonn

An intersecting set-system S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection. A singleton is an edge containing only one vertex.

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

Cf. A001206, A006126, A051185, A048143, A058891, A305001, A305843, A305844, A305854-A305857, A305935, A305999, A306001.

a(n) = A051185(n) - n*2^(2^(n-1)-1). - Andrew Howroyd, Aug 12 2019

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

A326372 Number of intersecting antichains of (possibly empty) subsets of {1..n}.

Original entry on oeis.org

2, 3, 5, 13, 82, 2647, 1422565, 229809982113, 423295099074735261881

Offset: 0

Gus Wiseman, Jul 01 2019

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.

			The a(0) = 2 through a(3) = 13 antichains:
  {}    {}     {}       {}
  {{}}  {{}}   {{}}     {{}}
        {{1}}  {{1}}    {{1}}
               {{2}}    {{2}}
               {{1,2}}  {{3}}
                        {{1,2}}
                        {{1,3}}
                        {{2,3}}
                        {{1,2,3}}
                        {{1,2},{1,3}}
                        {{1,2},{2,3}}
                        {{1,3},{2,3}}
                        {{1,2},{1,3},{2,3}}

The case without empty edges is A001206.
The inverse binomial transform is the spanning case A305844.
The unlabeled case is A306007.
Maximal intersecting antichains are A326363.
Intersecting set systems are A051185.
Cf. A000372, A007363, A014466, A305843, A326361, A326362.

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

A326911 BII-numbers of set-systems with empty intersection.

Original entry on oeis.org

0, 3, 7, 9, 10, 11, 12, 13, 14, 15, 18, 19, 22, 23, 25, 26, 27, 28, 29, 30, 31, 33, 35, 37, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 67, 71, 73, 74, 75, 76, 77, 78, 79, 82, 83, 86, 87, 89, 90, 91, 92, 93, 94, 95

Offset: 1

Gus Wiseman, Aug 04 2019

nonn

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 finite set of finite nonempty sets 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 all set-systems with empty intersection together with their BII-numbers begins:
   0: {}
   3: {{1},{2}}
   7: {{1},{2},{1,2}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  12: {{1,2},{3}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  15: {{1},{2},{1,2},{3}}
  18: {{2},{1,3}}
  19: {{1},{2},{1,3}}
  22: {{2},{1,2},{1,3}}
  23: {{1},{2},{1,2},{1,3}}
  25: {{1},{3},{1,3}}
  26: {{2},{3},{1,3}}
  27: {{1},{2},{3},{1,3}}
  28: {{1,2},{3},{1,3}}
  29: {{1},{1,2},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}

Cf. A048793, A051185, A305843, A317752, A317755, A317757, A319077, A326031, A326910, A326912.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[0,100],#==0||Intersection@@bpe/@bpe[#]=={}&]

A337696 Numbers k such that the k-th composition in standard order (A066099) is strict and pairwise non-coprime, meaning the parts are distinct and any two of them have a common divisor > 1.

Original entry on oeis.org

0, 2, 4, 8, 16, 32, 34, 40, 64, 128, 130, 160, 256, 260, 288, 512, 514, 520, 544, 640, 1024, 2048, 2050, 2052, 2056, 2082, 2088, 2176, 2178, 2208, 2304, 2560, 2568, 2592, 4096, 8192, 8194, 8200, 8224, 8226, 8232, 8320, 8704, 8706, 8832, 10240, 10248, 10368

Offset: 1

Gus Wiseman, Oct 06 2020

nonn

Differs from A291165 in having 1090535424, corresponding to the composition (6,10,15).

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence together with the corresponding compositions begins:
       0: ()        512: (10)       2304: (3,9)
       2: (2)       514: (8,2)      2560: (2,10)
       4: (3)       520: (6,4)      2568: (2,6,4)
       8: (4)       544: (4,6)      2592: (2,4,6)
      16: (5)       640: (2,8)      4096: (13)
      32: (6)      1024: (11)       8192: (14)
      34: (4,2)    2048: (12)       8194: (12,2)
      40: (2,4)    2050: (10,2)     8200: (10,4)
      64: (7)      2052: (9,3)      8224: (8,6)
     128: (8)      2056: (8,4)      8226: (8,4,2)
     130: (6,2)    2082: (6,4,2)    8232: (8,2,4)
     160: (2,6)    2088: (6,2,4)    8320: (6,8)
     256: (9)      2176: (4,8)      8704: (4,10)
     260: (6,3)    2178: (4,6,2)    8706: (4,8,2)
     288: (3,6)    2208: (4,2,6)    8832: (4,2,8)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

A318719 gives the Heinz numbers of the unordered version, with non-strict version A337694.
A337667 counts the non-strict version.
A337983 counts these compositions, with unordered version A318717.
A051185 counts intersecting set-systems, with spanning case A305843.
A200976 and A328673 count the unordered non-strict version.
A337462 counts pairwise coprime compositions.
A318749 counts pairwise non-coprime factorizations, with strict case A319786.
All of the following pertain to compositions in standard order (A066099):
- A000120 is length.
- A070939 is sum.
- A124767 counts runs.
- A233564 ranks strict compositions.
- A272919 ranks constant compositions.
- A333219 is Heinz number.
- A333227 ranks pairwise coprime compositions, or A335235 if singletons are considered coprime.
- A333228 ranks compositions whose distinct parts are pairwise coprime.
- A335236 ranks compositions neither a singleton nor pairwise coprime.
- A337561 is the pairwise coprime instead of pairwise non-coprime version, or A337562 if singletons are considered coprime.
- A337666 ranks the non-strict version.
Cf. A082024, A101268, A302797, A305713, A319752, A327040, A327516, A336737, A337599, A337604, A337605.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
stabQ[u_,Q_]:=And@@Not/@Q@@@Tuples[u,2];
Select[Range[0,1000],UnsameQ@@stc[#]&&stabQ[stc[#],CoprimeQ]&]

Intersection of A337666 and A233564.

A319784 Number of non-isomorphic intersecting T_0 set systems of weight n.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 3, 5, 7, 14, 25

Offset: 0

Gus Wiseman, Sep 27 2018

A multiset partition is intersecting if no two parts are disjoint. The weight of a multiset partition is the sum of sizes of its parts. The dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}. The T_0 condition means the dual is strict.

			Non-isomorphic representatives of the a(1) = 1 through a(8) = 7 multiset partitions:
1: {{1}}
3: {{2},{1,2}}
4: {{1,3},{2,3}}
5: {{3},{1,3},{2,3}}
6: {{3},{2,3},{1,2,3}}
   {{1,2},{1,3},{2,3}}
   {{1,4},{2,4},{3,4}}
7: {{4},{1,3,4},{2,3,4}}
   {{1,3},{1,4},{2,3,4}}
   {{1,3},{2,3},{1,2,3}}
   {{1,4},{3,4},{2,3,4}}
   {{4},{1,4},{2,4},{3,4}}
8: {{1,5},{2,4,5},{3,4,5}}
   {{2,4},{3,4},{1,2,3,4}}
   {{2,4},{1,2,5},{3,4,5}}
   {{2,4},{1,3,4},{2,3,4}}
   {{3},{1,3},{2,3},{1,2,3}}
   {{4},{1,4},{3,4},{2,3,4}}
   {{1,5},{2,5},{3,5},{4,5}}

Cf. A007716, A049311, A283877, A305843, A305854, A306006, A316980, A317752.

Cf. A319755, A319759, A319760, A319765, A319779, A319787, A319782, A319789.

A327061 BII-numbers of pairwise intersecting set-systems where every two covered vertices appear together in some edge (cointersecting).

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 8, 16, 17, 24, 32, 34, 40, 52, 64, 65, 66, 68, 69, 70, 72, 80, 81, 84, 85, 88, 96, 98, 100, 102, 104, 112, 116, 120, 128, 256, 257, 384, 512, 514, 640, 772, 1024, 1025, 1026, 1028, 1029, 1030, 1152, 1280, 1281, 1284, 1285, 1408, 1536, 1538

Offset: 1

Gus Wiseman, Aug 18 2019

nonn

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. This sequence gives all BII-numbers (defined below) of pairwise intersecting set-systems whose dual is also pairwise intersecting.

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.

			The sequence of all pairwise intersecting, cointersecting set-systems together with their BII-numbers begins:
   0: {}
   1: {{1}}
   2: {{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
  16: {{1,3}}
  17: {{1},{1,3}}
  24: {{3},{1,3}}
  32: {{2,3}}
  34: {{2},{2,3}}
  40: {{3},{2,3}}
  52: {{1,2},{1,3},{2,3}}
  64: {{1,2,3}}
  65: {{1},{1,2,3}}
  66: {{2},{1,2,3}}
  68: {{1,2},{1,2,3}}
  69: {{1},{1,2},{1,2,3}}
  70: {{2},{1,2},{1,2,3}}

The unlabeled multiset partition version is A319765.
Equals the intersection of A326853 and A326910.
The T_0 version is A326854.
These set-systems are counted by A327037 (covering) and A327038 (not covering).
Cf. A029931, A048793, A051185, A305843, A319774, A326031, A327039, A327040, A327041, A327057.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[0,100],stableQ[bpe/@bpe[#],Intersection[#1,#2]=={}&]&&stableQ[dual[bpe/@bpe[#]],Intersection[#1,#2]=={}&]&]

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

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jul 03 2019

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.

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

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.

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

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

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

cp's OEIS Frontend

A305855 Number of unlabeled spanning intersecting antichains on n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A305856 Number of unlabeled intersecting set-systems on up to n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A305935 Number of labeled spanning intersecting set-systems on n vertices with no singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A306000 Number of labeled intersecting set-systems with no singletons covering some subset of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A326372 Number of intersecting antichains of (possibly empty) subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A326911 BII-numbers of set-systems with empty intersection.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A337696 Numbers k such that the k-th composition in standard order (A066099) is strict and pairwise non-coprime, meaning the parts are distinct and any two of them have a common divisor > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A319784 Number of non-isomorphic intersecting T_0 set systems of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A327061 BII-numbers of pairwise intersecting set-systems where every two covered vertices appear together in some edge (cointersecting).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica