login
This site is supported by donations to The OEIS Foundation.

 

Logo

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

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 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.

License Agreements, Terms of Use, Privacy Policy. .

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