A365322 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

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.

LINKS

Table of n, a(n) for n=0..33.

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

FORMULA

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

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

EXAMPLE

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}

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

PROG

(Python)

from sympy.utilities.iterables import partitions

def A365322(n): return (1<<n)-len({tuple(sorted(set(p))) for p in partitions(n)}) # Chai Wah Wu, Sep 14 2023

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.

Sequence in context: A266879 A104237 A085945 * A371662 A005469 A218575

Adjacent sequences: A365319 A365320 A365321 * A365323 A365324 A365325

KEYWORD

nonn

AUTHOR

Gus Wiseman, Sep 04 2023

EXTENSIONS

More terms from Alois P. Heinz, Sep 04 2023

STATUS

approved