Search: id:A005612
Results 1-1 of 1 results found.

%I A005612 M1895
%S A005612 2,8,64,736,10624,183936,3715072,85755392,2226939904,64255903744,
%T A005612 2039436820480,70614849282048,2648768014680064,106998205418995712,
%U A005612 4630973410260287488,213794635951073787904,10486975675879356104704
%N A005612 Number of Boolean functions of n variables that are variously called 
               "unate cascades" or "1-decision list functions" or "read-once threshold 
               functions".
%C A005612 Several other characterizations are given in the paper by Eitel et al.
%C A005612 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 A005612 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A005612 E. A. Bender and J. T. Butler, Asymptotic approximations for the number 
               of fanout-free functions, IEEE Trans. Computers, 27 (1978), 1180-1183.
%D A005612 Thomas Eiter, Toshihide Ibaraki and Kazuhisa Makino, ``Decision lists 
               and related Boolean functions,'' Theoretical Computer Science 270 
               (2002), 493-524.
%D A005612 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
%H A005612 Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008, <a href="b005612.txt">
               Table of n, a(n) for n = 1..22</a>
%H A005612 <a href="Sindx_Bo.html#Boolean">Index entries for sequences related to 
               Boolean functions</a>
%H A005612 A. S. Jarraha, B. Raposab and R. Laubenbachera, <a href="http://arXiv.org/
               pdf/q-bio/0606013.pdf">Nested canalyzing, unate cascade and polynomial 
               functions</a>, Physica D: Nonlinear Phenomena Volume 233, Issue 2, 
               15 September 2007, Pages 167-174
%F A005612 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 A005612 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.
%o A005612 (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 A005612 See also sequence A005840, which is A005612 divided by 2^n. These are 
               the monotone functions of the kind enumerated in the present sequence.
%Y A005612 Sequence in context: A139018 A052707 A059862 this_sequence A136282 A092934 
               A139679
%Y A005612 Adjacent sequences: A005609 A005610 A005611 this_sequence A005613 A005614 
               A005615
%K A005612 nonn,easy
%O A005612 1,1
%A A005612 N. J. A. Sloane (njas(AT)research.att.com).
%E A005612 Better description, comments, formulae and a new reference from D. E. 
               Knuth, Sep 22 2007
%E A005612 More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008

Search completed in 0.001 seconds