A040996 Maximum number of distinct functions at the bottom of a Boolean (or Binary) Decision Diagram (or BDD) with negation by pointer complementation.

1, 6, 120, 32640, 2147450880, 9223372034707292160, 170141183460469231722463931679029329920, 57896044618658097711785492504343953926464851149359812787997104700240680714240

Offset

0,2

Comments

At 0, the last variable, the only choice is (t, f) because the first entry is always uncomplemented and the 2nd must be different.

At level 1, the 2nd-to-last variable, the first entry is either t or a pointer to a following level (0) and the 2nd entry is either of these or its negation, except it may not equal the first entry.

At level n, the n-th-to-last variable, the first entry is either t or a pointer to one of the following levels' functions and the second entry is any of these or its negation, but not equal to the first entry.

From Luis H. Gallardo, Nov 18 2021: (Start)

Another description of a(n) follows: let TP(n) = t^(2^n-1)*(t+1)^(2^n-1) in the ring F_2[t]. Expand TP(n) as a sum of monomials c*t^k in F_2[t], with c equal 0 or 1. Lift TP(n) to LTP(n) in the ring Z[t], i.e., consider the coefficients c of TP(n) to be integers in LTP(n), instead of elements of F_2. Finally, substitute t by 2 in LTP(n). We get: a(n) = LTP(n).

Example: a(3) = subs(t=2, TP(3)) = 32640, where TP(3) = t^14 + t^13 + t^12 + t^10 + t^9 + t^8 + t^7 = t^7*(t+1)^7 in F_2[t]. (End)

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..12

Cezar Campeanu, Nelma Moreira, and Rogerio Reis, Expected Compression Ratio for DFCA: experimental average case analysis, Technical Report Series: DCC-2011-07, December 2011, Departamento de Ciencia de Computadores, Universidade do Porto.

Dagstuhl Seminar Design & Test, More about BDD's

Alan J. Hu, David L. Dill, Andreas J. Drexler and C. Han Yang, Higher-level specification and verification with BDDs, In: von Bochmann G., Probst D.K. (eds) Computer Aided Verification. CAV 1992. Lecture Notes in Computer Science (1993), vol 663. Springer, Berlin, Heidelberg.

Formula

a(n) = (S(n-1) + 1) * (2*S(n-1) + 1) where S(n-1) = Sum_{k<n} a(k).

a(n) is the (2^(2^n)-1)-th triangular number; i.e., a(n) = 2^(2^n)*(2^(2^n)-1)/2.

Maple

a(n) = subs(t=2, modp(expand(t^(2^n-1)*(t+1)^(2^n-1)), 2)); # Luis H. Gallardo, Nov 18 2021

Mathematica

f[x_]:=Module[{c=2^(2^x)}, (c(c-1))/2]; Array[f, 10, 0] (* Harvey P. Dale, Sep 29 2011 *)

Prog

(PARI) a(n)=if(n<=0, n==0, 2^(2^n)*(2^(2^n)-1)/2)
(Magma) [2^(2^n)*(2^(2^n)-1)/2: n in [0..10]]; // Vincenzo Librandi, Sep 30 2011

Crossrefs

Subsequence of A000217.

Sequence in context: A023199 A355757 A007539 * A110442 A371206 A137149

Adjacent sequences: A040993 A040994 A040995 * A040997 A040998 A040999

Keyword

nonn

Author

R. H. Hardin

Status

approved