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

Author

R. H. Hardin

Keywords

• nonn

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.

Crossrefs

Subsequence of A000217. Half of A111403.

Programs

Magma

[2^(2^n)*(2^(2^n)-1)/2: n in [0..10]]; // Vincenzo Librandi, Sep 30 2011

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

PARI

a(n)=if(n<=0,n==0,2^(2^n)*(2^(2^n)-1)/2)

Formula

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

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

a(n) = A111403(n) / 2. - Tilman Piesk, Oct 04 2024

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.