login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)
6
2, 8, 64, 736, 10624, 183936, 3715072, 85755392, 2226939904, 64255903744, 2039436820480, 70614849282048, 2648768014680064, 106998205418995712, 4630973410260287488, 213794635951073787904, 10486975675879356104704 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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).

LINKS

Herman Jamke and Robert Israel, Table of n, a(n) for n = 1..350 (n = 1..22 from Herman Jamke)

E. A. Bender and J. T. Butler, Asymptotic approximations for the number of fanout-free functions, IEEE Trans. Computers, 27 (1978), 1180-1183. (Annotated scanned copy)

J. T. Butler, Letter to N. J. A. Sloane, Dec. 1978.

Thomas Eiter, Toshihide Ibaraki and Kazuhisa Makino, Decision lists and related Boolean functions, Theoretical Computer Science 270 (2002), 493-524.

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, 167-174.

T. Sasao, K. Kinoshita, On the Number of Fanout-Free Functions and Unate Cascade Functions, IEEE Transactions on Computers, Volume C-28, Issue 1 (1979), 66-72.

Index entries for sequences related to Boolean functions

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 e.g.f. 2(x+e^{-2x}-1)/(1-2e^{-2x}), which can easily be simplified to (2-4x)/(2-e^(2x))+2x-2.

a(n) ~ n! * (1 - log(2)) * 2^n / (log(2))^(n+1). - Vaclav Kotesovec, Nov 27 2017

MAPLE

egf:= (2-4*x)/(2-exp(2*x))+2*x-2:

S:=series(egf, x, 31):

seq(j! *coeff(S, x, j), j=1..30); # Robert Israel, Jul 07 2015

MATHEMATICA

p[0] = 1; p[n_] := p[n] = Sum[Binomial[n, k]*p[n-k], {k, 1, n}]; a[n_] := a[n] = 2^(n+1)*(p[n] - n*p[n-1]); a[1] = 2; Table[a[n], {n, 1, 17}] (* Jean-Fran├žois Alcover, Aug 01 2011, after formula *)

PROG

(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: A059862 A268666 A193549 * A136282 A092934 A224801

Adjacent sequences:  A005609 A005610 A005611 * A005613 A005614 A005615

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

Better description, comments, formulas and a new reference from Don Knuth, Sep 22 2007

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 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 April 23 14:15 EDT 2019. Contains 322386 sequences. (Running on oeis4.)