A114303 -id:A114303 - cp's OEIS frontend

A114572 Number of "ultrasweet" Boolean functions of n variables which depend on all the variables.

2, 1, 2, 6, 27, 185, 2135, 55129

Offset: 0

Don Knuth, Aug 17 2008, Oct 14 2008

nonn

Inverse binomial transform of A114491.
This sequence enumerates a certain type of matroid, except for the first entry (which is 2 instead of 1). If the first entry is changed from 2 to 1, giving A118085, this enumerates "combinatorial geometries" on n labeled points.
These are matroids in which no element has rank 0; equivalently, all one-element sets are independent; equivalently, the closure of the empty set is empty.
These are called "simple matroids" in A002773. So A118085 is the "labeled" equivalent of that sequence, which counts unlabeled points.

			For all n>1, a function like "x2" is counted in A114491 but not in the present sequence.

Cf. A114302, A114303, A114491, A118085, A002773.

A114302 Number of "sweet" Boolean functions of n variables.

Original entry on oeis.org

2, 3, 6, 18, 106, 2102, 456774, 7108935325

Offset: 0

Don Knuth, Aug 16 2008

A sweet Boolean function is a monotone function whose BDD (binary decision diagram) is the same as the ZDD (zero-suppressed decision diagram) for its prime implicants (aka minimal solutions).
Equivalently, this is the number of sweet antichains contained in {1,...,n}. (Also called sweet clutters.) A sweet antichain whose largest element is n is a family of subsets A \cup (n\cup B) where A and B are sweet antichains in {1,...n-1}, B is nonempty and every element of A properly contains some element of B.
The property of being "sweet" depends on the order of the variables - compare A114491.

			All six of the antichains in {1,2} are sweet. They are emptyset, {emptyset}, {{1}}, {{2}}, {{1,2}} and {{1},{2}}.
Only 18 of the 20 antichains in {1,2,3} are sweet. The nonsweet ones are {{1,3},{2}} and {{1},{2,3}}. Because, in the latter case, A={1} and B={2}. However, {{1,2},{3}} is sweet because A={{1,2}} and B={emptyset}.
Some of the most interesting members of this apparently new family of Boolean functions are the connectedness functions, defined on the edges of any graph. The function f=[these arcs give a connected subgraph] is sweet, under any ordering of the arcs. Threshold functions [x_1+...+x_n >= k] are sweet too.
Also the conjunction of sweet functions on disjoint sets of variables is sweet.

Donald E. Knuth, The Art of Computer Programming, Vol. 4, fascicle 1, section 7.1.4, p. 117, Addison-Wesley, 2009.

Cf. A114303, A114492, A114572.

A114491 Number of "ultrasweet" Boolean functions of n variables.

Original entry on oeis.org

2, 3, 6, 17, 69, 407, 3808, 75165, 10607541

Offset: 0

Don Knuth, Aug 17 2008, Oct 14 2008

nonn

A Boolean function is ultrasweet if it is sweet (see A114302) under all permutations of the variables.

Two students, Shaddin Dughmi and Ian Post, have identified these functions as precisely the monotone Boolean functions whose prime implicants are the bases of a matroid, together with the constant function 0. This explains why a(n) = A058673(n) + 1.

			For all n>1, a function like "x2" is counted in the present sequence but not in A114572.

Cf. A114302, A114303, A114572, A058673.

cp's OEIS Frontend

A114572 Number of "ultrasweet" Boolean functions of n variables which depend on all the variables.

Views

Author

Keywords

Comments

Examples

Crossrefs

A114302 Number of "sweet" Boolean functions of n variables.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A114491 Number of "ultrasweet" Boolean functions of n variables.

Views

Author

Keywords

Comments

Examples

Crossrefs