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,3

Links

Andrew Howroyd, Table of n, a(n) for n = 0..100

S. R. Finch, Monoids of natural numbers, March 17, 2009.

Example

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}

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}]

Prog

(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<<n)
} \\ Andrew Howroyd, Sep 04 2023

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.

Sequence in context: A277954 A279986 A279474 * A282756 A030012 A001970

Adjacent sequences: A365070 A365071 A365072 * A365074 A365075 A365076

Keyword

nonn

Author

Gus Wiseman, Sep 01 2023

Extensions

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

Status

approved