login
A365542
Number of subsets of {1..n-1} that can be linearly combined using nonnegative coefficients to obtain n.
5
0, 1, 2, 6, 10, 28, 48, 116, 224, 480, 920, 2000, 3840, 7984, 15936, 32320, 63968, 130176, 258304, 521920, 1041664, 2089472, 4171392, 8377856, 16726528, 33509632, 67004416, 134129664, 268111360, 536705024, 1072961536, 2146941952, 4293509120, 8588414976
OFFSET
1,3
EXAMPLE
The a(2) = 1 through a(5) = 10 partitions:
{1} {1} {1} {1}
{1,2} {2} {1,2}
{1,2} {1,3}
{1,3} {1,4}
{2,3} {2,3}
{1,2,3} {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-1]], combs[n, #]!={}&]], {n, 5}]
PROG
(Python)
from itertools import combinations
from sympy.utilities.iterables import partitions
def A365542(n):
a = {tuple(sorted(set(p))) for p in partitions(n)}
return sum(1 for m in range(1, n) for b in combinations(range(1, n), m) if any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 12 2023
CROSSREFS
The case of positive coefficients is A365042, complement A365045.
For subsets of {1..n} instead of {1..n-1} we have A365073.
The binary complement is A365315.
The complement is counted by A365380.
A124506 and A326083 appear to count combination-free subsets.
A179822 and A326080 count sum-closed subsets.
A364350 counts combination-free strict partitions.
A364914 and A365046 count combination-full subsets.
Sequence in context: A190034 A119459 A291463 * A364879 A192616 A243393
KEYWORD
nonn
AUTHOR
Gus Wiseman, Sep 09 2023
EXTENSIONS
More terms from Alois P. Heinz, Sep 13 2023
STATUS
approved