A005609 Number of Boolean functions realized by cascades of n gates. (Formerly M5333)

64, 1744, 48784, 1365904, 38245264, 1070867344, 29984285584, 839559996304, 23507679896464, 658215037100944, 18430021038826384, 516040589087138704, 14449136494439883664, 404575821844316742544, 11328123011640868791184

Offset

1,1

References

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

Links

Table of n, a(n) for n=1..15.

J. T. Butler, Fanout-free networks of multivalued gates, Proc. Internat. Symposium Multiple-Valued Logic, Charlotte, NC, 1977, IEEE Press, NY (1977), 39-46. (Annotated scanned copy)

J. T. Butler, Letter to N. J. A. Sloane, Dec. 1978.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

Index entries for sequences related to Boolean functions

Index entries for linear recurrences with constant coefficients, signature (29, -28).

Formula

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

a(1)=64, a(2)=1744, a(n) = 29*a(n-1) - 28*a(n-2). - Harvey P. Dale, Nov 19 2011

a(n) = N(n,2,3) where N(n,s,r) is defined in A005608. - Sean A. Irvine, Jul 13 2016

Maple

A005609:=-16*(-4+7*z)/(28*z-1)/(z-1); # conjectured by Simon Plouffe in his 1992 dissertation

Mathematica

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 *)

Crossrefs

Cf. A005608, A005618.

Sequence in context: A234240 A017115 A269203 * A065788 A264275 A283689

Adjacent sequences: A005606 A005607 A005608 * A005610 A005611 A005612

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved