login
A365046
Number of subsets of {1..n} containing n such that some element can be written as a nonnegative linear combination of the others.
32
0, 0, 1, 2, 6, 11, 28, 53, 118, 235, 490, 973, 2008, 3990, 8089, 16184, 32563, 65071, 130667, 261183, 523388, 1046748, 2095239, 4190208, 8385030, 16768943, 33546257, 67092732, 134201461, 268400553, 536839090, 1073670970, 2147414967, 4294829905, 8589793931
OFFSET
0,4
COMMENTS
Includes all subsets containing both 1 and n.
LINKS
FORMULA
a(n+1) = 2^n - A124506(n).
EXAMPLE
The subset {3,4,10} has 10 = 2*3 + 1*4 so is counted under a(10).
The a(0) = 0 through a(5) = 11 subsets:
. . {1,2} {1,3} {1,4} {1,5}
{1,2,3} {2,4} {1,2,5}
{1,2,4} {1,3,5}
{1,3,4} {1,4,5}
{2,3,4} {2,3,5}
{1,2,3,4} {2,4,5}
{1,2,3,5}
{1,2,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
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]], MemberQ[#, n]&&Or@@Table[combs[#[[k]], Union[Delete[#, k]]]!={}, {k, Length[#]}]&]], {n, 0, 10}]
CROSSREFS
The complement is A124506, first differences of A326083.
The binary complement is A288728, first differences of A007865.
First differences of A364914.
The positive version is A365042, first differences of A365043.
The positive complement is counted by A365045, first differences of A365044.
Without re-usable parts we have A365069, first differences of A364534.
The binary version is A365070, first differences of A093971.
A364350 counts combination-free strict partitions, complement A364839.
A085489 and A364755 count subsets without the sum of two distinct elements.
A088809 and A364756 count subsets with the sum of two distinct elements.
A364913 counts combination-full partitions.
Sequence in context: A184884 A275222 A165821 * A296390 A135048 A189319
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 24 2023
STATUS
approved