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,2

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.

Links

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

S. R. Finch, Monoids of natural numbers, March 17, 2009.

Formula

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

Example

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}

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

Prog

(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

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.

Sequence in context: A110542 A101542 A101581 * A349676 A287915 A354141

Adjacent sequences: A365041 A365042 A365043 * A365045 A365046 A365047

Keyword

nonn

Author

Gus Wiseman, Aug 26 2023

Extensions

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

Status

approved