A365044 Number of subsets of {1..n} whose greatest element cannot be written as a (strictly) positive linear combination of the others.

1, 2, 3, 5, 9, 20, 43, 96, 207, 442, 925, 1913, 3911, 7947, 16061, 32350, 64995, 130384, 261271, 523194, 1047208, 2095459, 4192212, 8386044, 16774078, 33550622, 67104244, 134212163, 268428760, 536862900, 1073732255, 2147472267, 4294953778, 8589918612, 17179850312

Offset: 0

Author

Gus Wiseman, Aug 26 2023

Keywords

• nonn

Comments

Sets of this type may be called "positive combination-free".

Also subsets of {1..n} such that no element can be written as a (strictly) positive linear combination of the others.

Examples

			The subset S = {3,5,6,8} has 6 = 2*3 + 0*5 + 0*8 and 8 = 1*3 + 1*5 + 0*6 but neither of these is strictly positive, so S is counted under a(8).
The a(0) = 1 through a(5) = 20 subsets:
  {}  {}   {}   {}     {}         {}
      {1}  {1}  {1}    {1}        {1}
           {2}  {2}    {2}        {2}
                {3}    {3}        {3}
                {2,3}  {4}        {4}
                       {2,3}      {5}
                       {3,4}      {2,3}
                       {2,3,4}    {2,5}
                       {1,2,3,4}  {3,4}
                                  {3,5}
                                  {4,5}
                                  {2,3,4}
                                  {2,4,5}
                                  {3,4,5}
                                  {1,2,3,4}
                                  {1,2,3,5}
                                  {1,2,4,5}
                                  {1,3,4,5}
                                  {2,3,4,5}
                                  {1,2,3,4,5}
		

Links

• Steven R. Finch, Monoids of natural numbers, March 17, 2009.

Crossrefs

The binary version is A007865, first differences A288728.

The binary complement is A093971, first differences A365070.

Without re-usable parts we have A151897, first differences A365071.

The nonnegative version is A326083, first differences A124506.

A subclass is A341507.

The nonnegative complement is A364914, first differences A365046.

The complement is counted by A365043, first differences A365042.

First differences are A365045.

A085489 and A364755 count subsets w/o the sum of two distinct elements.

A088809 and A364756 count subsets with the sum of two distinct elements.

A364350 counts combination-free strict partitions, complement A364839.

A364913 counts combination-full partitions.

Cf. A006951, A237113, A237668, A308546, A324736, A326020, A326080, A364272, A364349, A364534, A365069.

Programs

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[Subsets[Range[n]],And@@Table[combp[Last[#],Union[Most[#]]]=={},{k,Length[#]}]&]],{n,0,10}]

Python

from itertools import combinations
from sympy.utilities.iterables import partitions
def A365044(n):
    mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))
    return n+1+sum(1 for k in range(2,n+1) for w in combinations(range(1,n+1),k) if w[:-1] not in mlist[w[-1]-1]) # Chai Wah Wu, Nov 20 2023

Formula

a(n) = 2^n - A365043(n).

Extensions

a(15)-a(34) from Chai Wah Wu, Nov 20 2023