# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a040996
Showing 1-1 of 1

%I A040996 #63 Jun 27 2025 18:15:13
%S A040996 1,6,120,32640,2147450880,9223372034707292160,
%T A040996 170141183460469231722463931679029329920,
%U A040996 57896044618658097711785492504343953926464851149359812787997104700240680714240
%N A040996 Maximum number of distinct functions at the bottom of a Boolean (or Binary) Decision Diagram (or BDD) with negation by pointer complementation.
%C A040996 At 0, the last variable, the only choice is (t, f) because the first entry is always uncomplemented and the 2nd must be different.
%C A040996 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.
%C A040996 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.
%C A040996 From _Luis H. Gallardo_, Nov 18 2021: (Start)
%C A040996 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).
%C A040996 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)
%H A040996 Vincenzo Librandi, <a href="/A040996/b040996.txt">Table of n, a(n) for n = 0..12</a>
%H A040996 Cezar Campeanu, Nelma Moreira, and Rogerio Reis, <a href="https://www.dcc.fc.up.pt/Pubs/TR11/dcc-2011-07.pdf">Expected Compression Ratio for DFCA: experimental average case analysis</a>, Technical Report Series: DCC-2011-07, December 2011, Departamento de Ciencia de Computadores, Universidade do Porto.
%H A040996 Dagstuhl Seminar Design & Test, <a href="https://web.archive.org/web/20031202020741/http://www.bdd-portal.org/dagstuhl-ppt/dagstuhl-talks.htm">More about BDD's</a>
%H A040996 Alan J. Hu, David L. Dill, Andreas J. Drexler and C. Han Yang, <a href="https://doi.org/10.1007/3-540-56496-9_8">Higher-level specification and verification with BDDs</a>, In: von Bochmann G., Probst D.K. (eds) Computer Aided Verification. CAV 1992. Lecture Notes in Computer Science (1993), vol 663. Springer, Berlin, Heidelberg.
%F A040996 a(n) = (S(n-1) + 1) * (2*S(n-1) + 1) where S(n-1) = Sum_{k<n} a(k).
%F A040996 a(n) is the (2^(2^n)-1)-th triangular number; i.e., a(n) = 2^(2^n)*(2^(2^n)-1)/2.
%F A040996 a(n) = A111403(n) / 2. - _Tilman Piesk_, Oct 04 2024
%p A040996 a(n) = subs(t=2,modp(expand(t^(2^n-1)*(t+1)^(2^n-1)),2)); # _Luis H. Gallardo_, Nov 18 2021
%t A040996 f[x_]:=Module[{c=2^(2^x)},(c(c-1))/2]; Array[f,10,0] (* _Harvey P. Dale_, Sep 29 2011 *)
%o A040996 (PARI) a(n)=if(n<=0,n==0,2^(2^n)*(2^(2^n)-1)/2)
%o A040996 (Magma) [2^(2^n)*(2^(2^n)-1)/2: n in [0..10]]; // _Vincenzo Librandi_, Sep 30 2011
%Y A040996 Subsequence of A000217. Half of A111403.
%K A040996 nonn
%O A040996 0,2
%A A040996 _R. H. Hardin_

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE