A365542 Number of subsets of {1..n-1} that can be linearly combined using nonnegative coefficients to obtain n.

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

Links

Table of n, a(n) for n=1..34.

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.

Cf. A007865, A088314, A088809, A151897, A364534, A364839, A365314, A365322.

Sequence in context: A190034 A119459 A291463 * A364879 A192616 A243393

Adjacent sequences: A365539 A365540 A365541 * A365543 A365544 A365545

Keyword

nonn

Author

Gus Wiseman, Sep 09 2023

Extensions

More terms from Alois P. Heinz, Sep 13 2023

Status

approved