login
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
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.
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
KEYWORD
nonn,easy
AUTHOR
Don Knuth, Sep 06 2007
STATUS
approved