A365073 - OEIS

%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