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.
a(n) = A111403(n) / 2. - Tilman Piesk, Oct 4 2024
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
KEYWORD
nonn
AUTHOR
STATUS
approved