A365322 Number of subsets of {1..n} that cannot be linearly combined using positive coefficients to obtain n.

0, 1, 2, 5, 11, 26, 54, 116, 238, 490, 994, 2011, 4045, 8131, 16305, 32672, 65412, 130924, 261958, 524066, 1048301, 2096826, 4193904, 8388135, 16776641, 33553759, 67108053, 134216782, 268434324, 536869595, 1073740266, 2147481835, 4294965158, 8589932129

Offset: 0

Author

Gus Wiseman, Sep 04 2023

Keywords

• nonn

Comments

We consider (for example) that 2x + y + 3z is a positive linear combination of (x,y,z), but 2x + y is not, as the coefficient of z is 0.

Examples

			The set {1,3} has 4 = 1 + 3 so is not counted under a(4). However, 3 cannot be written as a linear combination of {1,3} using all positive coefficients, so it is counted under a(3).
The a(1) = 1 through a(4) = 11 subsets:
  {}  {}     {}       {}
      {1,2}  {2}      {3}
             {1,3}    {1,4}
             {2,3}    {2,3}
             {1,2,3}  {2,4}
                      {3,4}
                      {1,2,3}
                      {1,2,4}
                      {1,3,4}
                      {2,3,4}
                      {1,2,3,4}
		

Links

• Steven R. Finch, Monoids of natural numbers, March 17, 2009.

Crossrefs

The complement is counted by A088314.

The version for strict partitions is A088528.

The nonnegative complement is counted by A365073, without n A365542.

The binary complement is A365315, nonnegative A365314.

The binary version is A365321, nonnegative A365320.

For nonnegative coefficients we have A365380.

A085489 and A364755 count subsets without the sum of two distinct elements.

A124506 appears to count combination-free subsets, differences of A326083.

A179822 counts sum-closed subsets, first differences of A326080.

A364350 counts combination-free strict partitions, non-strict A364915.

A365046 counts combination-full subsets, first differences of A364914.

Cf. A070880, A088809, A093971, A151897, A326020, A364272, A364839, A365043, A365381.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, {{}}, `if`(i<1, {},
      {b(n, i-1)[], seq(map(x->{x[], i}, b(n-i*j, i-1))[], j=1..n/i)}))
    end:
a:= n-> 2^n-nops(b(n$2)):
seq(a(n), n=0..33);  # Alois P. Heinz, Sep 04 2023

Mathematica

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

Python

from sympy.utilities.iterables import partitions
def A365322(n): return (1<Chai Wah Wu, Sep 14 2023

Formula

a(n) = 2^n - A088314(n).

a(n) = A070880(n) + 2^(n-1) for n>=1.

Extensions

More terms from Alois P. Heinz, Sep 04 2023