|
%I M1895 #56 May 02 2023 14:41:29
%S 2,8,64,736,10624,183936,3715072,85755392,2226939904,64255903744,
%T 2039436820480,70614849282048,2648768014680064,106998205418995712,
%U 4630973410260287488,213794635951073787904,10486975675879356104704
%N Number of Boolean functions of n variables that are variously called "unate cascades" or "1-decision list functions" or "read-once threshold functions".
%C Several other characterizations are given in the paper by Eitel et al.
%C 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.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Herman Jamke and Robert Israel, <a href="/A005612/b005612.txt">Table of n, a(n) for n = 1..350</a> (n = 1..22 from Herman Jamke)
%H E. A. Bender and J. T. Butler, <a href="http://dx.doi.org/10.1109/TC.1978.1675021">Asymptotic approximations for the number of fanout-free functions</a>, IEEE Trans. Computers, 27 (1978), 1180-1183. (<a href="/A005612/a005612.pdf">Annotated scanned copy</a>)
%H Aniruddha Biswas and Palash Sarkar, <a href="https://arxiv.org/abs/2304.14069">Counting unate and balanced monotone Boolean functions</a>, arXiv:2304.14069 [math.CO], 2023.
%H J. T. Butler, <a href="/A005607/a005607_1.pdf">Letter to N. J. A. Sloane, Dec. 1978</a>.
%H Thomas Eiter, Toshihide Ibaraki and Kazuhisa Makino, <a href="http://dx.doi.org/10.1016/S0304-3975(01)00003-2">Decision lists and related Boolean functions</a>, Theoretical Computer Science 270 (2002), 493-524.
%H A. S. Jarraha, B. Raposab and R. Laubenbachera, <a href="http://arXiv.org/abs/q-bio/0606013.pdf">Nested canalyzing, unate cascade and polynomial functions</a>, Physica D: Nonlinear Phenomena Volume 233, Issue 2, 15 September 2007, 167-174.
%H T. Sasao and K. Kinoshita, <a href="http://dx.doi.org/10.1109/TC.1979.1675227">On the Number of Fanout-Free Functions and Unate Cascade Functions</a>, IEEE Transactions on Computers, Volume C-28, Issue 1 (1979), 66-72.
%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%F 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).
%F 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.
%F a(n) ~ n! * (1 - log(2)) * 2^n / (log(2))^(n+1). - _Vaclav Kotesovec_, Nov 27 2017
%p egf:= (2-4*x)/(2-exp(2*x))+2*x-2:
%p S:=series(egf,x,31):
%p seq(j! *coeff(S,x,j), j=1..30); # _Robert Israel_, Jul 07 2015
%t 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 *)
%o (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
%Y See also sequence A005840, which is A005612 divided by 2^n. These are the monotone functions of the kind enumerated in the present sequence.
%K nonn,easy
%O 1,1
%A _N. J. A. Sloane_
%E Better description, comments, formulas and a new reference from _Don Knuth_, Sep 22 2007
%E More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008
|
