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

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

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

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

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 A340247

Adjacent sequences: A131670 A131671 A131672 * A131674 A131675 A131676

Keyword

nonn,easy

Author

Don Knuth, Sep 06 2007

Status

approved