

A114302


Number of "sweet" Boolean functions of n variables.


3




OFFSET

0,1


COMMENTS

A sweet Boolean function is a monotone function whose BDD (binary decision diagram) is the same as the ZDD (zerosuppressed 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,...n1}, 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.


REFERENCES

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


LINKS

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


EXAMPLE

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.


CROSSREFS

Cf. A114303, A114492, A114572.
Sequence in context: A072241 A093468 A185625 * A000304 A000614 A233239
Adjacent sequences: A114299 A114300 A114301 * A114303 A114304 A114305


KEYWORD

nonn,more


AUTHOR

Don Knuth, Aug 16 2008


STATUS

approved



