login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A114302 Number of "sweet" Boolean functions of n variables. 3
2, 3, 6, 18, 106, 2102, 456774, 7108935325 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

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.

REFERENCES

Donald E. Knuth, The Art of Computer Programming, Vol. 4, fascicle 1, section 7.1.4, p. 117, Addison-Wesley, 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 16 14:39 EDT 2021. Contains 343949 sequences. (Running on oeis4.)