|
| |
|
|
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
|
|
|
|
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):
|
|
|
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.
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
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
|
| |
|
|
