|
%I #42 Sep 17 2022 19:02:40
%S 0,0,1,2,4,10,20,44,93,198,414,864,1788,3687,7541,15382,31200,63191,
%T 127482,256857,516404,1037104,2080357,4170283,8354078,16728270
%N Number of dependent sets with largest element n.
%C Let S be a set of positive integers. If S can be divided into two subsets which have equal sums, then S is said to be a dependent set.
%D J. Bourgain, Λ_p-sets in analysis: results, problems and related aspects. Handbook of the geometry of Banach spaces, Vol. I,195-232, North-Holland, Amsterdam, 2001.
%e Here are the dependent sets counted by a(6): {1,5,6}, {2,4,6}, {1,2,3,6}, {1,2,5,6}, {1,3,4,6}, {2,3,5,6}, {3,4,5,6}, {1,2,3,4,6}, {1,2,4,5,6}, {2,3,4,5,6}.
%p b:= proc(n, i) option remember; `if`(i<1, `if`(n=0, {0}, {}),
%p `if`(i*(i+1)/2<n, {}, b(n, i-1) union map(p-> p+x^i,
%p b(n+i, i-1) union b(abs(n-i), i-1))))
%p end:
%p a:= n-> nops(b(n, n-1)):
%p seq(a(n), n=1..15); # _Alois P. Heinz_, Nov 24 2013
%t b[n_, i_] := b[n, i] = If[i<1, If[n == 0, {0}, {}], If[i*(i+1)/2 < n, {}, b[n, i-1] ~Union~ Map[Function[p, p+x^i], b[n+i, i-1] ~Union~ b[Abs[n-i], i-1]]]]; a[n_] := Length[b[n, n-1]]; Table[Print[a[n]]; a[n], {n, 1, 24}] (* _Jean-François Alcover_, Mar 04 2014, after _Alois P. Heinz_ *)
%o (PARI) dep(S,k=0)=if(#S<2,return(if(#S,S[1],0)==k)); my(T=S[1..#S-1]);dep(T,abs(k-S[#S]))||dep(T,k+S[#S])
%o a(n)=my(S=[1..n-1]);sum(i=1,2^(n-1)-1,dep(vecextract(S,i),n)) \\ _Charles R Greathouse IV_, Nov 25 2013
%Y Cf. A161943, A232534.
%Y Column k=2 of A248112.
%K nonn,more
%O 1,4
%A _David S. Newman_, Nov 24 2013
%E a(9)-a(24) from _Alois P. Heinz_, Nov 24 2013
%E a(25) from _Alois P. Heinz_, Sep 30 2014
%E a(26) from _Alois P. Heinz_, Sep 17 2022
|
