A131674 Size of the largest BDD of symmetric Boolean functions of n variables when the sink nodes are not counted.

0, 1, 3, 5, 8, 12, 17, 23, 29, 36, 44, 53, 63, 74, 86, 99, 113, 127, 142, 158, 175, 193, 212, 232, 253, 275, 298, 322, 347, 373, 400, 428, 457, 487, 517, 548, 580, 613, 647, 682, 718, 755, 793, 832, 872, 913, 955, 998, 1042, 1087, 1133, 1180, 1228, 1277, 1327, 1378, 1430, 1483

Offset

0,3

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

Table of n, a(n) for n=0..57.

Formula

a(n) = sum_{k=1..n} min(k,2^{n+2-k}-2).

Mathematica

f[n_] := Sum[ Min[k, 2^{n + 2 - k} - 2], {k, n}]; Table[ f@n, {n, 0, 57}] (* Robert G. Wilson v, Sep 16 2007 *)

Crossrefs

See A131673 for another version.

Sequence in context: A014811 A282513 A241567 * A095173 A002579 A023544

Adjacent sequences: A131671 A131672 A131673 * A131675 A131676 A131677

Keyword

nonn,easy

Author

Don Knuth, Sep 06 2007

Status

approved