This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005609 Number of Boolean functions realized by cascades of n gates.
(Formerly M5333)

%I M5333

%S 64,1744,48784,1365904,38245264,1070867344,29984285584,839559996304,

%T 23507679896464,658215037100944,18430021038826384,516040589087138704,

%U 14449136494439883664,404575821844316742544,11328123011640868791184

%N Number of Boolean functions realized by cascades of n gates.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H J. T. Butler, <a href="/A005607/a005607.pdf">Fanout-free networks of multivalued gates</a>, Proc. Internat. Symposium Multiple-Valued Logic, Charlotte, NC, 1977, IEEE Press, NY (1977), 39-46. (Annotated scanned copy)

%H J. T. Butler, <a href="/A005607/a005607_1.pdf">Letter to N. J. A. Sloane, Dec. 1978</a>.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 1992.

%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (29, -28).

%F G.f.: (64 - 112 x) / (1 - x) (1 - 28 x).

%F a(1)=64, a(2)=1744, a(n) = 29*a(n-1) - 28*a(n-2). - _Harvey P. Dale_, Nov 19 2011

%F a(n) = N(n,2,3) where N(n,s,r) is defined in A005608. - _Sean A. Irvine_, Jul 13 2016

%p A005609:=-16*(-4+7*z)/(28*z-1)/(z-1); # conjectured by _Simon Plouffe_ in his 1992 dissertation

%t CoefficientList[Series[(64-112 x)/((1-x) (1-28 x)),{x,0,30}],x] (* or *) LinearRecurrence[{29,-28},{64,1744},30] (* _Harvey P. Dale_, Nov 19 2011 *)

%Y Cf. A005608, A005618.

%K nonn,easy

%O 1,1

%A _N. J. A. Sloane_

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 18 12:34 EDT 2019. Contains 322209 sequences. (Running on oeis4.)