login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A345677 Total number of nodes of the binary decision diagrams (BDDs) for all Boolean functions of n variables. 1
2, 8, 56, 1472, 615872, 66741913472, 481633806031213129472, 14977615127386591957251601320841928924672, 8683854397629333456697983324568080952156333564253951567157061992396002450127872 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

REFERENCES

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Addison-Wesley, 2011, Section 7.1.4.

LINKS

Table of n, a(n) for n=0..8.

Wikipedia, Binary decision diagram

FORMULA

a(n) = 2*(2^2^n-1) + Sum_{k=0..n-1} (2^2^(n-k)-2^2^(n-k-1))*(2^2^n-(2^2^(n-k)-1)^2^k).

a(n) < 2^2^n*A327461(n) for n >= 1.

MATHEMATICA

a[n_]:=2(2^2^n-1)+Sum[(2^2^(n-k)-2^2^(n-k-1))*(2^2^n-(2^2^(n-k)-1)^2^k), {k, 0, n-1}]; Array[a, 9, 0] (* Stefano Spezia, Jun 26 2021 *)

CROSSREFS

Cf. A327461, A345678.

Sequence in context: A191713 A191508 A113725 * A256724 A153538 A153566

Adjacent sequences:  A345674 A345675 A345676 * A345678 A345679 A345680

KEYWORD

nonn

AUTHOR

Pontus von Brömssen, Jun 22 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 19 16:39 EDT 2022. Contains 356229 sequences. (Running on oeis4.)