login
A365322
Number of subsets of {1..n} that cannot be linearly combined using positive coefficients to obtain n.
12
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,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
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.
Sequence in context: A266879 A104237 A085945 * A371662 A005469 A218575
KEYWORD
nonn
AUTHOR
Gus Wiseman, Sep 04 2023
EXTENSIONS
More terms from Alois P. Heinz, Sep 04 2023
STATUS
approved