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 positive complement is counted by A365322.
The complement is counted by A365380.
The case of subsets without n is A365542.
A364350 counts combination-free strict partitions.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Sep 01 2023
EXTENSIONS
Terms a(12) and beyond from Andrew Howroyd, Sep 04 2023
STATUS
approved