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)
Aniruddha Biswas and Palash Sarkar, Counting unate and balanced monotone Boolean functions, arXiv:2304.14069 [math.CO], 2023.
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 and 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.
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
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