|
|
A365073
|
|
Number of subsets of {1..n} that can be linearly combined using nonnegative coefficients to obtain n.
|
|
27
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
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)
|
|
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.
Cf. A007865, A088809, A093971, A151897, A237668, A308546, A326020, A364534, A364839, A365043, A365381.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|