cp's OEIS Frontend

A365073 Number of subsets of {1..n} that can be linearly combined using nonnegative coefficients to obtain n.

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