|
Search: id:A131673
|
|
|
| A131673 |
|
Size of the largest BDD of symmetric Boolean functions of n variables when the sink nodes are counted. |
|
+0
2
|
|
| 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; listen)
|
|
|
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 (rgwv(AT)rgwv.com), Sep 16 2007 *)
|
|
CROSSREFS
|
See A131674 for another version.
Sequence in context: A112509 A054040 A011848 this_sequence A151945 A140261 A015827
Adjacent sequences: A131670 A131671 A131672 this_sequence A131674 A131675 A131676
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
D. E. Knuth, Sep 06 2007
|
|
|
Search completed in 0.002 seconds
|
