|
Search: id:A005612
|
|
|
| A005612 |
|
Number of Boolean functions of n variables that are variously called "unate cascades" or "1-decision list functions" or "read-once threshold functions".
(Formerly M1895)
|
|
+0
1
|
|
| 2, 8, 64, 736, 10624, 183936, 3715072, 85755392, 2226939904, 64255903744, 2039436820480, 70614849282048, 2648768014680064, 106998205418995712, 4630973410260287488, 213794635951073787904, 10486975675879356104704
(list; graph; listen)
|
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
Several other characterizations are given in the paper by Eitel et al.
These functions are the Boolean functions with the nice property that all of their projections are "canalizing" or "single-faced": that is, f is constant on half of the n-cube and on the other half it recursively satisfies the same constraint.
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
E. A. Bender and J. T. Butler, Asymptotic approximations for the number of fanout-free functions, IEEE Trans. Computers, 27 (1978), 1180-1183.
Thomas Eiter, Toshihide Ibaraki and Kazuhisa Makino, ``Decision lists and related Boolean functions,'' Theoretical Computer Science 270 (2002), 493-524.
Sasao, T.; Kinoshita, K., On the Number of Fanout-Free Functions and Unate Cascade Functions, IEEE Transactions on Computers, Volume C-28, Issue 1, 1979 Page(s):66 - 72
|
|
LINKS
|
Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008, Table of n, a(n) for n = 1..22
Index entries for sequences related to Boolean functions
A. S. Jarraha, B. Raposab and R. Laubenbachera, Nested canalyzing, unate cascade and polynomial functions, Physica D: Nonlinear Phenomena Volume 233, Issue 2, 15 September 2007, Pages 167-174
|
|
FORMULA
|
When n>1, the number is 2^{n+1}(P_n-nP_{n-1}), where P_n is the number of weak orders (preferential arrangements), sequence A000670. For example, when n=4 we have 736 = 32 times (75 - 4*13).
Bender and Butler give the generating function 2(x+e^{-2x}-1)/(1-2e^{-2x}), which can easily be simplified to (2-4x)/(2-e^(2x))+2x-2.
|
|
PROGRAM
|
(PARI) a(n)=if(n<0, 0, n!*polcoeff(subst((2-4*y)/(2-exp(2*y))+2*y-2, y, x+x*O(x^n)), n)) - Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008
|
|
CROSSREFS
|
See also sequence A005840, which is A005612 divided by 2^n. These are the monotone functions of the kind enumerated in the present sequence.
Sequence in context: A139018 A052707 A059862 this_sequence A136282 A092934 A139679
Adjacent sequences: A005609 A005610 A005611 this_sequence A005613 A005614 A005615
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
Better description, comments, formulae and a new reference from D. E. Knuth, Sep 22 2007
More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008
|
|
|
Search completed in 0.002 seconds
|
