login
A365043
Number of subsets of {1..n} whose greatest element can be written as a (strictly) positive linear combination of the others.
18
0, 0, 1, 3, 7, 12, 21, 32, 49, 70, 99, 135, 185, 245, 323, 418, 541, 688, 873, 1094, 1368, 1693, 2092, 2564, 3138, 3810, 4620, 5565, 6696, 8012, 9569, 11381, 13518, 15980, 18872, 22194
OFFSET
0,4
COMMENTS
Sets of this type may be called "positive combination-full".
Also subsets of {1..n} such that some element can be written as a (strictly) positive linear combination of the others.
LINKS
FORMULA
a(n) = 2^n - A365044(n).
EXAMPLE
The subset S = {3,4,9} has 9 = 3*3 + 0*4, but this is not strictly positive, so S is not counted under a(9).
The subset S = {3,4,10} has 10 = 2*3 + 1*4, so S is counted under a(10).
The a(0) = 0 through a(5) = 12 subsets:
. . {1,2} {1,2} {1,2} {1,2}
{1,3} {1,3} {1,3}
{1,2,3} {1,4} {1,4}
{2,4} {1,5}
{1,2,3} {2,4}
{1,2,4} {1,2,3}
{1,3,4} {1,2,4}
{1,2,5}
{1,3,4}
{1,3,5}
{1,4,5}
{2,3,5}
MATHEMATICA
combp[n_, y_]:=With[{s=Table[{k, i}, {k, y}, {i, 1, Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Rest[Subsets[Range[n]]], combp[Last[#], Union[Most[#]]]!={}&]], {n, 0, 10}]
PROG
(Python)
from itertools import combinations
from sympy.utilities.iterables import partitions
def A365043(n):
mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m, k=m-1)} for m in range(1, n+1))
return sum(1 for k in range(2, n+1) for w in combinations(range(1, n+1), k) if w[:-1] in mlist[w[-1]-1]) # Chai Wah Wu, Nov 20 2023
CROSSREFS
The binary complement is A007865, first differences A288728.
The binary version is A093971, first differences A365070.
The nonnegative complement is A326083, first differences A124506.
The nonnegative version is A364914, first differences A365046.
First differences are A365042.
The complement is counted by A365044, first differences A365045.
Without re-usable parts we have A364534, first differences A365069.
A085489 and A364755 count subsets with no sum of two distinct elements.
A088809 and A364756 count subsets with some sum of two distinct elements.
A364350 counts combination-free strict partitions, complement A364839.
A364913 counts combination-full partitions.
Sequence in context: A337656 A029452 A367892 * A294422 A034434 A243190
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Aug 25 2023
EXTENSIONS
a(15)-a(35) from Chai Wah Wu, Nov 20 2023
STATUS
approved