cp's OEIS Frontend

Unlike the connected case (A057500), these graphs may have more than one cycle; for example, the graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}} has multiple cycles.

From Gus Wiseman, Jul 31 2019: (Start)

If we define a connectedness system to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges, then a(n) is the number of connectedness systems on n vertices without singleton edges. The BII-numbers of these set-systems are given by A326873. The a(3) = 12 connectedness systems without singletons are:

{}

{{1,2}}

{{1,3}}

{{2,3}}

{{1,2,3}}

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

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

{{2,3},{1,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}}

(End)

Previous name was: a(1) = 1; for n > 1, a(n) = number of families of subsets of {1, ..., n} that contain both the universe and the empty set, are closed under union of nondisjoint sets, and contain no singletons.

A connectedness system is (as below) a set of (finite) nonempty sets that is closed under union of nondisjoint sets.

The old definition was: "Number of subsets S of the power set P{1,2,...,n} such that: {1}, {2},..., {n} are all elements of S; {1,2,...n} is an element of S; if X and Y are elements of S and X and Y have a nonempty intersection, then the union of X and Y is an element of S."

Comments on the old definition from Gus Wiseman, Aug 01 2019: (Start)

If this sequence were defined similarly to A326877, we would have a(1) = 0.

We define a connectedness system to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is connected if it is empty or contains an edge with all the vertices. a(n) is the number of connected connectedness systems on n vertices without singletons. For example, the a(3) = 8 connected connectedness systems without singletons are:

{{1,2,3}}

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

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

{{2,3},{1,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}}

(End)

Conjecture concerning the original definition: a(n) is also the number of families of subsets of {1, ..., n} that contain both the universe and the empty set, are closed under intersection and contain no sets of cardinality n-1. - Tian Vlasic, Nov 04 2022. [This was false, as pointed out by Christian Sievers, Oct 20 2023. It is easy to see that for n>1, a(n) is also the number of families of subsets of {1, ..., n} that contain both the universe and the empty set, are closed under union of nondisjoint sets, and contain no singletons; whereas by duality, the sequence suggested in the conjecture is also the number of those families that are also closed under arbitrary union. For details see the Sievers link. - N. J. A. Sloane, Oct 21 2023]

We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is covering if every vertex belongs to some edge.

We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges.

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 enumeration of these set-systems by number of covered vertices is given by A326877.

We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges.