|
%I #6 Aug 08 2015 23:56:27
%S 1,3,5,7,10,14,19,25,31,38,46,55,65,76,88,101,115,129,144,160,177,195,
%T 214,234,255,277,300,324,349,375,402,430,459,489,519,550,582,615,649,
%U 684,720,757,795,834,874,915,957,1000,1044,1089,1135,1182,1230,1279,1329,1380,1432
%N Size of the largest BDD of symmetric Boolean functions of n variables when the sink nodes are counted.
%D Mark Heap, On the exact ordered binary decision diagram size of totally symmetric functions, Journal of Electronic Testing 4 (1993), 191-195.
%D Ingo Wegener, Optimal decision trees and one-time-only branching programs for symmetric Boolean functions, Information and Control 62 (1984), 129-143.
%F a(0) = 1; for n>0, a(n) = 2 + sum_{k=1..n} min(k,2^{n+2-k}-2).
%F 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).
%t f[0] = 1; f[n_] := 2 + Sum[Min[k, 2^{n + 2 - k} - 2], {k, n}]; Table[f@n, {n, 0, 56}] (* or *)
%t 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 *)
%Y See A131674 for another version.
%K nonn,easy
%O 0,2
%A _Don Knuth_, Sep 06 2007
|
