cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A118085 Alternative version of A114572 with a(0) = 1 instead of 2.

Original entry on oeis.org

1, 1, 2, 6, 27, 185, 2135, 55129
Offset: 0

Views

Author

Don Knuth, Aug 17 2008, Oct 14 2008

Keywords

Comments

A114572 is the main entry for this sequence.

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

Original entry on oeis.org

2, 3, 6, 18, 106, 2102, 456774, 7108935325
Offset: 0

Views

Author

Don Knuth, Aug 16 2008

Keywords

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.

Examples

			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.

References

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

Crossrefs

Cf. A114303, A114492, A114572.

A114303 Number of sweet Boolean functions of n variables that depend on all the variables.

Original entry on oeis.org

2, 1, 2, 7, 60, 1705, 445466, 7105778862
Offset: 0

Views

Author

Don Knuth, Aug 16 2008

Keywords

Crossrefs

Cf. A114302, A114492, A114572.

Formula

Inverse binomial transform of A114302.

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

Views

Author

Don Knuth, Aug 17 2008, Oct 14 2008

Keywords

Comments

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.

Examples

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

Crossrefs

Cf. A114302, A114303, A114572, A058673.
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.