A345677 Total number of nodes of the binary decision diagrams (BDDs) for all Boolean functions of n variables.

2, 8, 56, 1472, 615872, 66741913472, 481633806031213129472, 14977615127386591957251601320841928924672, 8683854397629333456697983324568080952156333564253951567157061992396002450127872

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