cp's OEIS Frontend

a(2), a(3), a(5) and a(7) are prime; a(11) is not.

Let S be a set of n elements. First we perform a set partition on S. Let SU be the set of all nonempty subsets of S. As is well known, 2^n - 1 is the number of nonempty subsets of a set with n elements (see A000225). That is, 2^n - 1 is the number of elements |SU| of SU. In the second step, we select k elements from SU. We want to know how many different selections are possible. Let W be the resulting set of selections formed from SU. Then the number of elements |W| of W is |W| = Sum_{k=1..2^n-1} binomial(2^n-1,k) = 2^(2^n-1) - 1 = A077585. Example: |W(n)| = a(n=2) = 7, because W = {[[1, 2]], [[1]], [[1, 2], [1]], [[1, 2], [2], [1]], [[1, 2], [2]], [[2], [1]], [[2]]}. - Thomas Wieder, Nov 08 2007

These are so-called double Mersenne numbers, sometimes denoted MM(n) where M = A000225. MM(n) is prime iff M(n) = 2^n-1 is a Mersenne prime exponent (A000043), which isn't possible unless n itself is also in A000043. Primes of this form are called double Mersenne primes MM(p). For all Mersenne exponents between 7 and 61, factors of MM(p) are known. MM(61) is far too large for any currently known primality test, but a distributed search for factors of this and other MM(p) is ongoing, see the doublemersenne.org web site. - M. F. Hasler, Mar 05 2020

This is a strong divisibility sequence, that is, gcd(a(n),a(m)) = a(gcd(n,m)) for n, m >= 1. - Peter Bala, Dec 05 2022

We define a hypergraph to be any finite set of finite nonempty sets. A hypergraph is uniform if all edges have the same size, and regular if all vertices have the same degree. The span of a hypergraph is the union of its edges.

Also the number of 0-1 matrices with n columns, all distinct rows, no zero columns, equal row-sums, and equal column-sums, up to a permutation of the rows.

A set system (set of sets) is an antichain if no element is a subset of any other.

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

Excludes all set-systems with more edges than covered vertices, but this condition is not sufficient.

Same as A059523 except with a(1) = 1 instead of 2.

Alternatively, these are set-systems covering n vertices whose dual is a (strict) antichain. A set-system is a finite set of finite nonempty sets. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. An antichain is a set of sets, none of which is a subset of any other.

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 (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.

In a set-system, the degree of a vertex is the number of edges containing it.

From Gus Wiseman, Jan 02 2024: (Start)

Also the number of n-element sets of finite nonempty subsets of {1..n}, including a unique singleton, such that there is exactly one way to choose a different element from each. For example, the a(0) = 0 through a(3) = 15 set-systems are:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

These set-systems are all connected.

The case of labeled graphs is A000169.

(End)

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

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 counts set-systems that are cointersecting, meaning their dual is pairwise intersecting.

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.