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

Author

Gus Wiseman, Sep 09 2023

Keywords

• nonn

Examples

			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}
		

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.

Programs

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}]

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

Extensions

More terms from Alois P. Heinz, Sep 13 2023