This site is supported by donations to The OEIS Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A131673 Size of the largest BDD of symmetric Boolean functions of n variables when the sink nodes are counted. 1
 1, 3, 5, 7, 10, 14, 19, 25, 31, 38, 46, 55, 65, 76, 88, 101, 115, 129, 144, 160, 177, 195, 214, 234, 255, 277, 300, 324, 349, 375, 402, 430, 459, 489, 519, 550, 582, 615, 649, 684, 720, 757, 795, 834, 874, 915, 957, 1000, 1044, 1089, 1135, 1182, 1230, 1279, 1329, 1380, 1432 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 REFERENCES Mark Heap, On the exact ordered binary decision diagram size of totally symmetric functions, Journal of Electronic Testing 4 (1993), 191-195. Ingo Wegener, Optimal decision trees and one-time-only branching programs for symmetric Boolean functions, Information and Control 62 (1984), 129-143. LINKS FORMULA a(0) = 1; for n>0, a(n) = 2 + sum_{k=1..n} min(k,2^{n+2-k}-2). Also a(n) = binomial(n+2-b_n, 2)+2(2^{b_n}-b_n), where b_n = lambda(n+4-lambda(n+4)) and lambda(n) = floor(log_2 n). MATHEMATICA f[0] = 1; f[n_] := 2 + Sum[Min[k, 2^{n + 2 - k} - 2], {k, n}]; Table[f@n, {n, 0, 56}] (* or *) flg[n_] := Floor@Log[2, n + 4 - Floor@Log[2, n + 4]]; f[0] = 1; f[n_] := Binomial[n + 2 - flg@n, 2] + 2 (2^flg@n - flg@n); Table[ f@n, {n, 0, 56}] (* Robert G. Wilson v, Sep 16 2007 *) CROSSREFS See A131674 for another version. Sequence in context: A194166 A054040 A011848 * A151945 A140261 A310021 Adjacent sequences:  A131670 A131671 A131672 * A131674 A131675 A131676 KEYWORD nonn,easy AUTHOR Don Knuth, Sep 06 2007 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 17 18:48 EST 2019. Contains 319251 sequences. (Running on oeis4.)