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

1, 1, 3, 6, 14, 26, 60, 112, 244, 480, 992, 1944, 4048, 7936, 16176, 32320, 65088, 129504, 261248, 520448, 1046208, 2090240, 4186624, 8365696, 16766464, 33503744, 67064064, 134113280, 268347392, 536546816, 1073575936, 2146703360, 4294425600, 8588476416, 17178349568

Offset: 0

Author

Gus Wiseman, Sep 01 2023

Keywords

• nonn

Examples

			The subset {2,3,6} has 7 = 2*2 + 1*3 + 0*6 so is counted under a(7).
The a(1) = 1 through a(4) = 14 subsets:
  {1}  {1}    {1}      {1}
       {2}    {3}      {2}
       {1,2}  {1,2}    {4}
              {1,3}    {1,2}
              {2,3}    {1,3}
              {1,2,3}  {1,4}
                       {2,3}
                       {2,4}
                       {3,4}
                       {1,2,3}
                       {1,2,4}
                       {1,3,4}
                       {2,3,4}
                       {1,2,3,4}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..100
• Steven R. Finch, Monoids of natural numbers, March 17, 2009.

Crossrefs

The case of positive coefficients is A088314.

The case of subsets containing n is A131577.

The binary version is A365314, positive A365315.

The binary complement is A365320, positive A365321.

The positive complement is counted by A365322.

A version for partitions is A365379, strict A365311.

The complement is counted by A365380.

The case of subsets without n is A365542.

A326083 and A124506 appear to count combination-free subsets.

A179822 and A326080 count sum-closed subsets.

A364350 counts combination-free strict partitions.

A364914 and A365046 count combination-full subsets.

Cf. A007865, A088809, A093971, A151897, A237668, A308546, A326020, A364534, A364839, A365043, A365381.

Programs

Mathematica

combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],combs[n,#]!={}&]],{n,0,5}]

PARI

a(n)={
  my(comb(k,b)=while(b>>k, b=bitor(b, b>>k); k*=2); b);
  my(recurse(k,b)=
    if(bittest(b,0), 2^(n+1-k),
    if(2*k>n, 2^(n+1-k) - 2^sum(j=k, n, !bittest(b,j)),
    self()(k+1, b) + self()(k+1, comb(k,b)) )));
  recurse(1, 1<Andrew Howroyd, Sep 04 2023

Extensions

Terms a(12) and beyond from Andrew Howroyd, Sep 04 2023