%I #17 Sep 10 2023 11:04:53
%S 1,1,3,6,14,26,60,112,244,480,992,1944,4048,7936,16176,32320,65088,
%T 129504,261248,520448,1046208,2090240,4186624,8365696,16766464,
%U 33503744,67064064,134113280,268347392,536546816,1073575936,2146703360,4294425600,8588476416,17178349568
%N Number of subsets of {1..n} that can be linearly combined using nonnegative coefficients to obtain n.
%H Andrew Howroyd, <a href="/A365073/b365073.txt">Table of n, a(n) for n = 0..100</a>
%H S. R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009.
%e The subset {2,3,6} has 7 = 2*2 + 1*3 + 0*6 so is counted under a(7).
%e The a(1) = 1 through a(4) = 14 subsets:
%e {1} {1} {1} {1}
%e {2} {3} {2}
%e {1,2} {1,2} {4}
%e {1,3} {1,2}
%e {2,3} {1,3}
%e {1,2,3} {1,4}
%e {2,3}
%e {2,4}
%e {3,4}
%e {1,2,3}
%e {1,2,4}
%e {1,3,4}
%e {2,3,4}
%e {1,2,3,4}
%t combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
%t Table[Length[Select[Subsets[Range[n]],combs[n,#]!={}&]],{n,0,5}]
%o (PARI)
%o a(n)={
%o my(comb(k,b)=while(b>>k, b=bitor(b, b>>k); k*=2); b);
%o my(recurse(k,b)=
%o if(bittest(b,0), 2^(n+1-k),
%o if(2*k>n, 2^(n+1-k) - 2^sum(j=k, n, !bittest(b,j)),
%o self()(k+1, b) + self()(k+1, comb(k,b)) )));
%o recurse(1, 1<<n)
%o } \\ _Andrew Howroyd_, Sep 04 2023
%Y The case of positive coefficients is A088314.
%Y The case of subsets containing n is A131577.
%Y The binary version is A365314, positive A365315.
%Y The binary complement is A365320, positive A365321.
%Y The positive complement is counted by A365322.
%Y A version for partitions is A365379, strict A365311.
%Y The complement is counted by A365380.
%Y The case of subsets without n is A365542.
%Y A326083 and A124506 appear to count combination-free subsets.
%Y A179822 and A326080 count sum-closed subsets.
%Y A364350 counts combination-free strict partitions.
%Y A364914 and A365046 count combination-full subsets.
%Y Cf. A007865, A088809, A093971, A151897, A237668, A308546, A326020, A364534, A364839, A365043, A365381.
%K nonn
%O 0,3
%A _Gus Wiseman_, Sep 01 2023
%E Terms a(12) and beyond from _Andrew Howroyd_, Sep 04 2023