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
S. R. Finch, Monoids of natural numbers, March 17, 2009.
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
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Aug 25 2023
EXTENSIONS
a(15)-a(35) from Chai Wah Wu, Nov 20 2023
STATUS
approved